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 (84)

• Community structure in social and biological 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
• Natural Scales in Geographical Patterns
• Fast algorithm for detecting community structure in networks
• 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
• The diameter of the world wide web
• Functional cartography of complex metabolic networks
• Near linear time algorithm to detect community structures in large-scale networks
• Multilayer Networks
• Benchmark graphs for testing community detection algorithms
• The structure and dynamics of multilayer networks
• Resolution limit in community detection
• Temporal Networks
• Analysis of weighted networks
• Defining and identifying communities in networks
• Community detection algorithms: a comparative analysis
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Link communities reveal multiscale complexity 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
• The performance of modularity maximization in practical contexts
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Synchronization reveals topological scales in complex networks
• Consensus clustering in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Finding local community structure in networks
• Modularity and community detection in bipartite networks
• Social Structure of Facebook Networks
• Spectral redemption: clustering sparse networks
• Mapping change in large networks
• Line Graphs, Link Partitions and Overlapping Communities
• Clustering and Community Detection in Directed Networks: A Survey
• Mixture models and exploratory analysis in networks
• Limits of modularity maximization in community detection
• 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
• Memory in network flows and its effects on spreading dynamics and community detection
• Phase transition in the detection of modules in sparse networks
• An efficient and principled method for detecting communities in networks
• Structure and inference in annotated networks
• Narrow scope for resolution-limit-free community detection
• Uncovering space-independent communities in spatial networks
• Robustness of community structure in networks
• Comparing Community Structure to Characteristics in Online Collegiate Social Networks
• Graph spectra and the detectability of community structure in networks
• A Classification for Community Discovery Methods in Complex Networks
• Distance, dissimilarity index, and network community structure
• Characterizing the community structure of complex networks
• Multiresolution community detection for megascale networks by information-based replica correlations
• 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
• Local resolution-limit-free Potts model for community detection
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Efficiently inferring community structure in bipartite networks
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Clique Graphs and Overlapping Communities
• Network Landscape from a Brownian Particle's Perspective
• 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
• Benchmark model to assess community structure in evolving networks
• Hierarchical multiresolution method to overcome the resolution limit in complex networks
• Community detection in networks with unequal groups
• Compression of Flow Can Reveal Overlapping-Module Organization in Networks
• Detecting communities of triangles in complex networks using spectral optimization
• Finding communities in sparse networks
• Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
• Improving the performance of algorithms to find communities in networks
• Eigenvector dynamics under perturbation of modular networks

Cited by in corpus (224)

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