A three-stage algorithm for local community detection based on the high node importance ranking in social networks

Community detection aims to discover and reveal community structures in complex networks. Some community detection method is called local methods that only apply local information in discovering steps. Local community detection methods are actually an attempt to increase efficiency in large-scale networks. Most of local community detection methods concentrate on finding the important nodes as initial communities. The quality of the detected communities fundamentally depends on the selected important nodes as community cores. Most of the existing works have disadvantages such as low accuracy, weak scalable, and instability in outcomes that makes the algorithm to detect different communities in each run. In order to solve these problems, this paper proposes a novel local community detection based on high importance nodes Ranking (LCDR). In the proposed algorithm, a new index for computing node importance is presented. With regards to the network locality, the proposed index can fully reflect the node importance of all nodes in the network. LCDR method initially selects important nodes to expand the initial communities based on a local similarity criterion until all nodes become members of one of the communities. Finally, it merges the discovered communities to form final community structures. Experiments on real and synthetic networks show that LCDR can significantly improve the accuracy of communities. Correspondingly, it is promising in different settings based on accuracy and modularity with near-linear time complexity.