Comparing community structure identification

Abstract

We compare recent approaches to community structure identification in terms of sensitivity and computational cost. The recently proposed modularity measure is revisited and the performance of the methods as applied to ad hoc networks with known community structure, is compared. We find that the most accurate methods tend to be more computationally expensive, and that both aspects need to be considered when choosing a method for practical purposes. The work is intended as an introduction as well as a proposal for a standard benchmark test of community detection methods.

10 pages, 3 figures, 1 table. v2: condensed, updated version as appears in JSTAT

References in corpus (29)

• Statistical mechanics of complex 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
• Hierarchical organization of modularity in metabolic networks
• Functional cartography of complex metabolic networks
• Defining and identifying communities in networks
• Community detection in complex networks using Extremal Optimization
• Self-similar community structure in organisations
• Community Structure in Jazz
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Detecting fuzzy community structures in complex networks with a Potts model
• Finding Communities in Linear Time: A Physics Approach
• Detecting Network Communities: a new systematic and efficient algorithm
• Subnetwork hierarchies of biochemical pathways
• Curvature of Co-Links Uncovers Hidden Thematic Layers in the World Wide Web
• Optimization with Extremal Dynamics
• A Method to Find Community Structures Based on Information Centrality
• A Local Method for Detecting Communities
• Distance, dissimilarity index, and network community structure
• Community analysis in social networks
• Identifying "communities" within energy landscapes
• Extremal Optimization for Graph Partitioning
• The large-scale structure of semantic networks: statistical analyses and a model for semantic growth
• Computing communities in large networks using random walks
• Casimir Energy Densities for Parallel Plate on Background of Conformally Flat Brane-World Geometries and Cosmological Constant Problem

