College of Science, Hebei Key Laboratory of Data Science and Application, Tangshan Key Laboratory of Data Science, North China University of Science and Technology

【目的】针对现有本地化差分隐私社交网络图生成算法中直接扰动邻居列表的方法会导致引入过多噪声且隐私保护程度不均衡的问题,提出了一种满足个性化的本地差分隐私社交网络图生成方法(GPDP)。【方法】首先,使用传统的社区发现算法Louvain对原始社交网络图进行划分,保留社区信息;其次,对于划分后的社区根据其社区内部平均权重度比值作为新的隐私预算参数分配给每个节点;然后,每个节点根据新的隐私预算各自扰动其邻居列表,同时利用随机邻接位向量(RABV)方法降低通讯成本;最后合并邻居列表形成生成图。【结果】通过在真实数据集上的实验结果表明,该算法在发布合成图数据时保证了数据隐私性和可用性的均衡,同时保留了更多的社区结构信息。

【Purposes】 Aiming at the problem that the randomized neighbor list method of di-rectly disturbing the neighbor list in the existing local differential privacy social network graph generation algorithm will lead to excessive noise and imbalanced privacy protection, a new social network graph generation algorithm satisfying personalized local differential privacy is proposed. 【Methods】 First, the Louvain algorithm is used to partition the original social network graph and preserve community information; Second, for the divided community, a new privacy budget pa-rameter is allocated to each node on the basis of the average weight ratio within the community; Then each node perturbs its neighbor list separately, meanwhile by using the Randomized Adja-cency Bit Vector method to reduce communication consumption; Finally, merge the neighbor lists are merged to form a generated graph. 【Findings】 The experimental results on real datasets show that this algorithm ensures a balance between data privacy and availability when publishing synthetic graph data, while retaining more community structure information.

国家自然科学基金资助项目(U20A20179)

高瑞,陈 学 斌,谷 铮,等.满 足 个 性 化 差 分 隐 私 的 社 交 网 络 图 生 成 方 法[J].太 原 理 工 大 学 学 报,2024,55(1):163-171.

GAO Rui,CHEN Xuebing,GU Zheng,et al.Social network graph generation method satisfying personalized dif-ferential privacy[J].Journal of Taiyuan University of Technology,2024,55(1):163-171.