WtLDP: Generating Synthetic Decentralized Weighted Graphs with Local Differential Privacy
摘要
In numerous scenarios, each node only has information about its adjacent nodes and no single node possesses the entire graph structure, as seen in call records and autonomous systems. The weights could represent the frequency of calls or the traffic between autonomous systems, reflecting the relationships between nodes. However, there is a conflict between collecting weighted graphs and protecting user privacy. Meanwhile, existing methods do not adequately protect weighted graphs. To address this issue, in this paper, we propose a method for generating a weighted graph with certain similarities in structure and weights while protecting user privacy under local differential privacy, called WtLDP, which mainly consists of three phases: initial community detection, community adjustment and synthetic graph generation, weight protection and weight generation. During the weight protection phase, we propose high-sensitivity method and low-sensitivity method for protecting the weights. For low-sensitivity method, we group the weights by dividing adjacent weights into one cluster and balance the noise level with the weight information by adjusting the number of groups. Extensive experiments across three distinct datasets has yielded promising outcomes at clustering coefficient, modularity, hellinger distance of weights and the relative error of total node weight, affirming the efficacy of our proposed method.