The ground truth about metadata and community detection in networks

Abstract

Across many scientific domains, there is a common need to automatically extract a simplified view or coarse-graining of how a complex system's components interact. This general task is called community detection in networks and is analogous to searching for clusters in independent vector data. It is common to evaluate the performance of community detection algorithms by their ability to find so-called "ground truth" communities. This works well in synthetic networks with planted communities because such networks' links are formed explicitly based on those known communities. However, there are no planted communities in real world networks. Instead, it is standard practice to treat some observed discrete-valued node attributes, or metadata, as ground truth. Here, we show that metadata are not the same as ground truth, and that treating them as such induces severe theoretical and practical problems. We prove that no algorithm can uniquely solve community detection, and we prove a general No Free Lunch theorem for community detection, which implies that there can be no algorithm that is optimal for all possible community detection tasks. However, community detection remains a powerful tool and node metadata still have value so a careful exploration of their relationship with network structure can yield insights of genuine worth. We illustrate this point by introducing two statistical techniques that can quantify the relationship between metadata and community structure for a broad class of models. We demonstrate these techniques using both synthetic and real-world networks, and for multiple types of metadata and community structure.

27 pages, 10 figures, 11 tables

References in corpus (11)

• Cooperative Game Theory Approaches for Network Partitioning
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• Phase transition in the detection of modules in sparse networks
• Subnetwork hierarchies of biochemical pathways
• Community detection in networks: Structural communities versus ground truth
• Maximizing Modularity is hard
• Clique Graphs and Overlapping Communities
• Network structure, metadata and the prediction of missing nodes and annotations
• Supervised Blockmodelling

Cited by in corpus (121)

