Community Detection as an Inference Problem

Abstract

We express community detection as an inference problem of determining the most likely arrangement of communities. We then apply belief propagation and mean-field theory to this problem, and show that this leads to fast, accurate algorithms for community detection.

4 pages, 2 figures

References in corpus (10)

• Finding and evaluating community structure in networks
• Fast algorithm for detecting community structure in networks
• Cooperative Game Theory Approaches for Network Partitioning
• Comparing community structure identification
• Theory of Phase Ordering Kinetics
• Statistical Mechanics of Community Detection
• Self-similar community structure in organisations
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Detecting fuzzy community structures in complex networks with a Potts model
• Subnetwork hierarchies of biochemical pathways

Cited by in corpus (71)

• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Near linear time algorithm to detect community structures in large-scale networks
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• Modularity and community detection in bipartite networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Mixture models and exploratory analysis in networks
• Statistical physics of inference: Thresholds and algorithms
• Phase transition in the detection of modules in sparse networks
• Robustness of community structure in networks
• A Bayesian Approach to Network Modularity
• A Classification for Community Discovery Methods in Complex Networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Multiresolution community detection for megascale networks by information-based replica correlations
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Adaptive Graph Encoder for Attributed Graph Embedding
• Local resolution-limit-free Potts model for community detection
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Structural Inference of Hierarchies in Networks
• Improved community structure detection using a modified fine tuning strategy
• 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
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• A Survey on Theoretical Advances of Community Detection in Networks
• Communities in Networks
• Attributed Graph Clustering: A Deep Attentional Embedding Approach
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Detection of node group membership in networks with group overlap
• Community Detection in Complex Networks by Dynamical Simplex Evolution
• A Replica Inference Approach to Unsupervised Multi-Scale Image Segmentation
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Significant communities in large sparse networks
• Spectral analysis of deformed random networks
• Detecting modules in dense weighted networks with the Potts method
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Multilayer Networks for Text Analysis with Multiple Data Types
• Path-dependent connectivity, not modularity, consistently predicts controllability of structural brain networks
• Community detection based on first passage probabilities
• The stability to instability transition in the structure of large scale networks
• Global disorder transition in the community structure of large-q Potts systems
• Resampling effects on significance analysis of network clustering and ranking
• Multiple phases in modularity-based community detection
• A Tractable Fully Bayesian Method for the Stochastic Block Model
• A Survey of Community Search Over Big Graphs
• Discovering Social Circles in Ego Networks
• Criterions for locally dense subgraphs
• Entrograms and coarse graining of dynamics on complex networks
• Statistical Mechanics of Semi-Supervised Clustering in Sparse Graphs
• Unsupervised Deep Manifold Attributed Graph Embedding
• Local multiresolution order in community detection
• Active Community Detection in Massive Graphs
• Quartic quantum speedups for planted inference
• Minimum entropy stochastic block models neglect edge distribution heterogeneity
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
• Stability of Maximum likelihood based clustering methods: exploring the backbone of classifications (Who is keeping you in that community?)
• Community Detection Clustering via Gumbel Softmax
• Community Detection Algorithm Combining Stochastic Block Model and Attribute Data Clustering
• Smoothness Sensor: Adaptive Smoothness-Transition Graph Convolutions for Attributed Graph Clustering
• Spectral community detection in heterogeneous large networks
• Community detection and tracking on networks from a data fusion perspective
• Thermodynamics of the Minimum Description Length on Community Detection
• Retrieving information from a noisy "knowledge network"
• Multi-dimensional Parametric Mincuts for Constrained MAP Inference
• Community Structure and Topical Differentiation in European RTD Collaborations
• The Limits of Inference in Complex Systems: When Stochastic Models Become Indistinguishable
• Error-Correcting Decoders for Communities in Networks
• The Function of Communities in Protein Interaction Networks at Multiple Scales
• Inverse Graph Identification: Can We Identify Node Labels Given Graph Labels?