Cited by in corpus (368)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Synchronization in complex networks
• Benchmark graphs for testing community detection algorithms
• Characterization of complex networks: A survey of measurements
• Community detection algorithms: a comparative analysis
• Stochastic blockmodels and community structure in networks
• Link communities reveal multiscale complexity in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Community structure in directed networks
• The Kuramoto model in complex networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Synchronization reveals topological scales in complex networks
• An information-theoretic framework for resolving community structure in complex networks
• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• Modularity and community detection in bipartite networks
• Detect overlapping and hierarchical community structure in networks
• Hierarchical modularity in human brain functional networks
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• Clustering and Community Detection in Directed Networks: A Survey
• Mixture models and exploratory analysis in networks
• Extracting the hierarchical organization of complex systems
• 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
• Generalized Louvain Method for Community Detection in Large Networks
• Classes of complex networks defined by role-to-role connectivity profiles
• Fuzzy communities and the concept of bridgeness in complex networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Module identification in bipartite and directed networks
• Memory in network flows and its effects on spreading dynamics and community detection
• Structure and inference in annotated networks
• An efficient and principled method for detecting communities in networks
• Detecting network communities by propagating labels under constraints
• Uncovering space-independent communities in spatial networks
• Robustness of community structure in networks
• Extending the definition of modularity to directed graphs with overlapping communities
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Modularity-Maximizing Network Communities via Mathematical Programming
• Community Detection via Maximization of Modularity and Its Variants
• A Bayesian Approach to Network Modularity
• A Classification for Community Discovery Methods in Complex Networks
• Towards real-time community detection in large networks
• The entropy of network ensembles
• Detecting highly overlapping community structure by greedy clique expansion
• Analysis of community structure in networks of correlated data
• Modularity clustering is force-directed layout
• Multiresolution community detection for megascale networks by information-based replica correlations
• Community detection in networks: Structural communities versus ground truth
• The entropy of randomized network ensembles
• Assessing the relevance of node features for network structure
• Community Detection as an Inference Problem
• Hydrodynamic provinces and oceanic connectivity from a transport network help designing marine reserves
• Identifying the Community Structure of the International-Trade Multi Network
• Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
• 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
• Trophic coherence determines food-web stability
• Evaluating Local Community Methods in Networks
• Local resolution-limit-free Potts model for community detection
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
• Tolerating the Community Detection Resolution Limit with Edge Weighting
• Limited resolution in complex network community detection with Potts model approach
• Identifying network communities with a high resolution
• On community structure in complex networks: challenges and opportunities
• 20 years of network community detection
• Efficiently inferring community structure in bipartite networks
• LinkRank: Finding communities in directed networks
• The structure of borders in a small world
• Exploring the Free Energy Landscape: From Dynamics to Networks and Back
• Community Structure of the Physical Review Citation Network
• Social media fingerprints of unemployment
• Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
• Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
• Community Structure in Congressional Cosponsorship Networks
• Synchronization processes in complex networks
• Communities, Knowledge Creation, and Information Diffusion
• Socially-Aware Networking: A Survey
• Random graph models for dynamic networks
• Large-scale structure of time evolving citation networks
• Detection of gene communities in multi-networks reveals cancer drivers
• Mixing local and global information for community detection in large networks
• Revisiting Date and Party Hubs: Novel Approaches to Role Assignment in Protein Interaction Networks
• Fuzzy overlapping communities in networks
• Analyzing complex functional brain networks: fusing statistics and network science to understand the brain
• Bi-clique Communities
• The Influence of Network Topology on Sound Propagation in Granular Materials
• Large-scale structure of a nation-wide production network
• Balance in signed networks
• When are networks truly modular?
• Clustering Network Layers With the Strata Multilayer Stochastic Block Model
• Social significance of community structure: Statistical view
• Deciphering Network Community Structure by Surprise
• Enhancing community detection using a network weighting strategy
• Detecting communities using asymptotical Surprise
• Flow networks: A characterization of geophysical fluid transport
• A Large-Scale Community Structure Analysis In Facebook
• Synchronizability determined by coupling strengths and topology on Complex Networks
• Spectral methods for the detection of network community structure: a comparative analysis
• Ranking and clustering of nodes in networks with smart teleportation
• Modular gateway-ness connectivity and structural core organization in maritime network science
• Emergence of Soft Communities from Geometric Preferential Attachment
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• Dynamical and spectral properties of complex networks
• Surprise maximization reveals the community structure of complex networks
• Applicability and Interpretability of Hierarchical Agglomerative Clustering With or Without Contiguity Constraints
• Using network science to analyze football passing networks: dynamics, space, time and the multilayer nature of the game
• Spectral tripartitioning of networks
• Community Detecting By Signaling on Complex Networks
• A New Comparative Definition of Community and Corresponding Identifying Algorithm
• Multiway spectral community detection in networks
• Mesoscopic organization reveals the constraints governing C. elegans nervous system
• Spectral Coarse Graining and Synchronization in Oscillator Networks
• Partitioning and modularity of graphs with arbitrary degree distribution
• Citation Recommendation: Approaches and Datasets
• Emergence of multiplex communities in collaboration networks
• Community structure of complex software systems: Analysis and applications
• Communicability Graph and Community Structures in Complex Networks
• The Community Structure of the Global Corporate Network
• Exploring the limits of community detection strategies in complex networks
• (Un)detectable cluster structure in sparse networks
• Improved mutual information measure for classification and community detection
• On a 'Two Truths' Phenomenon in Spectral Graph Clustering
• Synchronization and modularity in complex networks
• Dynamic communities in multichannel data: An application to the foreign exchange market during the 2007--2008 credit crisis
• Community Structure in the United Nations General Assembly
• Principled approach to the selection of the embedding dimension of networks
• Finding and testing network communities by lumped Markov chains
• Comparison and validation of community structures in complex networks
• Protein-Interaction-Networks: More than mere modules
• Hierarchical multiresolution method to overcome the resolution limit in complex networks
• Community structure: A comparative evaluation of community detection methods
• Impact of community structure on information transfer
• Multistep greedy algorithm identifies community structure in real-world and computer-generated networks
• Mesoscopic Structures Reveal the Network Between the Layers of Multiplex Datasets
• Efficient community detection of network flows for varying Markov times and bipartite networks
• Uncovering the community structure associated with the diffusion dynamics of 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
• Coexistence of opposite opinions in a network with communities
• Topologically biased random walk with application for community finding in networks
• Accuracy and Precision of Methods for Community Identification in Weighted Networks
• Covariance, correlation matrix and the multi-scale community structure of networks
• Characterizing the analogy between hyperbolic embedding and community structure of complex networks
• Exploring the solution landscape enables more reliable network community detection
• Markov random walk under constraint for discovering overlapping communities in complex networks
• Large network community detection by fast label propagation
• Using explosive percolation in analysis of real-world networks
• Maximizing Influence Propagation in Networks with Community Structure
• Communities in Networks
• Clustering Memes in Social Media
• Towards realistic artificial benchmark for community detection algorithms evaluation
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• Unveiling community structures in weighted networks
• Trapping in scale-free networks with hierarchical organization of modularity
• Detecting communities of triangles in complex networks using spectral optimization
• Network science: a review focused on tourism
• The Role of Weight on Community Structure of Networks
• Software systems through complex networks science: Review, analysis and applications
• Detection of node group membership in networks with group overlap
• Deterministic Modularity Optimization
• Multilevel Hierarchical Kernel Spectral Clustering for Real-Life Large Scale Complex Networks
• Network community detection using modularity density measures
• Random walks in modular scale-free networks with multiple traps
• Community Detection in Complex Networks by Dynamical Simplex Evolution
• How to become a superhero
• Measuring Significance of Community Structure in Complex Networks
• Stochastic block model and exploratory analysis in signed networks
• Community structures and role detection in music networks
• Bi-Objective Community Detection (BOCD) in Networks using Genetic Algorithm
• Multi-resolution community detection based on generalized self-loop rescaling strategy
• Community Detection in Quantum Complex Networks
• Finding network communities using modularity density
• Retweet communities reveal the main sources of hate speech
• Bridge Bounding: A Local Approach for Efficient Community Discovery in Complex Networks
• Broad lifetime distributions for ordering dynamics in complex networks
• Community detection using boundary nodes in complex networks
• Significant communities in large sparse networks
• A paradox in community detection
• Optimal map of the modular structure of complex networks
• A Distributed and Approximated Nearest Neighbors Algorithm for an Efficient Large Scale Mean Shift Clustering
• Leveraging disjoint communities for detecting overlapping community structure
• Maximal entropy random walk in community finding
• Genetic Algorithm with a Local Search Strategy for Discovering Communities in Complex Networks
• Community Detection with and without Prior Information
• Network Structure, Topology and Dynamics in Generalized Models of Synchronization
• Hierarchical benchmark graphs for testing community detection algorithms
• The inherent community structure of hyperbolic networks
• Coarse Graining for Synchronization in Directed Networks
• Finding communities in sparse networks
• Structure of Heterogeneous Networks
• Exponential random graph models for networks with community structure
• eBay users form stable groups of common interest
• OLCPM: An Online Framework for Detecting Overlapping Communities in Dynamic Social Networks
• DMCS : Density Modularity based Community Search
• Community evolution in retweet networks
• Extracting tag hierarchies
• Community detection and Social Network analysis based on the Italian wars of the 15th century
• Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
• Improving the performance of algorithms to find communities in networks
• Unsupervised Galaxy Morphological Visual Representation with Deep Contrastive Learning
• Community detection in multiplex networks based on orthogonal nonnegative matrix tri-factorization
• Spectral Clustering with Epidemic Diffusion
• Community Detection in Dynamic Networks via Adaptive Label Propagation
• Identifying overlapping communities in social networks using multi-scale local information expansion
• Group detection in complex networks: An algorithm and comparison of the state of the art
• Modular synchronization in complex networks with a gauge Kuramoto model
• RobustECD: Enhancement of Network Structure for Robust Community Detection
• SurpriseMe: an integrated tool for network community structure characterization using Surprise maximization
• Spatial regionalization based on optimal information compression
• Modularity and the spread of perturbations in complex dynamical systems
• Enhancing community detection by local structural information
• Alternative approach to community detection in networks
• Community detection in networks via nonlinear modularity eigenvectors
• Route Identification in the National Football League
• Mesoscopic analysis of networks: applications to exploratory analysis and data clustering
• Mutual Trust and Cooperation in the Evolutionary Hawks-Doves Game
• Effect of size heterogeneity on community identification in complex networks
• Co-community Structure in Time-varying Networks
• Quantum walks on complex networks with connection instabilities and community structure
• Ant Colony Optimization with a New Random Walk Model for Community Detection in Complex Networks
• Community detection using preference networks
• Revisiting Dynamic Graph Clustering via Matrix Factorization
• Spatial correlations in attribute communities
• Discovering link communities in complex networks by exploiting link dynamics
• Community detection by spectral methods in multi-layer networks
• Viewpoint Discovery and Understanding in Social Networks
• Network clustering and community detection using modulus of families of loops
• Seeding for pervasively overlapping communities
• Complex contagion features without social reinforcement in a model of social information flow
• Multi-resolution community detection in massive networks
• Optimizing at the Ergodic Edge
• Clustering memes in social media streams
• Detecting Communities in Tripartite Hypergraphs
• Coupled Graphs and Tensor Factorization for Recommender Systems and Community Detection
• Community detection by label propagation with compression of flow
• Signed Graph Analysis for the Interpretation of Voting Behavior
• Robustness of community structure to node removal
• Inference for graphs and networks: Extending classical tools to modern data
• Systems Applications of Social Networks
• An Ant-Based Algorithm with Local Optimization for Community Detection in Large-Scale Networks
• Community detection based on significance optimization in complex networks
• Node mixing and group structure of complex software networks
• Community detection based on first passage probabilities
• A Generative Node-attribute Network Model for Detecting Generalized Structure
• Community detection for weighted bipartite networks
• Graph coarse-graining reveals differences in the module-level structure of functional brain networks
• Characterization and exploitation of community structure in cover song networks
• Weighted Community Detection and Data Clustering Using Message Passing
• Parallel clustering of high-dimensional social media data streams
• Finding overlapping communities in networks using evolutionary method
• The stability to instability transition in the structure of large scale networks
• Distributed Community Detection in Dynamic Graphs
• A Method for Group Extraction and Analysis in Multilayer Social Networks
• Epidemic spreading in group-structured populations
• Evolutionary Subnetworks in Complex Systems
• Unsupervised clustering analysis: a multiscale complex networks approach
• Community detection based on "clumpiness" matrix in complex networks
• Efficient Bayesian Community Detection using Non-negative Matrix Factorisation
• Finite size analysis of the detectability limit of the stochastic block model
• Community Detection in Complex Networks Using Agents
• Pairwise Covariates-adjusted Block Model for Community Detection
• Detecting groups of similar components in complex networks
• A Survey of Community Search Over Big Graphs
• Convex skeletons of complex networks
• Detecting network communities beyond assortativity-related attributes
• Nested partitions from hierarchical clustering statistical validation
• Graph Generators: State of the Art and Open Challenges
• Emergence and persistence of communities in coevolutionary networks
• CARL-G: Clustering-Accelerated Representation Learning on Graphs
• Normalized mutual information is a biased measure for classification and community detection
• Decoding communities in networks
• Generalized Markov stability of network communities
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Community structure in real-world networks from a non-parametrical synchronization-based dynamical approach
• Metrics matter in community detection
• A Survey of Spatio-Temporal EEG data Analysis: from Models to Applications
• FCS-HGNN: Flexible Multi-type Community Search in Heterogeneous Information Networks
• The art of community detection
• Detectability of Macroscopic Structures in Directed Asymmetric Stochastic Block Model
• Network Community Detection on Metric Space
• Graph Neural Network Encoding for Community Detection in Attribute Networks
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Mutual information and the encoding of contingency tables
• Local multiresolution order in community detection
• Obtaining Communities with a Fitness Growth Process
• Overlapping Communities in Social Networks
• On the Stability of Community Detection Algorithms on Longitudinal Citation Data
• Democratic summary of public opinions in free-response surveys
• Towards a generalization of information theory for hierarchical partitions
• A Synthetic Network Generator for Covert Network Analytics
• Detection of hidden structures on all scales in amorphous materials and complex physical systems: basic notions and applications to networks, lattice systems, and glasses
• Role-based Label Propagation Algorithm for Community Detection
• Evolving community structure in the international pesticide trade networks
• Evaluating the role of risk networks on risk identification, classification and emergence
• A General Definition of Network Communities and the Corresponding Detection Algorithm
• SCOREH+: A High-Order Node Proximity Spectral Clustering on Ratios-of-Eigenvectors Algorithm for Community Detection
• Phase transitions and optimal algorithms for semi-supervised classifications on graphs: from belief propagation to graph convolution network
• Clubmark: a Parallel Isolation Framework for Benchmarking and Profiling Clustering Algorithms on NUMA Architectures
• EC-SBM Synthetic Network Generator
• The Atlas for the Aspiring Network Scientist
• Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering
• Community detection by resistance distance: automation and benchmark testing
• Gene-based and semantic structure of the Gene Ontology as a complex network
• Consistency between ordering and clustering methods for graphs
• NISQ-ready community detection based on separation-node identification
• I will be there for you: six friends in a clique
• Discovering Block Structure in Networks
• Stochastic fluctuations and the detectability limit of network communities
• The effect of the pandemic on complex socio-economic systems: community detection induced by communicability
• Comparing university organizational units and scientific co-authorship communities
• A new method for community detection in social networks based on message distribution
• A multilevel clustering technique for community detection
• Return to basics: Clustering of scientific literature using structural information
• A Boosting Approach to Learning Graph Representations
• Nonlinear Markov Clustering by Minimum Curvilinear Sparse Similarity
• Learning Optimal Graph Filters for Clustering of Attributed Graphs
• Metrics for Community Analysis: A Survey
• Outlier Edge Detection Using Random Graph Generation Models and Applications
• The Importance of Being Negative: A serious treatment of non-trivial edges in brain functional connectome
• Latent Geometry Inspired Graph Dissimilarities Enhance Affinity Propagation Community Detection in Complex Networks
• Skeleton coupling: a novel interlayer mapping of community evolution in temporal networks
• Sampling node group structure of social and information networks
• The way to uncover community structure with core and diversity
• Equipping SBMs with RBMs: An Explainable Approach for Analysis of Networks with Covariates
• Modeling Information Diffusion in Social Networks
• LUEM : Local User Engagement Maximization in Networks
• Evidential Label Propagation Algorithm for Graphs
• A modified Ricci flow on arbitrary weighted graph
• Clustering evolving data using kernel-based methods
• Feature extraction from complex networks: A case of study in genomic sequences classification
• Evolutionary Multi Objective Optimization Algorithm for Community Detection in Complex Social Networks
• A new method for quantifying network cyclic structure to improve community detection
• Limited Random Walk Algorithm for Big Graph Data Clustering
• Robust Fuzzy local k-plane clustering with mixture distance of hinge loss and L1 norm
• Efficient Detection of Communities with Significant Overlaps in Networks: Partial Community Merger Algorithm
• A Generative Model for Exploring Structure Regularities in Attributed Networks
• Une nouvelle mesure pour l'évaluation des méthodes de détection de communautés
• Measuring inter-cluster similarities with Alpha Shape TRIangulation in loCal Subspaces (ASTRICS) facilitates visualization and clustering of high-dimensional data
• Finding New Order in Biological Functions from the Network Structure of Gene Annotations
• Discriminative community detection for multiplex networks
• Understanding Vulnerability of Communities in Complex Networks
• Community Detection by a Riemannian Projected Proximal Gradient Method
• Detección de comunidades en redes: Algoritmos y aplicaciones
• Correlation-Based Community Detection
• Error-Correcting Decoders for Communities in Networks
• The attack tolerance of community structure in complex networks
• Model-based edge clustering for weighted networks with a noise component
• To Deconvolve, or Not to Deconvolve: Inferences of Neuronal Activities using Calcium Imaging Data
• A Surrogate-Assisted Variable Grouping Algorithm for General Large Scale Global Optimization Problems
• Absence of a resolution limit in in-block nestedness
• Multi-View Spatial-Temporal Graph Convolutional Networks with Domain Generalization for Sleep Stage Classification
• Sparse Nonnegative Matrix Factorization for Multiple Local Community Detection
• Ground state energy of $q$-state Potts model: the minimum modularity
• Beyond One Solution: The Case for a Comprehensive Exploration of Solution Space in Community Detection
• Probabilistic Causal Analysis of Social Influence
• Structure Amplification on Multi-layer Stochastic Block Models
• Interplay between Network Topology and Dynamics in Neural Systems
• CALF-SBM: A Covariate-Assisted Latent Factor Stochastic Block Model
• A Survey on Role-Oriented Network Embedding
• Community Structure and Topical Differentiation in European RTD Collaborations
• The efficiency of community detection by most similar node pairs