A Bayesian Approach to Network Modularity

Abstract

We present an efficient, principled, and interpretable technique for inferring module assignments and for identifying the optimal number of modules in a given network. We show how several existing methods for finding modules can be described as variant, special, or limiting cases of our work, and how the method overcomes the resolution limit problem, accurately recovering the true number of modules. Our approach is based on Bayesian methods for model selection which have been used with success for almost a century, implemented using a variational technique developed only in the past decade. We apply the technique to synthetic and real networks and outline how the method naturally allows selection among competing models.

Phys. Rev. Lett. 100, 258701 (2008)

References in corpus (10)

• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Resolution limit in community detection
• Comparing community structure identification
• Statistical Mechanics of Community Detection
• Mixture models and exploratory analysis in networks
• Community Detection as an Inference Problem
• Limited resolution in complex network community detection with Potts model approach
• An Information-Theoretic Approach to Network Modularity

Cited by in corpus (67)

• Community detection in graphs
• Variational Inference: A Review for Statisticians
• Stochastic blockmodels and community structure in networks
• The performance of modularity maximization in practical contexts
• The map equation
• Finding overlapping communities in networks by label propagation
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Statistical physics of inference: Thresholds and algorithms
• Phase transition in the detection of modules in sparse networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• A Classification for Community Discovery Methods in Complex Networks
• Hierarchical relational models for document networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Learning Latent Block Structure in Weighted Networks
• Uncovering latent structure in valued graphs: A variational approach
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Frequentist Consistency of Variational Bayes
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Overlapping stochastic block models with application to the French political blogosphere
• Fuzzy overlapping communities in networks
• Bayesian stochastic blockmodeling
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Spectral methods for the detection of network community structure: a comparative analysis
• Spectral tripartitioning of networks
• Non-parametric Bayesian modeling of complex networks
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Adapting the Stochastic Block Model to Edge-Weighted Networks
• Communities in Networks
• The Stochastic Topic Block Model for the Clustering of Vertices in Networks with Textual Edges
• Accelerating Community Detection by Using K-core Subgraphs
• The random subgraph model for the analysis of an ecclesiastical network in Merovingian Gaul
• Network Structure Inference, A Survey: Motivations, Methods, and Applications
• Detecting modules in dense weighted networks with the Potts method
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Component models for large networks
• Universal efficiency at optimal work with Bayesian statistics
• Discovering Network Structure Beyond Communities
• Using link and content over time for embedding generation in Dynamic Attributed Networks
• Community detection by label propagation with compression of flow
• Model selection and clustering in stochastic block models with the exact integrated complete data likelihood
• Inference for graphs and networks: Extending classical tools to modern data
• Community detection for networks with unipartite and bipartite structure
• Bayesian Degree-Corrected Stochastic Blockmodels for Community Detection
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• A Tractable Fully Bayesian Method for the Stochastic Block Model
• Infinite Multiple Membership Relational Modeling for Complex Networks
• Generalized network community detection
• Criterions for locally dense subgraphs
• Statistical Mechanics of Semi-Supervised Clustering in Sparse Graphs
• The art of community detection
• Generative models for local network community detection
• Local multiresolution order in community detection
• Nonparametric Bayesian models of hierarchical structure in complex networks
• Adjusted chi-square test for degree-corrected block models
• Cell biology: Networks, regulation, pathways
• Active Learning for Hidden Attributes in Networks
• Clustering in networks with the collapsed Stochastic Block Model
• Stability of Maximum likelihood based clustering methods: exploring the backbone of classifications (Who is keeping you in that community?)
• An Efficient Quadratic Penalty Method for a Class of Graph Clustering Problems
• When random initializations help: a study of variational inference for community detection
• Emergence of network communities driven by local rules
• Community detection and tracking on networks from a data fusion perspective
• Persistent homology method to detect block structures in weighted networks
• Sampling Graphlets of Multi-layer Networks: A Restricted Random Walk Approach
• Clustering on the Edge: Learning Structure in Graphs