高级检索

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

    Directed Graph Clustering Method with Edge Local Differential Privacy

    • 摘要: 基于本地差分隐私的图聚类工作成为近年来的一个研究热点. 已有工作主要针对的是无向图,且大多利用位向量技术通过模块化聚合实现的. 由于噪声量与向量维度成线性关系,使得聚类质量和隐私性难以很好的兼顾. 此外,针对无向图中边的有/无设计的2元扰动机制在面对有向图时,因无法对边的方向性进行处理而无法适用. 针对上述问题,提出一种基于本地边差分隐私(edge local differential privacy, Edge-LDP)的有向图聚类方法DGC-LDP (directed graph clustering under LDP). 具体来说,为了降低噪音量,同时适用于有向图,基于直接编码方式设计了一种适用于有向星型图的动态扰动机制,通过自适应添加噪声来平衡隐私性和统计效用. 在此基础上,在终端和收集者间构建迭代机制. 收集者依据终端上传的噪声数据,提取节点间的相似性信息,并设计基于轮廓系数测量模型的节点聚合方法,通过迭代机制不断的优化节点聚合形式,形成高质量簇. 理论分析和实验结果表明,所提方法在满足Edge-LDP 的同时能够有效兼顾聚类精度.

       

      Abstract: 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 method, 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 method 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 method can obtain desirable clustering results while satisfying edge-LDP.

       

    /

    返回文章
    返回