Community detection by label propagation with compression of flow

Abstract

The label propagation algorithm (LPA) has been proved to be a fast and effective method for detecting communities in large complex networks. However, its performance is subject to the non-stable and trivial solutions of the problem. In this paper, we propose a modified label propagation algorithm LPAf to efficiently detect community structures in networks. Instead of the majority voting rule of the basic LPA, LPAf updates the label of a node by considering the compression of a description of random walks on a network. A multi-step greedy agglomerative strategy is employed to enable LPAf to escape the local optimum. Furthermore, an incomplete update condition is also adopted to speed up the convergence. Experimental results on both synthetic and real-world networks confirm the effectiveness of our algorithm.

References in corpus (15)

• Fast unfolding of communities in large networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• 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
• Mixture models and exploratory analysis in networks
• Detecting network communities by propagating labels under constraints
• A Bayesian Approach to Network Modularity
• Towards real-time community detection in large networks
• Limited resolution in complex network community detection with Potts model approach
• 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
• Maximal entropy random walk in community finding