Community detection algorithms: a comparative analysis

Abstract

Uncovering the community structure exhibited by real networks is a crucial step towards an understanding of complex systems that goes beyond the local organization of their constituents. Many algorithms have been proposed so far, but none of them has been subjected to strict tests to evaluate their performance. Most of the sporadic tests performed so far involved small networks with known community structure and/or artificial graphs with a simplified structure, which is very uncommon in real systems. Here we test several methods against a recently introduced class of benchmark graphs, with heterogeneous distributions of degree and community size. The methods are also tested against the benchmark by Girvan and Newman and on random graphs. As a result of our analysis, three recent algorithms introduced by Rosvall and Bergstrom, Blondel et al. and Ronhovde and Nussinov, respectively, have an excellent performance, with the additional advantage of low computational complexity, which enables one to analyze large systems.

12 pages, 8 figures. The software to compute the values of our general normalized mutual information is available at http://santo.fortunato.googlepages.com/inthepress2

References in corpus (18)

• Fast unfolding of communities in large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Statistical Mechanics of Community Detection
• Detecting the overlapping and hierarchical community structure of complex networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• An information-theoretic framework for resolving community structure in complex networks
• Line Graphs, Link Partitions and Overlapping Communities
• Mixture models and exploratory analysis in networks
• Identifying "communities" within energy landscapes
• When are networks truly modular?
• Partitioning and modularity of graphs with arbitrary degree distribution
• (Un)detectable cluster structure in sparse networks
• Detection of node group membership in networks with group overlap
• Inversion method for content-based networks

Cited by in corpus (291)

• Community detection in graphs
• From Louvain to Leiden: guaranteeing well-connected communities
• Community detection in networks: A user guide
• Finding statistically significant communities in networks
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• The role of gender in scholarly authorship
• Consensus clustering in complex networks
• A Comprehensive Survey on Graph Anomaly Detection with Deep Learning
• Finding overlapping communities in networks by label propagation
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Hierarchical modularity in human brain functional networks
• Social physics
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• Limits of modularity maximization in community detection
• The ground truth about metadata and community detection in networks
• 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
• An efficient and principled method for detecting communities in networks
• Narrow scope for resolution-limit-free community detection
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• A Classification for Community Discovery Methods in Complex Networks
• Men Set Their Own Cites High: Gender and Self-citation across Fields and over Time
• Detecting highly overlapping community structure by greedy clique expansion
• Characterizing the community structure of complex networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Nestedness in complex networks: Observation, emergence, and implications
• Evolution of worldwide stock markets, correlation structure and correlation based graphs
• Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale
• A mechanistic model of connector hubs, modularity, and cognition
• Hydrodynamic provinces and oceanic connectivity from a transport network help designing marine reserves
• Identifying the Community Structure of the International-Trade Multi Network
• A General Optimization Technique for High Quality Community Detection in Complex Networks
• Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
• Robust network community detection using balanced propagation
• 20 years of network community detection
• Infomap Bioregions: Interactive mapping of biogeographical regions from species distributions
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Significant Scales in Community Structure
• Line Graphs of Weighted Networks for Overlapping Communities
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Stochastic Block Models and Reconstruction
• Faster unfolding of communities: speeding up the Louvain algorithm
• Deciphering Network Community Structure by Surprise
• Detecting communities using asymptotical Surprise
• Flow networks: A characterization of geophysical fluid transport
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Empirical Comparison of Algorithms for Network Community Detection
• Spectral methods for the detection of network community structure: a comparative analysis
• Centrality Measures for Networks with Community Structure
• Self-similar scaling of density in complex real-world networks
• Ranking and clustering of nodes in networks with smart teleportation
• Surprise maximization reveals the community structure of complex networks
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• Comparing and modeling land use organization in cities
• Z-score-based modularity for community detection in networks
• Overlapping Community Detection in Complex Networks using Symmetric Binary Matrix Factorization
• Efficient method for estimating the number of communities in a network
• Identification of clusters of investors from their real trading activity in a financial market
• Identifying robust communities and multi-community nodes by combining top-down and bottom-up approaches to clustering
• Evaluating accuracy of community detection using the relative normalized mutual information
• Community structure of complex software systems: Analysis and applications
• Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
• Brain Modularity Mediates the Relation between Task Complexity and Performance
• The Community Structure of the Global Corporate Network
• Estimating the resolution limit of the map equation in community detection
• Exploring the limits of community detection strategies in complex networks
• Evolution of correlation structure of industrial indices of US equity markets
• Qualitative Comparison of Community Detection Algorithms
• Community Structure Detection in Complex Networks with Partial Background Information
• Community Structure in the United Nations General Assembly
• Characterizing the Interactions Between Classical and Community-aware Centrality Measures in Complex Networks
• Will the US Economy Recover in 2010? A Minimal Spanning Tree Study
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Community characterization of heterogeneous complex systems
• Efficient community detection of network flows for varying Markov times and bipartite networks
• Data Mining on Social Interaction Networks
• Deep Community Detection
• The role of endogenous and exogenous mechanisms in the formation of R&D networks
• Topologically biased random walk with application for community finding in networks
• Potts model based on a Markov process computation solves the community structure problem effectively
• Bloggers Behavior and Emergent Communities in Blog Space
• Multi-scale Modularity in Complex Networks
• Characterization of citizens using word2vec and latent topic analysis in a large set of tweets
• Community detection in networks using graph embeddings
• Towards realistic artificial benchmark for community detection algorithms evaluation
• Hierarchical communities in the walnut structure of the Japanese production network
• Fast consensus clustering in complex networks
• Community Detection with Side Information: Exact Recovery under the Stochastic Block Model
• Link-Prediction Enhanced Consensus Clustering for Complex Networks
• Detecting communities of triangles in complex networks using spectral optimization
• DEMON: a Local-First Discovery Method for Overlapping Communities
• Mesoscopic analysis of online social networks - The role of negative ties
• A testing based extraction algorithm for identifying significant communities in networks
• Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits
• Communities and beyond: mesoscopic analysis of a large social network with complementary methods
• Multi-scale Anomaly Detection on Attributed Networks
• Significant communities in large sparse networks
• A paradox in community detection
• Community-based Immunization Strategies for Epidemic Control
• How higher goals are constructed and collapse under stress: a hierarchical Bayesian control systems perspective
• From Free Text to Clusters of Content in Health Records: An Unsupervised Graph Partitioning Approach
• Maximal entropy random walk in community finding
• Modularity functions maximization with nonnegative relaxation facilitates community detection in networks
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Contagion processes on the static and activity driven coupling networks
• Overlapping Community Discovery Methods: A Survey
• Synwalk -- Community Detection via Random Walk Modelling
• OLCPM: An Online Framework for Detecting Overlapping Communities in Dynamic Social Networks
• Embedding-based Silhouette Community Detection
• Community evolution in retweet networks
• DMCS : Density Modularity based Community Search
• Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
• Community Detection in Networks using Graph Distance
• A Unified Method of Detecting Core-Periphery Structure and Community Structure in Networks
• Improving the performance of algorithms to find communities in networks
• Group detection in complex networks: An algorithm and comparison of the state of the art
• Ensemble Clustering for Graphs
• Identifying overlapping communities in social networks using multi-scale local information expansion
• Effective and Scalable Clustering on Massive Attributed Graphs
• Explicitly Linking Regional Activation and Function Connectivity: Community Structure of Weighted Networks with Continuous Annotation
• A linear streaming algorithm for community detection in very large networks
• Cell assembly dynamics of sparsely-connected inhibitory networks: a simple model for the collective activity of striatal projection neurons
• A General Framework for Complex Network-Based Image Segmentation
• Extracting Complements and Substitutes from Sales Data: A Network Perspective
• Random Spatial Network Models with Core-Periphery Structure
• Community detection in networks via nonlinear modularity eigenvectors
• Community structure in the World Trade Network based on communicability distances
• Bow-tie structure and community identification of global supply chain network
• Mapping flows on sparse networks with missing links
• Closed benchmarks for network community structure characterization
• Ant Colony Optimization with a New Random Walk Model for Community Detection in Complex Networks
• Stock portfolio structure of individual investors infers future trading behavior
• Spatial correlations in attribute communities
• DeFiNe: an optimisation-based method for robust disentangling of filamentous networks
• Detecting mesoscale structures by surprise
• Discovering link communities in complex networks by exploiting link dynamics
• Universal productivity patterns in research careers
• Power-law relations in random networks with communities
• Detecting Communities in Tripartite Hypergraphs
• Pattern-detection in the global automotive industry: a manufacturer-supplier-product network analysis
• Comparative analysis on the selection of number of clusters in community detection
• An Ant-Based Algorithm with Local Optimization for Community Detection in Large-Scale Networks
• The stability to instability transition in the structure of large scale networks
• A data-driven framework for dimensionality reduction and causal inference in climate fields
• Maps of sparse Markov chains efficiently reveal community structure in network flows with memory
• Global disorder transition in the community structure of large-q Potts systems
• Perception, Prestige and PageRank
• A Method for Group Extraction and Analysis in Multilayer Social Networks
• Cycle Analysis of Directed Acyclic Graphs
• Total variation based community detection using a nonlinear optimization approach
• Generalization of Clustering Agreements and Distances for Overlapping Clusters and Network Communities
• Efficiently Detecting Overlapping Communities through Seeding and Semi-Supervised Learning
• Comparison of Cross-Validation Methods for Stochastic Block Models
• Distress propagation on production networks: Coarse-graining and modularity of linkages
• Multiple bipolar fuzzy measures: an application to community detection problems for networks with additional information
• Subdivisions and Crossroads: Identifying Hidden Community Structures in a Data Archive's Citation Network
• Semi-supervised Graph Neural Networks for Pileup Noise Removal
• User-Relatedness and Community Structure in Social Interaction Networks
• Community detection based on "clumpiness" matrix in complex networks
• The Impact of Random Models on Clustering Similarity
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Fragmenting networks by targeting collective influencers at a mesoscopic level
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• Generating global network structures by triad types
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Convex skeletons of complex networks
• Ordered community structure in networks
• Hierarchical community detection by recursive partitioning
• Modules in the metabolic network of E.coli with regulatory interactions
• Comparing Graph Clusterings: Set partition measures vs. Graph-aware measures
• Robustness of community structure under edge addition
• Detecting network communities beyond assortativity-related attributes
• Time-sync Video Tag Extraction Using Semantic Association Graph
• POISED: Spotting Twitter Spam Off the Beaten Paths
• Inferring propagation paths for sparsely observed perturbations on complex networks
• Online Tensor Methods for Learning Latent Variable Models
• Multi-scale Laplacian community detection in heterogeneous networks
• Discovering Social Circles in Ego Networks
• Normalized mutual information is a biased measure for classification and community detection
• Decoding communities in networks
• Generalized network community detection
• Scalable Spectral Algorithms for Community Detection in Directed Networks
• Non-overlapping community detection
• Topological Feature Based Classification
• DUEF-GA: Data Utility and Privacy Evaluation Framework for Graph Anonymization
• The Impact of Social Segregation on Human Mobility in Developing and Urbanized Regions
• Performance of attack strategies on modular networks
• Community detection in weighted brain connectivity networks beyond the resolution limit
• Mining the modular structure of protein interaction networks
• Matching Community Structure Across Online Social Networks
• Entrograms and coarse graining of dynamics on complex networks
• Criterions for locally dense subgraphs
• Extending modularity by capturing the similarity attraction feature in the null model
• On Comparing and Enhancing Common Approaches to Network Community Detection
• A Modular Multiscale Approach to Overlapping Community Detection
• Unsupervised Machine Learning of Open Source Russian Twitter Data Reveals Global Scope and Operational Characteristics
• The Asymptotic Distribution of Modularity in Weighted Signed Networks
• Overlapping Communities in Social Networks
• Local multiresolution order in community detection
• Modular Networks for Validating Community Detection Algorithms
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Multi-Level Modeling of Quotation Families Morphogenesis
• Obtaining Communities with a Fitness Growth Process
• Understanding news story chains using information retrieval and network clustering techniques
• A New Community Definition For MultiLayer Networks And A Novel Approach For Its Efficient Computation
• Comparison and Benchmark of Graph Clustering Algorithms
• Community Structure Characterization
• Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm
• A Statistical Density-Based Analysis of Graph Clustering Algorithm Performance
• Detection of hidden structures on all scales in amorphous materials and complex physical systems: basic notions and applications to networks, lattice systems, and glasses
• Community Detection in networks by Dynamical Optimal Transport Formulation
• Location Prediction: Communities Speak Louder than Friends
• Discovery of Latent Factors in High-dimensional Data Using Tensor Methods
• Shaping Communities out of Triangles
• Gaining Insights on Student Course Selection in Higher Education with Community Detection
• I will be there for you: six friends in a clique
• The Atlas for the Aspiring Network Scientist
• Tradition and Innovation in Scientists' Research Strategies
• Modular decomposition of Markov chain: detecting hierarchical organization of pervasive communities
• Directed mixed membership stochastic blockmodel
• Community detection by resistance distance: automation and benchmark testing
• Stochastic fluctuations and the detectability limit of network communities
• GVE-Louvain: Fast Louvain Algorithm for Community Detection in Shared Memory Setting
• Side Information in the Binary Stochastic Block Model: Exact Recovery
• Latent Geometry Inspired Graph Dissimilarities Enhance Affinity Propagation Community Detection in Complex Networks
• Initial validation for the estimation of resting-state fMRI effective connectivity by a generalization of the correlation approach
• Coresets for Vector Summarization with Applications to Network Graphs
• Metrics for Community Analysis: A Survey
• Tourists Profiling by Interest Analysis
• Transforming complex network to the acyclic one
• The Importance of Being Negative: A serious treatment of non-trivial edges in brain functional connectome
• The NOESIS Network-Oriented Exploration, Simulation, and Induction System
• Estimating Network Parameters for Selecting Community Detection Algorithms
• A new edge betweenness measure using a game theoretical approach: an application to hierarchical community detection
• Community Detection in Signed Networks: an Error-Correcting Code Approach
• Leveraging Evolution Dynamics to Generate Benchmark Complex Networks with Community Structures
• A new method for quantifying network cyclic structure to improve community detection
• Network community detection via iterative edge removal in a flocking-like system
• A new measure of modularity density for community detection
• Multi-level Graph Drawing using Infomap Clustering
• Node Embedding via Word Embedding for Network Community Discovery
• Triangles as basis to detect communities: an application to Twitter's network
• Modeling Information Diffusion in Social Networks
• Collusion-Resistant Worker Set Selection for Transparent and Verifiable Voting
• Approximate Closest Community Search in Networks
• Graph-based Method for Summarized Storyline Generation in Twitter
• Quantum Algorithm for Testing Graph Completeness
• From Leiden to Pleasure Island: The Constant Potts Model for Community Detection as a Hedonic Game
• Community detection robustness of graph neural networks
• Generic criticality of community structure in random graphs
• Who will accept my request? Predicting response of link initiation in two-way relation networks
• Neural Stochastic Block Model & Scalable Community-Based Graph Learning
• Network maps of student work with physics, other sciences, and math in an integrated science course
• Clustering evolving data using kernel-based methods
• The Emerging Scholarly Brain
• EXIT Analysis for Community Detection
• Community Detection by a Riemannian Projected Proximal Gradient Method
• Detecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach
• Identifying Illicit Drug Dealers on Instagram with Large-scale Multimodal Data Fusion
• Identification of hybrid node and link communities in complex networks
• The efficiency of community detection by most similar node pairs
• Analysis of Social Group Dynamics
• BigGraphVis: Leveraging Streaming Algorithms and GPU Acceleration for Visualizing Big Graphs
• EagleMine: Vision-Guided Mining in Large Graphs
• Structure Amplification on Multi-layer Stochastic Block Models
• Streaming Belief Propagation for Community Detection
• Uncovering nodes that spread information between communities in social networks
• Similarity networks of ordinal-pattern transitions classify falling paper trajectories
• On Varying Topology of Complex Networks and Performance Limitations of Community Detection Algorithms
• A High-Performance Evolutionary Multiobjective Community Detection Algorithm
• Simulation-Optimization Approaches for the Network Immunization Problem with Quarantining
• A graph-based spectral classification of Type II supernovae
• Reinventing the Triangles: Rule of Thumb for Assessing Detectability
• SGPD Volume Maximization for Community Detection
• Modeling Regime Shifts in Multiple Time Series
• Overlapping Communities in Complex Networks
• Distributed Community Detection with the WCC Metric
• Understanding Vulnerability of Communities in Complex Networks
• Estimating Mixed-Memberships Using the Symmetric Laplacian Inverse Matrix
• GA Based Q-Attack on Community Detection
• Multilayer Network Analysis of the Drug Pipeline in the Global Pharmaceutical Industry
• Scalable Community Detection over Geo-Social Network
• The Bron-Kerbosch Algorithm with Vertex Ordering is Output-Sensitive
• A framework for community detection in heterogeneous multi-relational networks
• Bayesian Modeling of Random Walker for Community Detection in Networks
• Towards a property graph generator for benchmarking
• Error-Correcting Decoders for Communities in Networks
• Network analyses of student engagement with on-line textbook problems
• Correlation-Based Community Detection