Community detection in networks: A user guide

Abstract

Community detection in networks is one of the most popular topics of modern network science. Communities, or clusters, are usually groups of vertices having higher probability of being connected to each other than to members of other groups, though other patterns are possible. Identifying communities is an ill-defined problem. There are no universal protocols on the fundamental ingredients, like the definition of community itself, nor on other crucial issues, like the validation of algorithms and the comparison of their performances. This has generated a number of confusions and misconceptions, which undermine the progress in the field. We offer a guided tour through the main aspects of the problem. We also point out strengths and weaknesses of popular methods, and give directions to their use.

43 pages, 29 figures, 2 tables, 202 references. Final version published in Physics Reports

References in corpus (41)

• Modularity and community structure in networks
• Natural Scales in Geographical Patterns
• Uncovering the overlapping community structure of complex networks in nature and society
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• The structure and dynamics of multilayer networks
• Resolution limit in community detection
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Quantifying social group evolution
• Higher-order organization of complex networks
• Finding statistically significant communities in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Consensus clustering in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Modularity and community detection in bipartite networks
• Line Graphs, Link Partitions and Overlapping Communities
• Mixture models and exploratory analysis in networks
• Community detection in networks with positive and negative links
• Analysis of the structure of complex networks at different resolution levels
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Phase transition in the detection of modules in sparse networks
• Narrow scope for resolution-limit-free community detection
• Robustness of community structure in networks
• Graph spectra and the detectability of community structure in networks
• A Classification for Community Discovery Methods in Complex Networks
• Characterizing the community structure of complex networks
• Community detection in networks: Structural communities versus ground truth
• Learning Latent Block Structure in Weighted Networks
• Community Detection as an Inference Problem
• Identification of core-periphery structure in networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Clique Graphs and Overlapping Communities
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Estimating the number of communities in a network
• Motif-based communities in complex networks
• A New Comparative Definition of Community and Corresponding Identifying Algorithm
• Detecting communities of triangles in complex networks using spectral optimization

Cited by in corpus (222)

