基于本地边差分隐私的有向图聚类算法  

Directed Graph Clustering Algorithm with Edge Local Differential Privacy

作　　者：付楠 倪巍伟[1] 姜泽鹏 侯立贺 张东月 张如玉 Fu Nan;Ni Weiwei;Jiang Zepeng;Hou Lihe;Zhang Dongyue;Zhang Ruyu(School of Computer Science and Engineering,Southeast University,Nanjing 211102)

机构地区：[1]东南大学计算机科学与工程学院,南京211102

出　　处：《计算机研究与发展》2025年第1期256-268,共13页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61772131)。

摘　　要：基于本地差分隐私的图聚类工作成为近年来的一个研究热点.已有工作主要针对的是无向图,且大多利用位向量技术通过模块化聚合实现.由于噪声量与向量维度成线性关系,使得聚类质量和隐私性难以很好地兼顾.此外,针对无向图中边的有/无设计的2元扰动机制在面对有向图时,因无法对边的方向性进行处理而无法适用.针对上述问题,提出一种基于本地边差分隐私(edge local differential privacy,Edge-LDP)的有向图聚类算法DGC-LDP(directed graph clustering under LDP).具体来说,为了降低噪音量同时适用于有向图,基于直接编码方式设计了一种适用于有向星型图的动态扰动机制,通过自适应添加噪声来平衡隐私性和统计效用.在此基础上,在终端和收集者之间构建迭代机制.收集者依据终端上传的噪声数据提取节点间的相似性信息,并设计基于轮廓系数测量模型的节点聚合算法,通过迭代机制不断地优化节点聚合形式形成高质量簇.理论分析和实验结果表明,所提算法在满足Edge-LDP的同时能够有效兼顾聚类精度.Graph clustering based on local differential privacy has become a hot research topic in recent years.Most existing solutions are mainly realized through modular aggregation using bit vector technology.The linear relationship between the amount of noise and the vector dimension makes balancing clustering quality and privacy challenges.Aiming at the above problems,a directed graph clustering algorithm,DGC-LDP(directed graph clustering under LDP),is proposed based on edge local differential privacy(Edge-LDP).Concretely,the direct encoding method replaces the bit vector encoding method to reduce the amount of data in privacy processing.Meanwhile,a dynamic perturbation mechanism is designed based on the graph structure to balance privacy and statistical utility by adaptively adding noise.Then,according to the individual information uploaded by the terminal,the collector extracts the similarity information between nodes and designs a node aggregation algorithm based on the silhouette coefficient measurement model to generate clusters.Finally,an iterative mechanism is built between the terminal and the collector,and the collector iteratively optimizes the node aggregation form based on the statistical information fed back by the mechanism to achieve high-quality clustering.Theoretical analysis and experimentation on real-world datasets demonstrate that our proposed algorithm can obtain desirable clustering results while satisfying Edge-LDP.

关 键 词：隐私保护 本地差分隐私 图聚类 随机响应 相似度 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]