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

• 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
• 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
• Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
• 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