• Random walks and diffusion on networks
• Social physics
• Robustness and resilience of complex networks
• Community Discovery in Dynamic Networks: a Survey
• What are higher-order networks?
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• A Comprehensive Survey on Community Detection with Deep Learning
• Coevolution spreading in complex networks
• Nestedness in complex networks: Observation, emergence, and implications
• Ranking in evolving complex networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Network Analysis of Particles and Grains
• Evaluating Overfit and Underfit in Models of Network Community Structure
• The many facets of community detection in complex networks
• Network reconstruction and community detection from dynamics
• Persistent homology of time-dependent functional networks constructed from coupled time series
• Inference of hyperedges and overlapping communities in hypergraphs
• Nonparametric weighted stochastic block models
• Structural transition in social networks: The role of homophily
• Modular gateway-ness connectivity and structural core organization in maritime network science
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• Investigating Italian disinformation spreading on Twitter in the context of 2019 European elections
• Defining a historic football team: Using Network Science to analyze Guardiola's F.C. Barcelona
• Centrality in Modular Networks
• Stock market as temporal network
• Efficient method for estimating the number of communities in a network
• Detecting Multiple Communities Using Quantum Annealing on the D-Wave System
• Multistability, intermittency and hybrid transitions in social contagion models on hypergraphs
• Statistical inference of assortative community structures
• From the origin of life to pandemics: Emergent phenomena in complex systems
• Multilink Communities of Multiplex Networks
• Centrality-based identification of important edges in complex networks
• Opinion formation and distribution in a bounded confidence model on various networks
• Local dominance unveils clusters in networks
• Characterizing the Interactions Between Classical and Community-aware Centrality Measures in Complex Networks
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Big Networks: A Survey
• Community structure: A comparative evaluation of community detection methods
• Influence of augmented humans in online interactions during voting events
• A Survey on Theoretical Advances of Community Detection in Networks
• Master equation analysis of mesoscopic localization in contagion dynamics on higher-order networks
• Community detection in networks using graph embeddings
• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Fast consensus clustering in complex networks
• Interaction Graphs for Cascading Failure Analysis in Power Grids: A Survey
• Stability of spontaneous, correlated activity in mouse auditory cortex
• Post-processing partitions to identify domains of modularity optimization
• Graph Coloring with Physics-Inspired Graph Neural Networks
• Revealing In-Block Nestedness: detection and benchmarking
• Network community detection using modularity density measures
• Revealing consensus and dissensus between network partitions
• Exploring the Structure of Misconceptions in the Force Concept Inventory with Modified Module Analysis
• International Trade Network: Country centrality and COVID-19 pandemic
• Multilayer Network Science: from Cells to Societies
• Scholarly migration within Mexico: Analyzing internal migration among researchers using Scopus longitudinal bibliometric data
• Adaptive Modularity Maximization via Edge Weighting Scheme
• Retweet communities reveal the main sources of hate speech
• Reconstructing networks
• Nine Quick Tips for Analyzing Network Data
• Spectral Detection of Simplicial Communities via Hodge Laplacians
• Universality of the stochastic block model
• Layer Communities in Multiplex Networks
• Different approaches to community detection
• Detecting Core-Periphery Structures by Surprise
• The inherent community structure of hyperbolic networks
• Synwalk -- Community Detection via Random Walk Modelling
• Hierarchical benchmark graphs for testing community detection algorithms
• A generalised significance test for individual communities in networks
• Threefold way to the dimension reduction of dynamics on networks: an application to synchronization
• Extreme rainfall propagation within Boreal Summer Intraseasonal Oscillation modulated by Pacific sea surface temperature
• Meta-validation of bipartite network projections
• Community evolution in retweet networks
• Community detection in multiplex networks based on orthogonal nonnegative matrix tri-factorization
• Mixing patterns and individual differences in networks
• Ensemble Clustering for Graphs
• Ensemble Clustering for Graphs: Comparisons and Applications
• Detection of Community Structures in Networks with Nodal Features based on Generative Probabilistic Approach
• Generalized Rich-Club Ordering in Networks
• Identification of Overlapping Communities via Constrained Egonet Tensor Decomposition
• Extracting Complements and Substitutes from Sales Data: A Network Perspective
• A novel metric for community detection
• Exact Blind Community Detection from Signals on Multiple Graphs
• Fast Detection of Community Structures using Graph Traversal in Social Networks
• A Map Equation with Metadata: Varying the Role of Attributes in Community Detection
• Randomizing growing networks with a time-respecting null model
• A system-wide network reconstruction of gene regulation and metabolism in Escherichia coli
• Reconstructing mesoscale network structures
• Identifying multi-scale communities in networks by asymptotic surprise
• Core of communities in bipartite networks
• Spread of infectious disease and social awareness as parasitic contagions on clustered networks
• Algorithmic detectability threshold of the stochastic block model
• Hyperlink communities in higher-order networks
• Interplay between $k$-core and community structure in complex networks
• Detecting mesoscale structures by surprise
• Characterization of fracture in topology-optimized bio-inspired networks
• Multi-attribute community detection in International Trade Network
• Universal productivity patterns in research careers
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• A framework to generate hypergraphs with community structure
• Fast Heuristic Algorithm for Multi-scale Hierarchical Community Detection
• Layer reconstruction and missing link prediction of multilayer network with a Maximum A Posteriori estimation
• Network mutual information measures for graph similarity
• Scalable and Robust Community Detection with Randomized Sketching
• Insights from Graph Theory on the Morphologies of Actomyosin Networks with Multilinkers
• Superradiant phase transition in complex networks
• Community-Aware Graph Signal Processing
• Label propagation for clustering
• Kernel k-Groups via Hartigan's Method
• Micro, Meso, Macro: the effect of triangles on communities in networks
• Community detection based on first passage probabilities
• Growing hyperbolic networks beyond two dimensions: the generalised popularity-similarity optimisation model
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
• Random intersection graphs with communities
• From spatio-temporal data to chronological networks: An application to wildfire analysis
• Measuring similarity in co-occurrence data using ego-networks
• LargeNetVis: Visual Exploration of Large Temporal Networks Based on Community Taxonomies
• Fitting In and Breaking Up: A Nonlinear Version of Coevolving Voter Models
• A Study on Modularity Density Maximization: Column Generation Acceleration and Computational Complexity Analysis
• Modular decomposition of protein structure using community detection
• Total variation based community detection using a nonlinear optimization approach
• KCoreMotif: An Efficient Graph Clustering Algorithm for Large Networks by Exploiting k-core Decomposition and Motifs
• Maximally modular structure of growing hyperbolic networks
• Subdivisions and Crossroads: Identifying Hidden Community Structures in a Data Archive's Citation Network
• Robustness modularity in complex networks
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Agent-Q: Fine-Tuning Large Language Models for Quantum Circuit Generation and Optimization
• Comparing Graph Clusterings: Set partition measures vs. Graph-aware measures
• State aggregations in Markov chains and block models of networks
• Robustness of community structure under edge addition
• Modularity in Multilayer Networks using Redundancy-based Resolution and Projection-based Inter-Layer Coupling
• Community detectability and structural balance dynamics in signed networks
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Emergent entanglement structures and self-similarity in quantum spin chains
• Inference of Edge Correlations in Multilayer Networks
• Multi-scale Laplacian community detection in heterogeneous networks
• Normalized mutual information is a biased measure for classification and community detection
• Community structure in co-inventor networks affects time to first citation for patents
• Random-Graph Models and Characterization of Granular Networks
• Motif-Based Spectral Clustering of Weighted Directed Networks
• Voter model on networks partitioned into two cliques of arbitrary sizes
• Regional economic integration via detection of circular flow in international value-added network
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Generalized Markov stability of network communities
• A useful criterion on studying consistent estimation in community detection
• Spectral partitioning of time-varying networks with unobserved edges
• Distributed Graph Clustering using Modularity and Map Equation
• Structured networks and coarse-grained descriptions: a dynamical perspective
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• Belief propagation on networks with cliques and chordless cycles
• Signed graphs in data sciences via communicability geometry
• Entrograms and coarse graining of dynamics on complex networks
• Iterative embedding and reweighting of complex networks reveals community structure
• The politics of physicists social models
• Term-community-based topic detection with variable resolution
• Community detection for directed networks revisited using bimodularity
• Community Detection with the Map Equation and Infomap: Theory and Applications
• Greedy routing optimisation in hyperbolic networks
• Estimating the number of communities in weighted networks
• Influence Maximization: Divide and Conquer
• Bayesian Learning of Graph Substructures
• Identifying bias in cluster quality metrics
• Stochastic Block Models are a Discrete Surface Tension
• Importance of initial conditions in the polarization of complex networks
• Predicting Nodal Influence via Local Iterative Metrics
• Graph clustering with Boltzmann machines
• Community Structure Characterization
• Community Detection in networks by Dynamical Optimal Transport Formulation
• Multiplicity and Diversity: Analyzing the Optimal Solution Space of the Correlation Clustering Problem on Complete Signed Graphs
• Community Detection Using Revised Medoid-Shift Based on KNN
• Towards a generalization of information theory for hierarchical partitions
• Temporal origin of nestedness in interaction networks
• Uncovering Complex Overlapping Pattern of Communities in Large-scale Social Networks
• Community Detection in Networks: A Rough Sets and Consensus Clustering Approach
• Detection of Functional Communities in Networks of Randomly Coupled Oscillators Using the Dynamic-Mode Decomposition
• Consistency between ordering and clustering methods for graphs
• Delay propagation patterns in Japan's domestic air transport network
• Navigating differential structures in complex networks
• Efficient Personalized Community Detection via Genetic Evolution
• Detecting User Community in Sparse Domain via Cross-Graph Pairwise Learning
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
• Optimal timescale for community detection in growing networks
• Community detection in hypergraphs through hyperedge percolation
• Minimum entropy stochastic block models neglect edge distribution heterogeneity
• Connectivity and Community Structure of Online and Register-based Social Networks
• Topological aspects of the multi-language phases of the Naming Game on community-based networks
• Spatial Social Network (SSN) Hot Spot Detection: Scan Methods for Non-Planar Networks
• Hierarchical clustering of bipartite data sets based on the statistical significance of coincidences
• Single-trajectory map equation
• On Finding the Community with Maximum Persistence Probability
• The parameterised complexity of computing the maximum modularity of a graph
• Introduction to Graph Neural Networks for Machine Learning Engineers
• An Efficient Quadratic Penalty Method for a Class of Graph Clustering Problems
• Effective Visualization and Analysis of Recommender Systems
• Edge based stochastic block model statistical inference
• Inference and Visualization of Community Structure in Attributed Hypergraphs Using Mixed-Membership Stochastic Block Models
• State Transfer in Noisy Modular Quantum Networks
• Sentiment-Driven Community Detection in a Network of Perfume Preferences
• Scalable Community Detection Using Quantum Hamiltonian Descent and QUBO Formulation
• Complex networks approach to curriculum analysis and subject integration: a case study on Physics and Mathematics
• The way to uncover community structure with core and diversity
• Universality of political corruption networks
• Optimising SARS-CoV-2 pooled testing strategies on social networks for low-resource settings
• Finding community structure using the ordered random graph model
• Machine Learning Analysis of the Impact of Increasing the Minimum Wage on Income Inequality in Spain from 2001 to 2021
• Anomaly, reciprocity, and community detection in networks
• Can x2vec Save Lives? Integrating Graph and Language Embeddings for Automatic Mental Health Classification
• Bayesian Modeling of Random Walker for Community Detection in Networks
• A new generalization of edge overlap to weighted networks
• Overlapping community detection in weighted networks
• Correlations of network trajectories
• Computing well-balanced spanning trees of unweighted networks
• A High-Performance Evolutionary Multiobjective Community Detection Algorithm
• Similarity networks of ordinal-pattern transitions classify falling paper trajectories
• Modularity of regular and treelike graphs
• Modeling Node Exposure for Community Detection in Networks
• Partitioning networks into clusters of synchronized nodes via the message-passing algorithm: an unbiased scalable approach
• Mapping Inter-City Trade Networks to Maximum Entropy Models using Electronic Invoice Data
• Nonconvex landscapes for ${\mathbf{Z}}_2$ synchronization and graph clustering are benign near exact recovery thresholds
• The impact of partially missing communities~on the reliability of centrality measures
• Discriminative community detection for multiplex networks
• Beyond One Solution: The Case for a Comprehensive Exploration of Solution Space in Community Detection
• Absence of a resolution limit in in-block nestedness