Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities

Abstract

Many complex networks display a mesoscopic structure with groups of nodes sharing many links with the other nodes in their group and comparatively few with nodes of different groups. This feature is known as community structure and encodes precious information about the organization and the function of the nodes. Many algorithms have been proposed but it is not yet clear how they should be tested. Recently we have proposed a general class of undirected and unweighted benchmark graphs, with heterogenous distributions of node degree and community size. An increasing attention has been recently devoted to develop algorithms able to consider the direction and the weight of the links, which require suitable benchmark graphs for testing. In this paper we extend the basic ideas behind our previous benchmark to generate directed and weighted networks with built-in community structure. We also consider the possibility that nodes belong to more communities, a feature occurring in real systems, like, e. g., social networks. As a practical application, we show how modularity optimization performs on our new benchmark.

9 pages, 13 figures. Final version published in Physical Review E. The code to create the benchmark graphs can be freely downloaded from http://santo.fortunato.googlepages.com/inthepress2

References in corpus (19)

• The structure and function of complex networks
• Community structure in social and biological 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
• 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
• Detecting the overlapping and hierarchical community structure of complex networks
• Self-similar community structure in organisations
• Community structure in directed networks
• Mixture models and exploratory analysis in networks
• Fuzzy communities and the concept of bridgeness in complex networks
• Size reduction of complex networks preserving modularity
• Detection of node group membership in networks with group overlap
• Inversion method for content-based networks

Cited by in corpus (150)