• Community Discovery in Dynamic Networks: a Survey
• Community detection in node-attributed social networks: a survey
• On community structure in complex networks: challenges and opportunities
• 20 years of network community detection
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Diversity of meso-scale architecture in human and non-human connectomes
• The many facets of community detection in complex networks
• Stacking Models for Nearly Optimal Link Prediction in Complex Networks
• Progresses and Challenges in Link Prediction
• Bayesian stochastic blockmodeling
• Element-centric clustering comparison unifies overlaps and hierarchy
• Inference of hyperedges and overlapping communities in hypergraphs
• Multiscale mixing patterns in networks
• A Clarified Typology of Core-Periphery Structure in Networks
• Measuring Node Contribution to Community Structure with Modularity Vitality
• Community Detection in Large Hypergraphs
• On a 'Two Truths' Phenomenon in Spectral Graph Clustering
• Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering
• Local dominance unveils clusters in networks
• Community detection with node attributes in multilayer networks
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Community structure: A comparative evaluation of community detection methods
• Using text analysis to quantify the similarity and evolution of scientific disciplines
• Community detection in networks without observing edges
• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Network community detection using modularity density measures
• Adaptive Modularity Maximization via Edge Weighting Scheme
• Community detection using boundary nodes in complex networks
• Cross-validation estimate of the number of clusters in a network
• Spectral Detection of Simplicial Communities via Hodge Laplacians
• Universality of the stochastic block model
• Different approaches to community detection
• Synwalk -- Community Detection via Random Walk Modelling
• Hierarchical community structure in networks
• Network constraints on the mixing patterns of binary node metadata
• Meta-validation of bipartite network projections
• Demarcating Geographic Regions using Community Detection in Commuting Networks with Significant Self-Loops
• A Unified Method of Detecting Core-Periphery Structure and Community Structure in Networks
• Blind identification of stochastic block models from dynamical observations
• Memetic search for overlapping topics based on a local evaluation of link communities
• Detection of Community Structures in Networks with Nodal Features based on Generative Probabilistic Approach
• Generalized Rich-Club Ordering in Networks
• A Map Equation with Metadata: Varying the Role of Attributes in Community Detection
• Mapping flows on sparse networks with missing links
• Multiplex Communities and the Emergence of International Conflict
• Structure and inference in hypergraphs with node attributes
• Generative model for reciprocity and community detection in networks
• Modularity and Projection of Bipartite Networks
• Mapping flows on weighted and directed networks with incomplete observations
• Comparative analysis on the selection of number of clusters in community detection
• Micro, Meso, Macro: the effect of triangles on communities in networks
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
• Asymptotic resolution bounds of generalized modularity and multi-scale community detection
• Regularized Stochastic Block Model for robust community detection in complex networks
• Assortative and preferential attachment lead to core-periphery networks
• Random Graphs with Prescribed $K$-Core Sequences: A New Null Model for Network Analysis
• Multiresolution Consensus Clustering in Networks
• Reduced network extremal ensemble learning (RenEEL) scheme for community detection in complex networks
• State aggregations in Markov chains and block models of networks
• Robustness of community structure under edge addition
• PyGenStability: Multiscale community detection with generalized Markov Stability
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Quantifying agent impacts on contact sequences in social interactions
• Pairwise Covariates-adjusted Block Model for Community Detection
• An Exact No Free Lunch Theorem for Community Detection
• On community structure validation in real networks
• MONET: Debiasing Graph Embeddings via the Metadata-Orthogonal Training Unit
• Normalized mutual information is a biased measure for classification and community detection
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Generalized Markov stability of network communities
• Resolution Limits for Detecting Community Changes in Multilayer Networks
• Decoding communities in networks
• Flow-based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• Entrograms and coarse graining of dynamics on complex networks
• Structured networks and coarse-grained descriptions: a dynamical perspective
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• Metrics matter in community detection
• Identifying bias in cluster quality metrics
• Making Communities Show Respect for Order
• Stochastic Block Models are a Discrete Surface Tension
• Identifying robust features of community structure in complex networks
• Detectability of Macroscopic Structures in Directed Asymmetric Stochastic Block Model
• Uncovering Complex Overlapping Pattern of Communities in Large-scale Social Networks
• Simulating systematic bias in attributed social networks and its effect on rankings of minority nodes
• Network Dependence Testing via Diffusion Maps and Distance-Based Correlations
• Community Detection in networks by Dynamical Optimal Transport Formulation
• The Atlas for the Aspiring Network Scientist
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
• GVE-Louvain: Fast Louvain Algorithm for Community Detection in Shared Memory Setting
• Detectability of hierarchical communities in networks
• Optimal timescale for community detection in growing networks
• Modular decomposition of Markov chain: detecting hierarchical organization of pervasive communities
• A General Definition of Network Communities and the Corresponding Detection Algorithm
• From reductionism to realism: Holistic mathematical modelling for complex biological systems
• Node metadata can produce predictability transitions in network inference problems
• Ollivier Ricci-flow on weighted graphs
• Sequential locality of graphs and its hypothesis testing
• The modular organization of human anatomical brain networks: Accounting for the cost of wiring
• Edge-cuts Optimized for Average Weight: a new alternative to Ford and Fulkerson
• Random walk based snapshot clustering for detecting community dynamics in temporal networks
• Learning common structures in a collection of networks. An application to food webs
• Simultaneous prediction and community detection for networks with application to neuroimaging
• Synthetic graphs for link prediction benchmarking
• Community Detection in the Hyperbolic Space
• The Automatic Quasi-clique Merger algorithm (AQCM)
• Overcoming Bias in Community Detection Evaluation
• Thermodynamics of the Minimum Description Length on Community Detection
• From communities to interpretable network and word embedding: an unified approach
• Skeleton coupling: a novel interlayer mapping of community evolution in temporal networks
• Quantifying metadata relevance to network block structure using description length
• Inference and Visualization of Community Structure in Attributed Hypergraphs Using Mixed-Membership Stochastic Block Models
• Testing Alignment of Node Attributes with Network Structure Through Label Propagation
• Prior Signal Editing for Graph Filter Posterior Fairness Constraints
• On a scalable entropic breaching of the overfitting barrier in machine learning
• Improving Community Detection by Mining Social Interactions
• Discrimination universally determines reconstruction of multiplex networks
• Binomial Tails for Community Analysis
• Learning Resolution Parameters for Graph Clustering
• Error-Correcting Decoders for Communities in Networks
• Block-corrected Modularity for Community Detection