Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction

Abstract

Label propagation has proven to be a fast method for detecting communities in large complex networks. Recent developments have also improved the accuracy of the approach, however, a general algorithm is still an open issue. We present an advanced label propagation algorithm that combines two unique strategies of community formation, namely, defensive preservation and offensive expansion of communities. Two strategies are combined in a hierarchical manner, to recursively extract the core of the network, and to identify whisker communities. The algorithm was evaluated on two classes of benchmark networks with planted partition and on almost 25 real-world networks ranging from networks with tens of nodes to networks with several tens of millions of edges. It is shown to be comparable to the current state-of-the-art community detection algorithms and superior to all previous label propagation algorithms, with comparable time complexity. In particular, analysis on real-world networks has proven that the algorithm has almost linear complexity, $\mathcal{O}(m^{1.19})$, and scales even better than basic label propagation algorithm ($m$ is the number of edges in the network).

References in corpus (14)

• Fast unfolding of communities in large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Community Structure in Jazz
• Mixture models and exploratory analysis in networks
• Detecting network communities by propagating labels under constraints
• Towards real-time community detection in large networks
• Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
• Note on the equivalence of the label propagation method of community detection and a Potts model approach

Cited by in corpus (2)

• Robust network community detection using balanced propagation
• Community structure of complex software systems: Analysis and applications