基于谱聚类的社交网络差分隐私保护算法研究

计算机工程与科学 ›› 2022, Vol. 44 ›› Issue (02): 251-256.

• 计算机网络与信息安全 • 上一篇下一篇

基于谱聚类的社交网络差分隐私保护算法研究

袁泉1，2，3，晏飞扬1，2，文志云1，2，张振康1，2

（1.重庆邮电大学通信与信息工程学院,重庆 400065；

2.重庆邮电大学通信新技术应用研究中心，重庆 400065；3.重庆信科设计有限公司，重庆 401121）

收稿日期:2020-09-07 修回日期:2020-11-18 接受日期:2022-02-25 出版日期:2022-02-25 发布日期:2022-02-17

A differential privacy protection algorithm in social network based on spectral clustering

YUAN Quan1,2,3,YAN Fei-yang1,2,WEN Zhi-yun1,2,ZHANG Zhen-kang1,2

(1.School of Communication and Information Engineering,
Chongqing University of Posts and Telecommunications,Chongqing 400065;

2.Research Center of New Telecommunication Technology Applications,
Chongqing University of Posts and Telecommunications,Chongqing 400065;

3.Chongqing Information Technology Designing Co.,LTD.,Chongqing 401121,China)

Received:2020-09-07 Revised:2020-11-18 Accepted:2022-02-25 Online:2022-02-25 Published:2022-02-17

摘要/Abstract

摘要： 针对权重社交网络差分隐私保护算法中噪声添加量过大以及隐私保护不均衡问题，提出了一种结合谱聚类算法与差分隐私保护模型的隐私保护算法SCDP。首先针对传统差分隐私保护算法直接向社交网络边权重添加噪声方式带来的噪声添加量过大的问题，结合谱聚类算法，将权重社交网络聚类成为不同的簇，对不同的簇采取随机添加噪声的方式，降低噪声的添加量，提高数据的可用性；其次设计新的隐私预算参数，根据社交网络边权重的大小决定噪声的添加量，实现更均衡的隐私保护；最后通过理论推导和实验证明了SCDP算法处理后的数据可用性更高。

关键词: 权重社交网络, 差分隐私, 谱聚类

Abstract: Aiming at the problems of excessive noise addition and unbalanced privacy protection in the differential privacy protection algorithm of weighted social networks, a privacy protection algorithm combining spectral clustering algorithm and differential privacy protection model is proposed. Firstly, to solve the problem of excessive noise addition caused by the way of directly adding noise to the side weights of social networks by traditional differential privacy protection algorithms, combined with the spectral clustering algorithm, the weighted social networks are clustered into different clusters, and different clusters are randomly selected. The method of adding noise reduces the amount of noise added and improves the availability of data. Secondly, new privacy budget parameters are designed, and the amount of noise added is determined according to the weight of the social network side, so as to achieve a more balanced privacy protection. Finally, theoretical derivation and experiments prove that the data processed by the proposed algorithm have higher availability.

Key words: weighted social network, differential privacy, spectral clustering

袁泉, 晏飞扬, 文志云, 张振康, . 基于谱聚类的社交网络差分隐私保护算法研究[J]. 计算机工程与科学, 2022, 44(02): 251-256.

YUAN Quan, YAN Fei-yang, WEN Zhi-yun, ZHANG Zhen-kang, . A differential privacy protection algorithm in social network based on spectral clustering [J]. Computer Engineering & Science, 2022, 44(02): 251-256.

参考文献［10］

［1］	Wang Jun.Looking at the predicament and way out of privacy protection in the era of artificial intelligence from the "Leak Door" of Facebook ［J］.Northern Media Research,2018(4):46-50.(in Chinese)
［2］	Dwork C.Differential privacy［C］∥Proc of International Colloquium on Automata Languages and Programming,2006:1-12.
［3］	Lan Li-hui, Ju Shi-guang.Privacypreserving based on diffe- rential privacy for weighted
	social networks［J］.Journal on Communications,2015,36(9):145-159.(in Chinese)
［4］	Li X Y, Yang J,Sun Z L,et al.Differential privacy for edge weights in social networks［J］.Security and Communication Networks,2017,2017:1-10.
［5］	Huang H,Zhang D J,Xiao F,et al.Privacy-preserving approach PBCN in social network with differential privacy［J］.IEEE Transactions on Network and Service Management,2020,17(2):931-945.
［6］	Qin Z,Yu T,Yang Y,et al.Generating synthetic decentra- lized social graphs with local differential privacy［C］∥Proc of
	the 2017 ACM SIGSAC Conference on Computer and Communications Security,2017:425-438.
