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

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