Robust network community detection using balanced propagation

Abstract

Label propagation has proven to be an extremely fast method for detecting communities in large complex networks. Furthermore, due to its simplicity, it is also currently one of the most commonly adopted algorithms in the literature. Despite various subsequent advances, an important issue of the algorithm has not yet been properly addressed. Random (node) update orders within the algorithm severely hamper its robustness, and consequently also the stability of the identified community structure. We note that an update order can be seen as increasing propagation preferences from certain nodes, and propose a balanced propagation that counteracts for the introduced randomness by utilizing node balancers. We have evaluated the proposed approach on synthetic networks with planted partition, and on several real-world networks with community structure. The results confirm that balanced propagation is significantly more robust than label propagation, when the performance of community detection is even improved. Thus, balanced propagation retains high scalability and algorithmic simplicity of label propagation, but improves on its stability and performance.

References in corpus (33)

• Emergence of scaling in random networks
• 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
• 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 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
• Community Structure in Jazz
• The performance of modularity maximization in practical contexts
• Synchronization reveals topological scales in complex networks
• Finding overlapping communities in networks by label propagation
• Finding Communities in Linear Time: A Physics Approach
• Detecting network communities by propagating labels under constraints
• Robustness of community structure in networks
• Modularity-Maximizing Network Communities via Mathematical Programming
• Towards real-time community detection in large networks
• Advanced modularity-specialized label propagation algorithm for detecting communities in networks
• Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
• Local resolution-limit-free Potts model for community detection
• Limited resolution in complex network community detection with Potts model approach
• A New Comparative Definition of Community and Corresponding Identifying Algorithm
• Note on the equivalence of the label propagation method of community detection and a Potts model approach
• Random field Ising model and community structure in complex networks

Cited by in corpus (39)

• Identifying optimal targets of network attack by belief propagation
• Fast and simple decycling and dismantling of networks
• Forman curvature for complex networks
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Comparative analysis of two discretizations of Ricci curvature for complex networks
• Self-similar scaling of density in complex real-world networks
• Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
• Complex networks vulnerability to module-based attacks
• Machine Learning in Network Centrality Measures: Tutorial and Outlook
• Characterizing the analogy between hyperbolic embedding and community structure of complex networks
• Statistical Mechanics of the Minimum Dominating Set Problem
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• Systematic evaluation of a new combinatorial curvature for complex networks
• Software systems through complex networks science: Review, analysis and applications
• Discrete Ricci curvatures for directed networks
• Efficient Bayesian inference for exponential random graph models by correcting the pseudo-posterior distribution
• Group detection in complex networks: An algorithm and comparison of the state of the art
• Persistent homology of unweighted complex networks via discrete Morse theory
• Enhancing community detection by local structural information
• Learning epidemic threshold in complex networks by Convolutional Neural Network
• Goal-directed graph construction using reinforcement learning
• Label propagation for clustering
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Convexity in complex networks
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• Network depth: identifying median and contours in complex networks
• Emergence of coexisting percolating clusters in networks
• Bilevel Optimization for Traffic Mitigation in Optimal Transport Networks
• Forman-Ricci curvature and Persistent homology of unweighted complex networks
• Laplacian Renormalization Group: An introduction to heterogeneous coarse-graining
• Locating line and node disturbances in networks of diffusively coupled dynamical agents
• Spin-glass model for the C-dismantling problem
• Nonlocal diffusion of variable order on complex networks
• Model-free hidden geometry of complex networks
• Locating fast-varying line disturbances with the frequency mismatch
• Computing Vertex Centrality Measures in Massive Real Networks with a Neural Learning Model
• Systematic comparison of graph embedding methods in practical tasks
• Systematic assessment of the quality of fit of the stochastic block model for empirical networks
• Comparative study of random walks with one-step memory on complex networks