Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (12): 3831-3838.DOI: 10.11772/j.issn.1001-9081.2023111706

• Cyber security • Previous Articles     Next Articles

Dynamic social network privacy publishing method for partial graph updating

Rui GAO1,2,3, Xuebin CHEN1,2,3(), Zucuan ZHANG1,2,3   

  1. 1.College of Science,North China University of Science and Technology,Tangshan Hebei 063210,China
    2.Hebei Key Laboratory of Data Science and Application (North China University of Science and Technology),Tangshan Hebei 063210,China
    3.Tangshan Key Laboratory of Data Science (North China University of Science and Technology),Tangshan Hebei 063210,China
  • Received:2023-12-11 Revised:2024-03-17 Accepted:2024-03-27 Online:2024-04-12 Published:2024-12-10
  • Contact: Xuebin CHEN
  • About author:GAO Rui, born in 2000, M. S. candidate. His research interests include data security, privacy protection.
    ZHANG Zucuan, born in 1998, M. S. candidate. His research interests include data security, federated learning.
  • Supported by:
    National Natural Science Foundation of China(U20A20179)

面向部分图更新的动态社交网络隐私发布方法

高瑞1,2,3, 陈学斌1,2,3(), 张祖篡1,2,3   

  1. 1.华北理工大学 理学院,河北 唐山 063210
    2.河北省数据科学与应用重点实验室(华北理工大学),河北 唐山 063210
    3.唐山市数据科学重点实验室(华北理工大学),河北 唐山 063210
  • 通讯作者: 陈学斌
  • 作者简介:高瑞(2000—),男,江苏南京人,硕士研究生,CCF会员,主要研究方向:数据安全、隐私保护
    张祖篡(1998—),男,江苏徐州人,硕士研究生,CCF会员,主要研究方向:数据安全、联邦学习。
  • 基金资助:
    国家自然科学基金资助项目(U20A20179)

Abstract:

Aiming at the problems of excessive added noise scale and error accumulation during iteration in existing dynamic social network privacy protection, a method named PGU-DNDP (Partial Graph Updating in Dynamic social Network based on Differential Privacy) was proposed. Firstly, the update sequences in the network snapshot graph set were collected through a temporal trade-off dynamic community discovery algorithm. Secondly, a static graph publishing method was used to obtain the initial generated graph. Finally, based on the generated graph of the previous moment and the update sequence of the current moment, the partial graph update was completed. The partial update method could reduce the excessive noise caused by the full graph perturbation and optimize the time cost, thus avoiding the intensive situation of synthetic graph. In addition, an edge updating strategy was proposed in the partial update, which combined the adaptive perturbation with a downsampling mechanism to reduce the cumulative error in the iterative process through privacy amplification, thus improving the synthetic graph accuracy effectively. Experimental results on three synthetic datasets and two real-world dynamic datasets show that PGU-DNDP can ensure the privacy requirements of dynamic social networks while retaining higher data utility than mainstream static graph generation method PrivGraph (differentially Private Graph data publication by exploiting community information).

Key words: local differential privacy, dynamic social network, privacy protection, dynamic graph publishing, privacy amplification

摘要:

针对现有动态社交网络隐私保护中存在的添加噪声尺度过大以及迭代过程中误差积累的问题,提出一种面向部分图更新的动态社交网络隐私发布方法PGU-DNDP(Partial Graph Updating in Dynamic social Network based on Differential Privacy)。首先,通过时间权衡的动态社区发现算法收集网络快照图集合中的更新序列;其次,使用静态图发布方法得到初始生成图;最后,基于上一时刻的生成图和当前时刻更新序列完成部分图更新。部分更新的方法可以降低全图扰动带来的过量噪声并优化时间成本,避免合成图密集情况发生。此外,在部分更新中设计一种边缘更新策略,结合自适应的扰动和下采样机制,通过隐私放大减小迭代过程中的累积误差,从而有效提高合成图的精度。在3个合成数据集和2个真实的动态数据集上的实验结果表明,PGU-DNDP能够在保证动态社交网络隐私需求的同时,比主流的静态图生成方法PrivGraph(differentially Private Graph data publication by exploiting community information)保留更高的数据效用。

关键词: 本地化差分隐私, 动态社交网络, 隐私保护, 动态图发布, 隐私放大

CLC Number: