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

• Fast unfolding of communities in large networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• The diameter of the world wide web
• The architecture of complex weighted networks
• Functional cartography of complex metabolic networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Defining and identifying communities in networks
• Statistical Mechanics of Community Detection
• Detecting the overlapping and hierarchical community structure of complex networks
• Self-similar community structure in organisations
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Synchronization reveals topological scales in complex networks
• 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
• Fuzzy communities and the concept of bridgeness in complex networks
• Detecting Network Communities: a new systematic and efficient algorithm
• Multiresolution community detection for megascale networks by information-based replica correlations
• Assessing the relevance of node features for network structure
• Subgraphs in random networks
• Identifying "communities" within energy landscapes
• When are networks truly modular?
• Partitioning and modularity of graphs with arbitrary degree distribution
• Subgraphs and network motifs in geometric networks
• (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 (294)

• Community detection in graphs
• From Louvain to Leiden: guaranteeing well-connected communities
• Link communities reveal multiscale complexity in networks
• 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
• Local resolution-limit-free Potts model for community detection
• 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
• Self-similar scaling of density in complex real-world networks
• Centrality Measures for Networks with Community Structure
• 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
• Overlapping Community Detection in Complex Networks using Symmetric Binary Matrix Factorization
• Z-score-based modularity for community detection in networks
• 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
• Exploring the limits of community detection strategies in complex networks
• The Community Structure of the Global Corporate Network
• Estimating the resolution limit of the map equation in community detection
• 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
• Will the US Economy Recover in 2010? A Minimal Spanning Tree Study
• 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
• Community characterization of heterogeneous complex systems
• Efficient community detection of network flows for varying Markov times and bipartite networks
• Deep Community Detection
• Data Mining on Social Interaction Networks
• The role of endogenous and exogenous mechanisms in the formation of R&D networks
• Potts model based on a Markov process computation solves the community structure problem effectively
• Topologically biased random walk with application for community finding in networks
• 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
• Hierarchical communities in the walnut structure of the Japanese production network
• Towards realistic artificial benchmark for community detection algorithms evaluation
• 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
• From Free Text to Clusters of Content in Health Records: An Unsupervised Graph Partitioning Approach
• How higher goals are constructed and collapse under stress: a hierarchical Bayesian control systems perspective
• Maximal entropy random walk in community finding
• Contagion processes on the static and activity driven coupling networks
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Overlapping Community Discovery Methods: A Survey
• Modularity functions maximization with nonnegative relaxation facilitates community detection in networks
• Synwalk -- Community Detection via Random Walk Modelling
• OLCPM: An Online Framework for Detecting Overlapping Communities in Dynamic Social Networks
• DMCS : Density Modularity based Community Search
• Community evolution in retweet networks
• Embedding-based Silhouette Community Detection
• Community Detection in Networks using Graph Distance
• A Unified Method of Detecting Core-Periphery Structure and Community Structure in Networks
• Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
• Improving the performance of algorithms to find communities in networks
• Effective and Scalable Clustering on Massive Attributed Graphs
• Group detection in complex networks: An algorithm and comparison of the state of the art
• Identifying overlapping communities in social networks using multi-scale local information expansion
• Ensemble Clustering for Graphs
• Cell assembly dynamics of sparsely-connected inhibitory networks: a simple model for the collective activity of striatal projection neurons
• 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
• A General Framework for Complex Network-Based Image Segmentation
• Extracting Complements and Substitutes from Sales Data: A Network Perspective
• Community detection in networks via nonlinear modularity eigenvectors
• Random Spatial Network Models with Core-Periphery Structure
• Bow-tie structure and community identification of global supply chain network
• Community structure in the World Trade Network based on communicability distances
• Ant Colony Optimization with a New Random Walk Model for Community Detection in Complex Networks
• Closed benchmarks for network community structure characterization
• Stock portfolio structure of individual investors infers future trading behavior
• Mapping flows on sparse networks with missing links
• DeFiNe: an optimisation-based method for robust disentangling of filamentous networks
• Spatial correlations in attribute communities
• Universal productivity patterns in research careers
• Discovering link communities in complex networks by exploiting link dynamics
• Detecting mesoscale structures by surprise
• 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
• Maps of sparse Markov chains efficiently reveal community structure in network flows with memory
• A data-driven framework for dimensionality reduction and causal inference in climate fields
• The stability to instability transition in the structure of large scale networks
• Global disorder transition in the community structure of large-q Potts systems
• Generalization of Clustering Agreements and Distances for Overlapping Clusters and Network Communities
• Total variation based community detection using a nonlinear optimization approach
• Cycle Analysis of Directed Acyclic Graphs
• Efficiently Detecting Overlapping Communities through Seeding and Semi-Supervised Learning
• A Method for Group Extraction and Analysis in Multilayer Social Networks
• Perception, Prestige and PageRank
• Community detection based on "clumpiness" matrix in complex networks
• Fragmenting networks by targeting collective influencers at a mesoscopic level
• Multiple bipolar fuzzy measures: an application to community detection problems for networks with additional information
• The Impact of Random Models on Clustering Similarity
• User-Relatedness and Community Structure in Social Interaction Networks
• Comparison of Cross-Validation Methods for Stochastic Block Models
• Semi-supervised Graph Neural Networks for Pileup Noise Removal
• Subdivisions and Crossroads: Identifying Hidden Community Structures in a Data Archive's Citation Network
• Distress propagation on production networks: Coarse-graining and modularity of linkages
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Robustness of community structure under edge addition
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Hierarchical community detection by recursive partitioning
• Comparing Graph Clusterings: Set partition measures vs. Graph-aware measures
• Generating global network structures by triad types
• Convex skeletons of complex networks
• Modules in the metabolic network of E.coli with regulatory interactions
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• Ordered community structure in networks
• Detecting network communities beyond assortativity-related attributes
• Online Tensor Methods for Learning Latent Variable Models
• Discovering Social Circles in Ego Networks
• Normalized mutual information is a biased measure for classification and community detection
• Time-sync Video Tag Extraction Using Semantic Association Graph
• Multi-scale Laplacian community detection in heterogeneous networks
• Inferring propagation paths for sparsely observed perturbations on complex networks
• POISED: Spotting Twitter Spam Off the Beaten Paths
• Non-overlapping community detection
• Decoding communities in networks
• Scalable Spectral Algorithms for Community Detection in Directed Networks
• Topological Feature Based Classification
• Generalized network community detection
• DUEF-GA: Data Utility and Privacy Evaluation Framework for Graph Anonymization
• The Impact of Social Segregation on Human Mobility in Developing and Urbanized Regions
• Criterions for locally dense subgraphs
• Matching Community Structure Across Online Social Networks
• 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
• Entrograms and coarse graining of dynamics on complex networks
• Overlapping Communities in Social Networks
• Modular Networks for Validating Community Detection Algorithms
• 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
• The Asymptotic Distribution of Modularity in Weighted Signed Networks
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Obtaining Communities with a Fitness Growth Process
• Local multiresolution order in community detection
• Unsupervised Machine Learning of Open Source Russian Twitter Data Reveals Global Scope and Operational Characteristics
• Multi-Level Modeling of Quotation Families Morphogenesis
• Location Prediction: Communities Speak Louder than Friends
• Community Detection in networks by Dynamical Optimal Transport Formulation
• 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
• Understanding news story chains using information retrieval and network clustering techniques
• 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
• Discovery of Latent Factors in High-dimensional Data Using Tensor Methods
• Directed mixed membership stochastic blockmodel
• Shaping Communities out of Triangles
• The Atlas for the Aspiring Network Scientist
• I will be there for you: six friends in a clique
• Modular decomposition of Markov chain: detecting hierarchical organization of pervasive communities
• GVE-Louvain: Fast Louvain Algorithm for Community Detection in Shared Memory Setting
• Stochastic fluctuations and the detectability limit of network communities
• Tradition and Innovation in Scientists' Research Strategies
• Community detection by resistance distance: automation and benchmark testing
• Gaining Insights on Student Course Selection in Higher Education with Community Detection
• Tourists Profiling by Interest Analysis
• Side Information in the Binary Stochastic Block Model: Exact Recovery
• The NOESIS Network-Oriented Exploration, Simulation, and Induction System
• The Importance of Being Negative: A serious treatment of non-trivial edges in brain functional connectome
• A new edge betweenness measure using a game theoretical approach: an application to hierarchical community detection
• Latent Geometry Inspired Graph Dissimilarities Enhance Affinity Propagation Community Detection in Complex Networks
• Metrics for Community Analysis: A Survey
• Initial validation for the estimation of resting-state fMRI effective connectivity by a generalization of the correlation approach
• Community Detection in Signed Networks: an Error-Correcting Code Approach
• Coresets for Vector Summarization with Applications to Network Graphs
• Estimating Network Parameters for Selecting Community Detection Algorithms
• Transforming complex network to the acyclic one
• Generic criticality of community structure in random graphs
• Multi-level Graph Drawing using Infomap Clustering
• Community detection robustness of graph neural networks
• A new method for quantifying network cyclic structure to improve community detection
• Neural Stochastic Block Model & Scalable Community-Based Graph Learning
• Quantum Algorithm for Testing Graph Completeness
• Clustering evolving data using kernel-based methods
• Approximate Closest Community Search in Networks
• Node Embedding via Word Embedding for Network Community Discovery
• The Emerging Scholarly Brain
• Modeling Information Diffusion in Social Networks
• From Leiden to Pleasure Island: The Constant Potts Model for Community Detection as a Hedonic Game
• Leveraging Evolution Dynamics to Generate Benchmark Complex Networks with Community Structures
• Network community detection via iterative edge removal in a flocking-like system
• Triangles as basis to detect communities: an application to Twitter's network
• Who will accept my request? Predicting response of link initiation in two-way relation networks
• Collusion-Resistant Worker Set Selection for Transparent and Verifiable Voting
• Graph-based Method for Summarized Storyline Generation in Twitter
• A new measure of modularity density for community detection
• Network maps of student work with physics, other sciences, and math in an integrated science course
• Overlapping Communities in Complex Networks
• Distributed Community Detection with the WCC Metric
• Estimating Mixed-Memberships Using the Symmetric Laplacian Inverse Matrix
• Detecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach
• Reinventing the Triangles: Rule of Thumb for Assessing Detectability
• SGPD Volume Maximization for Community Detection
• Identifying Illicit Drug Dealers on Instagram with Large-scale Multimodal Data Fusion
• BigGraphVis: Leveraging Streaming Algorithms and GPU Acceleration for Visualizing Big Graphs
• A framework for community detection in heterogeneous multi-relational networks
• Towards a property graph generator for benchmarking
• Modeling Regime Shifts in Multiple Time Series
• Structure Amplification on Multi-layer Stochastic Block Models
• Streaming Belief Propagation for Community Detection
• A graph-based spectral classification of Type II supernovae
• The efficiency of community detection by most similar node pairs
• Identification of hybrid node and link communities in complex networks
• Analysis of Social Group Dynamics
• Understanding Vulnerability of Communities in Complex Networks
• EagleMine: Vision-Guided Mining in Large Graphs
• Scalable Community Detection over Geo-Social Network
• The Function of Communities in Protein Interaction Networks at Multiple Scales
• Uncovering nodes that spread information between communities in social networks
• A High-Performance Evolutionary Multiobjective Community Detection Algorithm
• On Varying Topology of Complex Networks and Performance Limitations of Community Detection Algorithms
• GA Based Q-Attack on Community Detection
• Correlation-Based Community Detection
• Network analyses of student engagement with on-line textbook problems
• Error-Correcting Decoders for Communities in Networks
• Similarity networks of ordinal-pattern transitions classify falling paper trajectories
• Bayesian Modeling of Random Walker for Community Detection in Networks
• EXIT Analysis for Community Detection
• The Bron-Kerbosch Algorithm with Vertex Ordering is Output-Sensitive
• Community Detection by a Riemannian Projected Proximal Gradient Method
• Multilayer Network Analysis of the Drug Pipeline in the Global Pharmaceutical Industry
• Simulation-Optimization Approaches for the Network Immunization Problem with Quarantining