差分隐私下的权重社交网络隐私保护

doi:10.19665/j.issn1001-2400.2022.01.002

西安电子科技大学学报 ›› 2022, Vol. 49 ›› Issue (1): 17-25.doi: 10.19665/j.issn1001-2400.2022.01.002

• 隐私计算与数据安全专题 • 上一篇下一篇

差分隐私下的权重社交网络隐私保护

徐花^1,²(),田有亮^1,^2,³()

1.贵州大学计算机科学与技术学院,贵州贵阳 550025
2.贵州省公共大数据重点实验室,贵州贵阳 550025
3.贵州大学密码学与数据安全研究所,贵州贵阳 550025

收稿日期:2021-08-31 出版日期:2022-02-20 发布日期:2022-04-27
作者简介:徐花(1994—),女,贵州大学硕士研究生,E-mail: 17862325639@163.com;|田有亮(1982—),男,教授,E-mail: youliangtian@163.com
基金资助:
国家自然科学基金(61662009);国家自然科学基金(61772008);国家自然科学基金联合基金重点支持项目(U1836205);贵州省科技重大专项计划(20183001);贵州省科技计划(黔科合基础[2019]1098(黔科合基础[2019]1098);贵州省高层次创新型人才项目(黔科合平台人才[2020]6008(黔科合平台人才[2020]6008)

Protection of privacy of the weighted social network under differential privacy

XU Hua^1,²(),TIAN Youliang^1,^2,³()

1. College of Computer Science and Technology,Guizhou University,Guiyang 550025,China
2. State Key Laboratory of Public Big Data,Guizhou University,Guiyang 550025,China
3. Institute of Cryptography & Date Security,Guizhou University,Guiyang 550025,China

Received:2021-08-31 Online:2022-02-20 Published:2022-04-27

摘要/Abstract

摘要：

由于权重社交网络的复杂性和噪声随机性,传统的隐私保护方法无法兼顾社交网络中的隐私和效用需求。针对此问题,融合直方图统计和非交互式差分隐私查询模型,提出社交网络边权重直方图统计发布方法。该方法将边权重统计直方图作为查询结果,并设计低敏感度的边权重拉普拉斯噪声随机扰动算法,实现社交关系的差分隐私保护。为减少噪声量,引入社区结构熵将社交网络的用户节点划分为若干子社区,提出随机扰动改进算法,以社区为单位划分社交关系并注入拉普拉斯噪声,使各个社区序列满足差分隐私,实现从社区层面保护社交关系。此外,利用一维结构熵的特性,衡量算法对权重社交网络的整体隐私保护程度。理论分析和实验结果表明:所提出的隐私保护算法对节点度识别的保护程度均高于对比算法,能够实现更好的隐私保护效果,同时,在大型社交网络中能够满足差分隐私要求,且保持较高的社交网络数据效用。

关键词: 权重社交网络, 差分隐私, 直方图发布, 社区结构熵, 边关系分组

Abstract:

Due to randomness of noise and complexity of weighted social networks,traditional privacy protection methods cannot balance both data privacy and utility issues in social networks.This paper addresses these problems,combines histogram statistics and non-interactive differential privacy query model,and proposes a statistical releasing method for the histogram of weighted-edges in social networks.This method regards the statistical histogram of weighted-edges as the query result and designs the low-sensitivity Laplace noise random perturbation algorithm,which realizes the differential privacy protection of social relations.In order to reduce errors,the community structure entropy is introduced to divide the user nodes of the social network into several sub-communities,with the improved stochastic perturbation algorithm proposed.The social relationship is divided by community as a unit and Laplace noise is injected,so that each sequence of community satisfies the differential privacy with the social relationship protected from the community level.In addition,the characteristics of one-dimensional structural entropy are used to measure the overall privacy protection degree of the algorithm with respect to the weighted social network.By theoretical analysis and experimental results,the privacy protection algorithm proposed in this paper has a higher protection degree than the comparison algorithm for node degree identification,which achieves a better privacy protection effect.Meanwhile,it can meet the requirements of differential privacy in large social networks and maintain a high data utility of the weighted social network.

Key words: weighted social network, differential privacy, histogram release, community structure entropy, edge relation grouping

中图分类号:

TP309

徐花,田有亮. 差分隐私下的权重社交网络隐私保护[J]. 西安电子科技大学学报, 2022, 49(1): 17-25.

XU Hua,TIAN Youliang. Protection of privacy of the weighted social network under differential privacy[J]. Journal of Xidian University, 2022, 49(1): 17-25.

图/表 6

图1

图2

图3

图4

图5

图6

参考文献 22

[1]	HAY M, MIKLAU G, JENSEN D, et al. Resisting Structural Re-Identification in Anonymized Social Networks[J]. The VLDB Journal, 2010, 19(6):797-823. doi: 10.1007/s00778-010-0210-x
[2]	WONDRACEK G, HOLZ T, KIRDA E, et al. A Practical Attack to De-Anonymize Social Network Users[C]// 2010 IEEE Symposium on Security and Privacy.Piscataway:IEEE, 2010,223-238.
[3]	LIU K, TERZI E. Towards Identity Anonymization on Graphs[C]// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2008.93-106.
[4]	LIN S H, LIAO M H. Towards Publishing Social Network Data with Graph Anonymization[J]. Journal of Intelligent & Fuzzy Systems Applications in Engineering & Technology, 2016, 30(1):333-345.
[5]	YUAN Y, WANG G R, XU Y J, et al. Efficient Distributed Subgraph Similarity Matching[J]. VLDB Journal:The International Journal of Very Large Data Bases, 2015, 24(3):369-396.
[6]	ZOU L, CHEN L, ZSU M T. K-Automorphism:A General Framework for Privacy Preserving Network Publication[J]. VLDB Endowment, 2009, 2(1):946-957.
[7]	LI Y D, SHEN H. Anonymizing Graphs Against Weight-Based Attacks[C]// 2010 IEEE International Conference on Data Mining Workshops.Piscataway:IEEE, 2010,491-498.
[8]	BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast Unfolding of Communities in Large Networks[J]. Journal of Statistical Mechanics Theory and Experiment, 2008, 4(10):10008-10021.
[9]	LIU Y, LIU J, ZHANG Z, et al. REM:From Structural Entropy to Community Structure Deception[J]. Advances in Neural Information Processing Systems, 2019, 32:12918-12928.
[10]	XIAO Q, CHEN R, TAN K L. Differentially Private Network Data Release via Structural Inference[C]// Proceedings of the 20^th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2014:911-920.
[11]	NING B, SUN Y, TAO X, et al. Differential Privacy Protection on Weighted Graph in Wireless Networks[J]. Ad Hoc Networks, 2021, 110:102303. doi: 10.1016/j.adhoc.2020.102303
[12]	吴振强, 胡静, 田堉攀, 等. 社交网络下的不确定图隐私保护算法[J]. 软件学报, 2019, 30(4):1106-1120.
	WU Zhenqiang, HU Jing, TIAN Yupan, et al. Privacy Preserving Algorithms of Uncertain Graphs in Social Networks[J]. Journal of Software, 2019, 30(4):1106-1120.
[13]	WANG D, LONG S G. Boosting the Accuracy of Differentially Private in Weighted Social Networks[J]. Multimedia Tools and Applications, 2019, 78(24):34801-34817. doi: 10.1007/s11042-019-08092-0
[14]	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. doi: 10.1109/TNSM.2020.2982555
[15]	LI A S, PAN Y C. Structural Information and Dynamical Complexity of Networks[J]. IEEE Transactions on Information Theory, 2016, 62(6):3290-3339. doi: 10.1109/TIT.2016.2555904
[16]	DWORK C. Differential Privacy[C]// International Colloquium on Automata,Languages,and Programming.Heidelberg:Springer, 2006:1-12.
[17]	DWORK C, MCSHERRY F, NISSIM K, et al. Calibrating Noise to Sensitivity in Private Data Analysis[C]// Theory of Cryptography Conference.Heidelberg:Springer, 2006:265-284.
[18]	MCSHERRY F. Privacy Integrated Queries:An Extensible Platform for Privacy-Preserving Data Analysis[C]// Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2009:19-30.
[19]	DWORK C. The Differential Privacy Frontier[C]// Theory of Cryptography Conference.Heidelberg:Springer, 2009:496-502.
[20]	张啸剑, 邵超, 孟小峰. 差分隐私下一种精确直方图发布方法[J]. 计算机研究与发展, 2016, 53(5):1106-1117.
	ZHANG Xiaojian, SHAO Chao, MENG Xiaofeng. Accurate Histogram Release under Differential Privacy[J]. Journal of Computer Research and Development, 2016, 53(5):1106-1117.
[21]	LI A S, LI J K PAN YC. Discovering Natural Communities in Networks[J]. Physical A:Statistical Mechanics and Its Applications, 2015, 436:878-896.
[22]	TIAN Y L, ZHANG Z L, XIONG J B, et al. Achieving Graph Clustering Privacy Preservation Based on Structure Entropy in Social IoT[J]. IEEE Internet of Things Journal, 2021(Early Access):1-1.

差分隐私下的权重社交网络隐私保护

Protection of privacy of the weighted social network under differential privacy

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 22

相关文章 1

Metrics

本文评价

推荐阅读 0