A weighted local view method based on observation over ground truth for community detection

摘要

Community detection is a fundamental problem for many networks, and there have been a lot of methods proposed to discover communities. However, due to the rapid increase of the scale and diversity of networks, the modular organization at the global level in many large networks is often extremely difficult to recognize. In these cases, many existing methods fail to discover the latent community structure, because they follow a paradigm of discovering communities from a global view of networks. In this paper, we propose a weighted local view method based on an interesting observation on ground-truth communities, with the aim of revealing community structure in large real networks. This is achieved by the following steps: 1) a set of nodes which can well represent their neighboring nodes are chosen by local seeding strategies; 2) each chosen node explores the community in its local view to the whole network, using an improved approximate personalized PageRank-based community finder which is based on an interesting observation on large real networks with ground-truth communities; 3) all explored local communities are merged to form the global community structure. We evaluate the weighted local view method against the state-of-the-art community detection methods on large real networks with ground-truth communities. Experiments show that the proposed method can not only improve the detected communities, but can also scale to very large networks with good computational efficiency compared with other methods, which indicates that the weighted local view method has great potential for overlapping community detection in large networks. (C) 2016 Elsevier Inc. All rights reserved.