Community detection in networks: Modularity optimization and maximum likelihood are equivalent

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.

8 pages, 1 figure, 1 table

References in corpus (14)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• 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 Structure in Jazz
• Analysis of the structure of complex networks at different resolution levels
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Phase transition in the detection of modules in sparse networks
• A Classification for Community Discovery Methods in Complex Networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity

Cited by in corpus (78)

• 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
• A Review of Modularization Techniques in Artificial Neural Networks
• Statistical inference of assortative community structures
• 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
• Geometric Multiscale Community Detection: Markov Stability and Vector Partitioning
• 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
• Spectral Algorithms for Community Detection in Directed Networks
• 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
• Mapping the spectrum of 3D communities in human chromosome conformation capture data
• State aggregations in Markov chains and block models of networks
• Finite size analysis of the detectability limit of the stochastic block model
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• 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
• Spectral partitioning in equitable graphs
• Multiscale Evolutionary Perturbation Attack on Community Detection
• The Hyperspherical Geometry of Community Detection: Modularity as a Distance
• Ising-Based Louvain Method: Clustering Large Graphs with Specialized Hardware
• Term-community-based topic detection with variable resolution
• Unsupervised Machine Learning of Open Source Russian Twitter Data Reveals Global Scope and Operational Characteristics
• Integrated Information Decomposition Unveils Major Structural Traits of $In$ $Silico$ and $In$ $Vitro$ Neuronal Networks
• Stochastic Block Models are a Discrete Surface Tension
• Link Prediction Accuracy on Real-World Networks Under Non-Uniform Missing Edge Patterns
• Importance of initial conditions in the polarization of complex networks
• The Asymptotic Distribution of Modularity in Weighted Signed Networks
• Statistical Evaluation of Spectral Methods for Anomaly Detection in Networks
• The Role of Network Analysis in Industrial and Applied Mathematics
• Community Detection on Networks with Ricci Flow
• Informative core identification in complex networks
• A Synthetic Network Generator for Covert Network Analytics
• The Atlas for the Aspiring Network Scientist
• Navigating differential structures in complex networks
• Optimal timescale for community detection in growing networks
• A General Definition of Network Communities and the Corresponding Detection Algorithm
• On the Consistency of the Likelihood Maximization Vertex Nomination Scheme: Bridging the Gap Between Maximum Likelihood Estimation and Graph Matching
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
• Model-based clustering in simple hypergraphs through a stochastic blockmodel
• NISQ-ready community detection based on separation-node identification
• Community Detection in the Stochastic Block Model by Mixed Integer Programming
• Exploring 3D community inconsistency in human chromosome contact networks
• A Social Network Analysis of Articles on Social Network Analysis
• Optimizing Edge Sets in Networks to Produce Ground Truth Communities Based on Modularity
• Uncovering the structure of the French media ecosystem
• Node Embedding via Word Embedding for Network Community Discovery
• Refinement for community structures of bipartite networks
• Thermodynamics of the Minimum Description Length on Community Detection
• Spectral community detection in heterogeneous large networks
• Almost exact recovery in noisy semi-supervised learning
• Community detection over a heterogeneous population of non-aligned networks
• Learning Resolution Parameters for Graph Clustering
• MGA: Momentum Gradient Attack on Network
• Non-backtracking walks reveal compartments in sparse chromatin interaction networks
• An Adaptive Networks Model to Simulate Consensus Formation Driven by Social Identity Recognition