Social Network Graph Generation Method Satisfying Personalized Differential Privacy

Abstract

Purposes Aiming at the problem that the randomized neighbor list method of directly 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 parameter 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 Adjacency 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.

Keywords

• personalized differential privacy
• social network
• privacy protection
• synthetic graph generation