Abstract: Aiming at the problems of excessive noise scale and error accumulation in existing dynamic social network privacy protection, a dynamic social network data privacy release method PGU-DNDP for partial graph updates is proposed to solve these problems. This scheme first collects update sequences from the network snapshot graph set through a Temporal Trade-off dynamic community discovery algorithm; then we use a static graph generation algorithm to obtain the initial graph generation work for the first snapshot graph; Then, based on the generated graph from the previous time and the update sequence from the current time, partial graph updates are completed. We utilized a partially updated approach to reduce excessive noise caused by full graph perturbations and optimize time costs, avoiding the occurrence of dense synthetic graph. In addition, we propose an edge update strategy combined with adaptive perturbation and downsampling techniques to reduce cumulative errors during the iteration process through privacy amplification, effectively improving the accuracy of the synthesized graph. Experimental results on three synthetic datasets and two real dynamic network datasets show that our proposed scheme is able to retain higher data utility while ensuring the privacy requirements of dynamic social network data.

Key words: Local Differential Privacy, Dynamic Social Networks, Privacy Protection, Dynamic Graph Publishing, Privacy amplification

摘要： 针对于现有动态社交网络隐私保护中存在的添加噪声尺度过大以及迭代过程中误差积累的问题，提出了一种面向部分图更新的动态社交网络隐私发布方法(PGU-DNDP)。该算法首先通过时间权衡的动态社区发现算法收集网络快照图集合中的更新序列；接着使用静态图发布方法得到初始生成图；然后基于上一时刻的生成图和当前时刻更新序列完成部分图更新。利用部分更新的方法降低了全图扰动带来的过量噪声并优化时间成本，避免了合成图密集情况发生。此外提出边缘更新策略结合自适应的扰动和下采样机制通过隐私放大减少了迭代过程中的累积误差，从而有效提高合成图精度。通过在三个合成数据集和两个真实的动态数据集上的实验结果表明，所提算法能够在保证动态社交网络隐私需求的同时，保留更高的数据效用。

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