Improving the Accuracy of Locally Differentially Private Community Detection by Order-consistent Data Perturbation

Community detection refers to mechanisms that aim to identify groups of interacting nodes in a network according to the structural properties of the network. It has been used to analyze various graphs. In the context of social networks, it requires the collection of each user's social relations, posing the risk of user privacy intrusion caused by untrusted servers. Local differential privacy is a widely adopted approach for providing privacy protection while allowing acceptable utility of the protected data for analytics. There has been growing research interest in applying local differential privacy protection to community detection. However, such protection approaches typically suffer from poor accuracy due to the excessive noise in the protected data. This paper proposes LDP-Cd, a two-phase community detection framework under local differential privacy. LDP-Cd initializes the community groups using the Louvain community detection algorithm and iteratively refines the community in the second phase. Besides, we propose an order-consistent data perturbation method over the degree vector, thus ensuring the ordering consistency of the fitness between the user and community groups, thereby improving the accuracy of community detection. Experimental results on real datasets show that LDP-Cd has significant advantages over existing methods regarding community detection accuracy and a trade-off between user privacy and community detection utility.