Edge based stochastic block model statistical inference

Abstract

Community detection in graphs often relies on ad hoc algorithms with no clear specification about the node partition they define as the best, which leads to uninterpretable communities. Stochastic block models (SBM) offer a framework to rigorously define communities, and to detect them using statistical inference method to distinguish structure from random fluctuations. In this paper, we introduce an alternative definition of SBM based on edge sampling. We derive from this definition a quality function to statistically infer the node partition used to generate a given graph. We then test it on synthetic graphs, and on the zachary karate club network.

References in corpus (10)

• Community structure in social and biological networks
• Finding community structure in very large networks
• Finding community structure in networks using the eigenvectors of matrices
• Community detection in networks: A user guide
• Modularity from Fluctuations in Random Graphs and Complex Networks
• The entropy of network ensembles
• A tutorial introduction to the minimum description length principle
• Entropy of stochastic blockmodel ensembles
• Bayesian stochastic blockmodeling
• Minimum entropy stochastic block models neglect edge distribution heterogeneity