The many facets of community detection in complex networks

Abstract

Community detection, the decomposition of a graph into essential building blocks, has been a core research topic in network science over the past years. Since a precise notion of what constitutes a community has remained evasive, community detection algorithms have often been compared on benchmark graphs with a particular form of assortative community structure and classified based on the mathematical techniques they employ. However, this comparison can be misleading because apparent similarities in their mathematical machinery can disguise different goals and reasons for why we want to employ community detection in the first place. Here we provide a focused review of these different motivations that underpin community detection. This problem-driven classification is useful in applied network science, where it is important to select an appropriate algorithm for the given purpose. Moreover, highlighting the different facets of community detection also delineates the many lines of research and points out open directions and avenues for future research.

arXiv comment8 Pages, 1 Figure

References in corpus (37)

• 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 networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• The structure and dynamics of multilayer networks
• Resolution limit in community detection
• Temporal Networks
• Stochastic blockmodels and community structure in networks
• Link communities reveal multiscale complexity in networks
• Community detection in networks: A user guide
• Higher-order organization of complex networks
• The performance of modularity maximization in practical contexts
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Synchronization reveals topological scales in complex networks
• Spectral redemption: clustering sparse networks
• Clustering and Community Detection in Directed Networks: A Survey
• Limits of modularity maximization in community detection
• The ground truth about metadata and community detection in networks
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Laplacian Dynamics and Multiscale Modular Structure in Networks
• Memory in network flows and its effects on spreading dynamics and community detection
• Phase transition in the detection of modules in sparse networks
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Fundamental structures of dynamic social networks
• Community Detection via Maximization of Modularity and Its Variants
• A Classification for Community Discovery Methods in Complex Networks
• Parsimonious module inference in large networks
• Learning Latent Block Structure in Weighted Networks
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Phase transition in the economically modeled growth of a cellular nervous system
• Flow-based network analysis of the Caenorhabditis elegans connectome
• The stability of a graph partition: A dynamics-based framework for community detection
• Using higher-order Markov models to reveal flow-based communities in networks

Cited by in corpus (34)

• Social physics
• What are higher-order networks?
• A Review of Stochastic Block Models and Extensions for Graph Clustering
• Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian
• Simplicial complexes and complex systems
• Multiscale mixing patterns in networks
• Multilink Communities of Multiplex Networks
• Community structure: A comparative evaluation of community detection methods
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Multiscale dynamical embeddings of complex networks
• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Post-processing partitions to identify domains of modularity optimization
• Network community detection using modularity density measures
• Community detection using boundary nodes in complex networks
• Universality of the stochastic block model
• From Free Text to Clusters of Content in Health Records: An Unsupervised Graph Partitioning Approach
• Embedding-based Silhouette Community Detection
• Fragmentation, integration and macroprudential surveillance of the US financial industry: Insights from network science
• Label propagation for clustering
• Reduced network extremal ensemble learning (RenEEL) scheme for community detection in complex networks
• PyGenStability: Multiscale community detection with generalized Markov Stability
• State aggregations in Markov chains and block models of networks
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Convex skeletons of complex networks
• Spectral partitioning of time-varying networks with unobserved edges
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Generalized Markov stability of network communities
• Structured networks and coarse-grained descriptions: a dynamical perspective
• Engineering Structural Robustness in Power Grid Networks Susceptible to Coherent Swing Instability
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
• Structural and temporal heterogeneities on networks
• Detectability of hierarchical communities in networks
• Mesoscopic architecture enhances communication across the Macaque connectome revealing structure-function correspondence in the brain
• The efficiency of community detection by most similar node pairs