Community detection in networks: Structural communities versus ground truth

Abstract

Algorithms to find communities in networks rely just on structural information and search for cohesive subsets of nodes. On the other hand, most scholars implicitly or explicitly assume that structural communities represent groups of nodes with similar (non-topological) properties or functions. This hypothesis could not be verified, so far, because of the lack of network datasets with information on the classification of the nodes. We show that traditional community detection methods fail to find the metadata groups in many large networks. Our results show that there is a marked separation between structural communities and metadata groups, in line with recent findings. That means that either our current modeling of community structure has to be substantially modified, or that metadata groups may not be recoverable from topology alone.

21 pages, 19 figures

References in corpus (16)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• The Dynamics of Viral Marketing
• Link communities reveal multiscale complexity in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Finding overlapping communities in networks by label propagation
• Social Structure of Facebook Networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Mixing local and global information for community detection in large networks

Cited by in corpus (66)

• Community detection in networks: A user guide
• Social physics
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• The ground truth about metadata and community detection in networks
• Structure and inference in annotated networks
• Which type of citation analysis generates the most accurate taxonomy of scientific and technical knowledge?
• Community detection in node-attributed social networks: a survey
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• 20 years of network community detection
• Diversity of meso-scale architecture in human and non-human connectomes
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Clustering scientific publications based on citation relations: A systematic comparison of different methods
• Bursty Human Dynamics
• Bayesian stochastic blockmodeling
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• Local dominance unveils clusters in networks
• Community structure: A comparative evaluation of community detection methods
• IEDC: An Integrated Approach for Overlapping and Non-overlapping Community Detection
• Detecting global bridges in networks
• Immunization Strategies Based on the Overlapping Nodes in Networks with Community Structure
• Network structure, metadata and the prediction of missing nodes and annotations
• Mixed Membership Estimation for Social Networks
• Codon Bias Patterns of $E.coli$'s Interacting Proteins
• Nine Quick Tips for Analyzing Network Data
• Different approaches to community detection
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Memetic search for overlapping topics based on a local evaluation of link communities
• Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
• Effective and Scalable Clustering on Massive Attributed Graphs
• Detection of Community Structures in Networks with Nodal Features based on Generative Probabilistic Approach
• Multilayer Networks for Text Analysis with Multiple Data Types
• Ground truth? Concept-based communities versus the external classification of physics manuscripts
• Mapping flows on weighted and directed networks with incomplete observations
• Intermediacy of publications
• Growing hyperbolic networks beyond two dimensions: the generalised popularity-similarity optimisation model
• Multiple phases in modularity-based community detection
• Discovering Communication Pattern Shifts in Large-Scale Labeled Networks using Encoder Embedding and Vertex Dynamics
• Stylized facts in social networks: Community-based static modeling
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Graph Generators: State of the Art and Open Challenges
• Structure constrained by metadata in networks of chess players
• Generalized Markov stability of network communities
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure
• Exploring triad-rich substructures by graph-theoretic characterizations in complex networks
• Uncovering Complex Overlapping Pattern of Communities in Large-scale Social Networks
• Clustering attributed graphs: models, measures and methods
• Modular decomposition of Markov chain: detecting hierarchical organization of pervasive communities
• The Atlas for the Aspiring Network Scientist
• EC-SBM Synthetic Network Generator
• Fast community structure local uncovering by independent vertex-centred process
• Latent Geometry Inspired Graph Dissimilarities Enhance Affinity Propagation Community Detection in Complex Networks
• Detecting Overlapping Link Communities by Finding Local Minima of a Cost Function with a Memetic Algorithm. Part 1: Problem and Method
• Router-level community structure of the Internet Autonomous Systems
• Efficient Detection of Communities with Significant Overlaps in Networks: Partial Community Merger Algorithm
• Quantifying metadata relevance to network block structure using description length
• Leveraging Evolution Dynamics to Generate Benchmark Complex Networks with Community Structures
• Overcoming Bias in Community Detection Evaluation
• Community detection algorithm evaluation with ground-truth data
• Homophilic organization of egocentric communities in ICT services
• Error-Correcting Decoders for Communities in Networks
• Optimization in large graphs: Toward a better future?
• Correlation Analysis of Nodes Identifies Real Communities in Networks
• Prior Signal Editing for Graph Filter Posterior Fairness Constraints
• Block-corrected Modularity for Community Detection
• Improving Community Detection by Mining Social Interactions