Accepted Paper: Differentially Private Community Detection in Attributed Social Networks

Back to list of accepted papers


Tianxi Ji (Case Western Reserve University); Changqing Luo (Virginia Commonwealth University); Yifan Guo (Case Western Reserve University); Jinlong Ji (Case Western Reserve University); Weixian Liao (Towson University); Pan Li (Case Western Reserve University)


Community detection is an effective approach to unveil social dynamics among individuals in social networks. In the literature, quite a few algorithms have been proposed to conduct community detection by exploiting the topology of social networks and the attributes of social actors. In practice, community detection is usually conducted by third parties like advertisement companies, hospitals, with access to social networks for different purposes, which can easily lead to privacy breaches. In this paper, we investigate community detection in social networks aiming to protect the privacy of both the network topologies and the users’ attributes. In particular, we propose a new scheme called differentially private community detection (DPCD). DPCD detects communities in social networks via a probabilistic generative model, which can be decomposed into subproblems solved by individual users. The private social relationships and attributes of each user are protected by objective perturbation with differential privacy guarantees. Through both theoretical analysis and experimental validation using synthetic and real world social networks, we demonstrate that the proposed DPCD scheme detects social communities under modest privacy budget.