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 (32)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Lethality and centrality in protein networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• The diameter of the world wide web
• The large-scale organization of metabolic networks
• 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
• Defining and identifying communities in networks
• Community detection algorithms: a comparative analysis
• Hierarchical Organization in Complex Networks
• The Dynamics of Viral Marketing
• Self-similar community structure in organisations
• Community Structure in Jazz
• The performance of modularity maximization in practical contexts
• Mixture models and exploratory analysis in networks
• Detecting Network Communities: a new systematic and efficient algorithm
• Detecting network communities by propagating labels under constraints
• Towards real-time community detection in large networks
• Advanced modularity-specialized label propagation algorithm for detecting communities in networks
• Local resolution-limit-free Potts model for community detection
• 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
• Protein-Interaction-Networks: More than mere modules

Cited by in corpus (15)

• Robust network community detection using balanced propagation
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Self-similar scaling of density in complex real-world networks
• Community structure of complex software systems: Analysis and applications
• Large network community detection by fast label propagation
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• Software systems through complex networks science: Review, analysis and applications
• Group detection in complex networks: An algorithm and comparison of the state of the art
• Sampling promotes community structure in social and information networks
• Label propagation for clustering
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• Generalized network community detection
• Role-based Label Propagation Algorithm for Community Detection
• Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm
• Deep learning tackles single-cell analysis A survey of deep learning for scRNA-seq analysis