On the relationship between Gaussian stochastic blockmodels and label propagation algorithms

Abstract

The problem of community detection receives great attention in recent years. Many methods have been proposed to discover communities in networks. In this paper, we propose a Gaussian stochastic blockmodel that uses Gaussian distributions to fit weight of edges in networks for non-overlapping community detection. The maximum likelihood estimation of this model has the same objective function as general label propagation with node preference. The node preference of a specific vertex turns out to be a value proportional to the intra-community eigenvector centrality (the corresponding entry in principal eigenvector of the adjacency matrix of the subgraph inside that vertex's community) under maximum likelihood estimation. Additionally, the maximum likelihood estimation of a constrained version of our model is highly related to another extension of label propagation algorithm, namely, the label propagation algorithm under constraint. Experiments show that the proposed Gaussian stochastic blockmodel performs well on various benchmark networks.

22 pages, 17 figures

References in corpus (16)

• Cooperative Game Theory Approaches for Network Partitioning
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Stochastic blockmodels and community structure in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Narrow scope for resolution-limit-free community detection
• Detecting network communities by propagating labels under constraints
• Modularity-Maximizing Network Communities via Mathematical Programming
• A Bayesian Approach to Network Modularity
• Towards real-time community detection in large networks
• Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
• Robust network community detection using balanced propagation
• 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