［7］	Chen X,Mauw S,Ramirezcruz Y,et al.Publishing community-preserving attributed social graphs with a differential privacy guarantee［J］.arXiv:1909.00280,2019.
［8］	Sun H P,Xiao X K,Khalil I,et al.Analyzing subgraph statistics from extended local views with decentralized differential privacy［C］∥Proc ofthe 2019 ACM SIGSAC Conference on Computer and Communications Security,2019:703-717.
［9］	Qian Q, Li Z X,Zhao P P,et al.Publishing graph node strength histogram with edge differential privacy［C］∥Proc of International Conference on Database Systems for Advanced Applications,2018:75-91.
［10］	Cai Xiao-yan, Dai Guan-zhong,Yang Li-bin. Survey on spectral clustering algorithms［J］.Computer Science,2008,35(7):14-18.(in Chinese)
［11］	Knuth D E.The Stanford GraphBase:A platform for combinatorial computing［M］.New Jersey:Addison-Wesley,1993.
［12］	Girvan M,Newman M E J.Community structure in social and biological networks ［J］.Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
	附中文参考文献：
［1］	王军.从脸书“泄密门”看人工智能时代隐私保护的困局与出路［J］.北方传媒研究,2018(4):46-50.
［3］	兰丽辉,鞠时光.基于差分隐私的权重社会网络隐私保护［J］.通信学报,2015,36(9):145-159.
［10］	蔡晓妍,戴冠中,杨黎斌.谱聚类算法综述［J］.计算机科学,2008,35(7):14-18.

[1]	李帅, 常锦才, 李吕牧之, 蔡昆杰, . 基于差分隐私保护的Stacking集成聚类算法研究[J]. 计算机工程与科学, 2022, 44(08): 1402-1408.
[2]	胡雨谷, 葛丽娜, . 一种改进的差分隐私参数设置及数据优化算法[J]. 计算机工程与科学, 2021, 43(10): 1758-1765.
[3]	贾俊杰，陈慧，马慧芳，牟玉祥. 差分隐私的查询一致性约束研究[J]. 计算机工程与科学, 2020, 42(01): 71-79.
[4]	毛伊敏，刘银萍. 基于复合物参与度和密度的关键蛋白质预测[J]. 计算机工程与科学, 2019, 41(10): 1738-1748.
[5]	周伟，肖杨 . 基于Canopy聚类的谱聚类算法[J]. 计算机工程与科学, 2019, 41(06): 1095-1100.
[6]	付玉香1，秦永彬1,2，申国伟1,2. 基于迁移学习的多源数据隐私保护方法研究[J]. 计算机工程与科学, 2019, 41(04): 641-648.
[7]	万月，陈秀宏，何佳佳. 基于加权密度的自适应谱聚类算法[J]. 计算机工程与科学, 2018, 40(10): 1897-1901.
[8]	刘汉强，张青. 区间模糊谱聚类图像分割方法[J]. 计算机工程与科学, 2018, 40(09): 1611-1616.
[9]	高志强，崔翛龙，周沙，袁琛. 本地差分隐私保护及其应用[J]. 计算机工程与科学, 2018, 40(06): 1029-1036.
[10]	李瑞琳1,2，赵永华1，黄小磊2,3. 一种基于MPI的稀疏化局部尺度并行谱聚类算法的研究与实现[J]. J4, 2016, 38(05): 839-847.
[11]	吴伟民，黄焕坤. 基于差分隐私保护的DP-DBScan聚类算法研究[J]. J4, 2015, 37(04): 830-834.
[12]	张振宇,张珍,杨文忠,吴晓红. 复杂网络中重叠社区检测[J]. J4, 2013, 35(12): 76-83.

基于谱聚类的社交网络差分隐私保护算法研究

A differential privacy protection algorithm in social network based on spectral clustering

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献［10］

相关文章 12

编辑推荐

Metrics

本文评价

基于谱聚类的社交网络差分隐私保护算法研究

A differential privacy protection algorithm in social network based on spectral clustering

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 ［10］

相关文章 12

编辑推荐

Metrics

本文评价

参考文献［10］