Community detection in networks: Modularity optimization and maximum likelihood are equivalent
arXiv:1606.02319 · doi:10.1103/PhysRevE.94.052315
Abstract
We demonstrate an exact equivalence between two widely used methods of community detection in networks, the method of modularity maximization in its generalized form which incorporates a resolution parameter controlling the size of the communities discovered, and the method of maximum likelihood applied to the special case of the stochastic block model known as the planted partition model, in which all communities in a network are assumed to have statistically similar properties. Among other things, this equivalence provides a mathematically principled derivation of the modularity function, clarifies the conditions and assumptions of its use, and gives an explicit formula for the optimal value of the resolution parameter.
arXiv comment8 pages, 1 figure, 1 table
References in corpus (31)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Fast algorithm for detecting community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- Random graphs with arbitrary degree distributions and their applications
- Resolution limit in community detection
- Statistical Mechanics of Community Detection
- Stochastic blockmodels and community structure in networks
- Community detection in networks: A user guide
- Community detection in complex networks using Extremal Optimization
- Community Structure in Jazz
- The performance of modularity maximization in practical contexts
- Scale-free topology of e-mail networks
- Modularity from Fluctuations in Random Graphs and Complex Networks
- Analysis of the structure of complex networks at different resolution levels
- Spectral methods for network community detection and graph partitioning
- Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
- Laplacian Dynamics and Multiscale Modular Structure in Networks
- Phase transition in the detection of modules in sparse networks
- A Classification for Community Discovery Methods in Complex Networks
- Consistency of community detection in networks under degree-corrected stochastic block models
- Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
- Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
- Estimating the number of communities in a network
- Community detection and graph partitioning
- Model Selection for Degree-corrected Block Models
- Optimal map of the modular structure of complex networks
Cited by in corpus (79)
- Random walks and diffusion on networks
- Social physics
- A Review of Stochastic Block Models and Extensions for Graph Clustering
- On community structure in complex networks: challenges and opportunities
- Evaluating Overfit and Underfit in Models of Network Community Structure
- The many facets of community detection in complex networks
- Clustering via Hypergraph Modularity
- Finding multiple core-periphery pairs in networks
- Statistical inference of assortative community structures
- A Review of Modularization Techniques in Artificial Neural Networks
- Principled approach to the selection of the embedding dimension of networks
- A statistical inference approach to structural reconstruction of complex networks from binary time series
- Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
- Characterizing the analogy between hyperbolic embedding and community structure of complex networks
- Classifying Patents Based on their Semantic Content
- Hierarchical Graph Clustering using Node Pair Sampling
- Universality of the stochastic block model
- Different approaches to community detection
- Hierarchical community structure in networks
- Versatility of nodal affiliation to communities
- The emergent integrated network structure of scientific research
- Mapping flows on sparse networks with missing links
- Community detection and reciprocity in networks by jointly modeling pairs of edges
- Spectral Algorithms for Community Detection in Directed Networks
- Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
- Asymptotic resolution bounds of generalized modularity and multi-scale community detection
- Geometric Multiscale Community Detection: Markov Stability and Vector Partitioning
- Regularized Stochastic Block Model for robust community detection in complex networks
- StaTIX - Statistical Type Inference on Linked Data
- Null Models and Community Detection in Multi-Layer Networks
- Multiresolution Consensus Clustering in Networks
- Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
- State aggregations in Markov chains and block models of networks
- Mapping the spectrum of 3D communities in human chromosome conformation capture data
- Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
- Finite size analysis of the detectability limit of the stochastic block model
- Group polarization, influence, and domination in online interaction networks: A case study of the 2022 Brazilian elections
- Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
- Generalized Markov stability of network communities
- Multiscale Evolutionary Perturbation Attack on Community Detection
- Spectral partitioning in equitable graphs
- The Hyperspherical Geometry of Community Detection: Modularity as a Distance
- The Role of Network Analysis in Industrial and Applied Mathematics
- Community Detection on Networks with Ricci Flow
- The Asymptotic Distribution of Modularity in Weighted Signed Networks
- Link Prediction Accuracy on Real-World Networks Under Non-Uniform Missing Edge Patterns
- Integrated Information Decomposition Unveils Major Structural Traits of and Neuronal Networks
- Term-community-based topic detection with variable resolution
- Ising-Based Louvain Method: Clustering Large Graphs with Specialized Hardware
- Unsupervised Machine Learning of Open Source Russian Twitter Data Reveals Global Scope and Operational Characteristics
- Stochastic Block Models are a Discrete Surface Tension
- Importance of initial conditions in the polarization of complex networks
- Statistical Evaluation of Spectral Methods for Anomaly Detection in Networks
- A Synthetic Network Generator for Covert Network Analytics
- Informative core identification in complex networks
- A General Definition of Network Communities and the Corresponding Detection Algorithm
- NISQ-ready community detection based on separation-node identification
- Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
- On the Consistency of the Likelihood Maximization Vertex Nomination Scheme: Bridging the Gap Between Maximum Likelihood Estimation and Graph Matching
- Navigating differential structures in complex networks
- The Atlas for the Aspiring Network Scientist
- Optimal timescale for community detection in growing networks
- Model-based clustering in simple hypergraphs through a stochastic blockmodel
- Community Detection in the Stochastic Block Model by Mixed Integer Programming
- Uncovering the structure of the French media ecosystem
- A Social Network Analysis of Articles on Social Network Analysis
- Exploring 3D community inconsistency in human chromosome contact networks
- Optimizing Edge Sets in Networks to Produce Ground Truth Communities Based on Modularity
- Node Embedding via Word Embedding for Network Community Discovery
- Almost exact recovery in noisy semi-supervised learning
- Thermodynamics of the Minimum Description Length on Community Detection
- Spectral community detection in heterogeneous large networks
- Refinement for community structures of bipartite networks
- An Adaptive Networks Model to Simulate Consensus Formation Driven by Social Identity Recognition
- Learning Resolution Parameters for Graph Clustering
- On Equivalence of Likelihood Maximization of Stochastic Block Model and Constrained Nonnegative Matrix Factorization
- Community detection over a heterogeneous population of non-aligned networks
- MGA: Momentum Gradient Attack on Network
- Non-backtracking walks reveal compartments in sparse chromatin interaction networks