• Community detection in graphs
• Community detection algorithms: a comparative analysis
• Community detection in networks: A user guide
• Finding statistically significant communities in networks
• Consensus clustering in complex networks
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• Clustering and Community Detection in Directed Networks: A Survey
• Community Discovery in Dynamic Networks: a Survey
• A Comprehensive Survey on Community Detection with Deep Learning
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Consistency and differences between centrality measures across distinct classes of networks
• Detecting highly overlapping community structure by greedy clique expansion
• A General Optimization Technique for High Quality Community Detection in Complex Networks
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• 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
• Faster unfolding of communities: speeding up the Louvain algorithm
• Bayesian stochastic blockmodeling
• Is a Single Embedding Enough? Learning Node Representations that Capture Multiple Social Contexts
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Overlapping Community Detection in Complex Networks using Symmetric Binary Matrix Factorization
• Z-score-based modularity for community detection in networks
• Developments in the theory of randomized shortest paths with a comparison of graph node distances
• Collective dynamics of belief evolution under cognitive coherence and social conformity
• Detecting sequences of system states in temporal networks
• The stability of a graph partition: A dynamics-based framework for community detection
• Finding and testing network communities by lumped Markov chains
• Weight Thresholding on Complex Networks
• Random Graph Modeling: A survey of the concepts
• A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning
• Magnetic eigenmaps for community detection in directed networks
• Markov random walk under constraint for discovering overlapping communities in complex networks
• Accelerating Community Detection by Using K-core Subgraphs
• Artificial Benchmark for Community Detection (ABCD): Fast Random Graph Model with Community Structure
• Towards realistic artificial benchmark for community detection algorithms evaluation
• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Structure and Overlaps of Communities in Networks
• Compression of Flow Can Reveal Overlapping-Module Organization in Networks
• A testing based extraction algorithm for identifying significant communities in networks
• Communities unfolding in multislice networks
• Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature
• Hyperbolicity Measures "Democracy" in Real-World Networks
• Communities and beyond: mesoscopic analysis of a large social network with complementary methods
• Significant communities in large sparse networks
• Synwalk -- Community Detection via Random Walk Modelling
• Hierarchical benchmark graphs for testing community detection algorithms
• Perturbation centrality and Turbine: a novel centrality measure obtained using a versatile network dynamics tool
• Magnetic Eigenmaps for the Visualization of Directed Networks
• Modularity-based approach for tracking communities in dynamic social networks
• Spectral Clustering with Epidemic Diffusion
• Identifying overlapping communities in social networks using multi-scale local information expansion
• Ensemble Clustering for Graphs: Comparisons and Applications
• Identifying multi-scale communities in networks by asymptotic surprise
• On Accuracy of Community Structure Discovery Algorithms
• Artificial Benchmark for Community Detection with Outliers (ABCD+o)
• Seeding for pervasively overlapping communities
• Mapping flows on weighted and directed networks with incomplete observations
• Fuzzy Overlapping Community Quality Metrics
• Robustness of community structure to node removal
• Efficiently Detecting Overlapping Communities through Seeding and Semi-Supervised Learning
• A Method for Group Extraction and Analysis in Multilayer Social Networks
• Scale-variant topological information for characterizing the structure of complex networks
• Multiresolution Consensus Clustering in Networks
• Community Detection in Partially Observable Social Networks
• On the Permanence of Vertices in Network Communities
• Community detection for networks with unipartite and bipartite structure
• Link community detection through global optimization and the inverse resolution limit of partition density
• Cycle flow based module detection in directed recurrence networks
• Robustness of community structure under edge addition
• A Survey of Community Search Over Big Graphs
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Random walks in directed modular networks
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• Detecting the optimal number of communities in complex networks
• Efficient Bayesian Community Detection using Non-negative Matrix Factorisation
• Comparing Graph Clusterings: Set partition measures vs. Graph-aware measures
• POISED: Spotting Twitter Spam Off the Beaten Paths
• Discovering Social Circles in Ego Networks
• Graph Generators: State of the Art and Open Challenges
• Scalable Spectral Algorithms for Community Detection in Directed Networks
• GANC: Greedy Agglomerative Normalized Cut
• A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• Transfer operators on graphs: Spectral clustering and beyond
• Criterions for locally dense subgraphs
• DANI: Fast Diffusion Aware Network Inference with Preserving Topological Structure Property
• Exploring triad-rich substructures by graph-theoretic characterizations in complex networks
• A Modular Multiscale Approach to Overlapping Community Detection
• Modular Networks for Validating Community Detection Algorithms
• Community Detection in Networks: A Rough Sets and Consensus Clustering Approach
• Compressive Network Analysis
• Parallel Global Edge Switching for the Uniform Sampling of Simple Graphs with Prescribed Degrees
• Comparison and Benchmark of Graph Clustering Algorithms
• Analysis of the susceptible-infected-susceptible epidemic dynamics in networks via the non-backtracking matrix
• Clubmark: a Parallel Isolation Framework for Benchmarking and Profiling Clustering Algorithms on NUMA Architectures
• DeepNC: Deep Generative Network Completion
• Modular decomposition of Markov chain: detecting hierarchical organization of pervasive communities
• Clustering Time-Evolving Networks Using the Spatio-Temporal Graph Laplacian
• Bayesian Overlapping Community Detection in Dynamic Networks
• DANI: A Fast Diffusion Aware Network Inference Algorithm
• Stochastic fluctuations and the detectability limit of network communities
• On Efficiently Detecting Overlapping Communities over Distributed Dynamic Graphs
• Topological aspects of the multi-language phases of the Naming Game on community-based networks
• Organisation of signal flow in directed networks
• Using Model-based Overlapping Seed Expansion to detect highly overlapping community structure
• Estimating Network Parameters for Selecting Community Detection Algorithms
• Content Distribution Strategies in Opportunistic Networks
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• Diffusion in Networks With Overlapping Community Structure
• Stochastic graph Voronoi tessellation reveals community structure
• Task-driven sampling of attributed networks
• Cross-Layer Design of Influence Maximization in Mobile Social Networks
• Overlapping Community Detection in Temporal Text Networks
• Partitioning Breaks Communities
• GCN for HIN via Implicit Utilization of Attention and Meta-paths
• Co-evolution of Functional Brain Network at Multiple Scales during Early Infancy
• Demographic and Structural Characteristics to Rationalize Link Formation in Online Social Networks
• Modeling Information Diffusion in Social Networks
• Community detection robustness of graph neural networks
• A Survey of Evolving Models for Weighted Complex Networks based on their Dynamics and Evolution
• Triangles as basis to detect communities: an application to Twitter's network
• Conflict Anticipation in the Search for Graph Automorphisms
• Krylov Subspace Approximation for Local Community Detection in Large Networks
• On role extraction for digraphs via neighbourhood pattern similarity
• Community detection and tracking on networks from a data fusion perspective
• ScienceWISE: Topic Modeling over Scientific Literature Networks
• Clustering evolving data using kernel-based methods
• A Cognition-Affect Integrated Model of Emotion
• Leveraging Evolution Dynamics to Generate Benchmark Complex Networks with Community Structures
• A Spatiotemporal Adaptive Local Search Method for Tracking Congestion Propagation in Dynamic Networks
• Cooperative Data Offload in Opportunistic Networks: From Mobile Devices to Infrastructure
• Detectability threshold in weighted modular networks
• Opinion Divergence Reveals the Hierarchical and Overlapping Community Structure in Networks
• Learning Resolution Parameters for Graph Clustering
• A framework for community detection in heterogeneous multi-relational networks
• Overlapping Communities Detection via Measure Space Embedding
• On Equivalence of Likelihood Maximization of Stochastic Block Model and Constrained Nonnegative Matrix Factorization
• Generating online social networks based on socio-demographic attributes
• An Efficient homophilic model and Algorithms for Community Detection using Nash Dynamics
• Approximate Conditional Sampling for Pattern Detection in Weighted Networks
• Learning dynamic representations of the functional connectome in neurobiological networks
• Ensemble-based Overlapping Community Detection using Disjoint Community Structures
• Optimization in large graphs: Toward a better future?
• Improving Data Forwarding in Mobile Social Networks with Infrastructure Support: A Space-Crossing Community Approach
• Spiking label propagation for community detection
• Effective Resistance-based Germination of Seed Sets for Community Detection
• Mining Application-aware Community Organization with Expanded Feature Subspaces from Concerned Attributes in Social Networks
• On Varying Topology of Complex Networks and Performance Limitations of Community Detection Algorithms
• From Community Detection to Community Deception
• Generating realistic scaled complex networks