Overlapping community detection by constrained personalized PageRank

摘要

Given a network, local community detection (a.k.a. graph clustering) methods aim at finding communities around the selected initial nodes (also referred to as seeds, starting nodes or core nodes). Methods in this kind successfully address the efficiency problem confronted by global clustering methods. And techniques, such as personalized PageRank and heat kernel diffusion, for ranking the proximity score of vertices nearby with respect to the corresponding starting nodes are developed. However, most of the random-walk based metrics allow a walker to diffuse without any constraint, and the walker can easily run into irrelevant communities. As a result, the corresponding community could include irrelevant high-quality communities (communities with good fitness score) nearby, we refer to the case that a walker goes into irrelevant communities and causes inaccurate expansion of a community as redundant diffusion. In this work, we develop a constrained personalized PageRank method for community expansion to reduce the problem of redundant diffusion. In the mechanism, a walker moves with lower probability to neighbor nodes already in the existing communities, and a walker tends to walk out of the community if the walker walks into an irrelevant community. Extensive experiments on synthetic and large real-world networks demonstrate that the proposed method outperforms approaches in the state of the art by a large margin in accuracy and efficiency.