Evaluating Overfit and Underfit in Models of Network Community Structure

Abstract

A common data mining task on networks is community detection, which seeks an unsupervised decomposition of a network into structural groups based on statistical regularities in the network's connectivity. Although many methods exist, the No Free Lunch theorem for community detection implies that each makes some kind of tradeoff, and no algorithm can be optimal on all inputs. Thus, different algorithms will over or underfit on different inputs, finding more, fewer, or just different communities than is optimal, and evaluation methods that use a metadata partition as a ground truth will produce misleading conclusions about general accuracy. Here, we present a broad evaluation of over and underfitting in community detection, comparing the behavior of 16 state-of-the-art community detection algorithms on a novel and structurally diverse corpus of 406 real-world networks. We find that (i) algorithms vary widely both in the number of communities they find and in their corresponding composition, given the same input, (ii) algorithms can be clustered into distinct high-level groups based on similarities of their outputs on real-world networks, and (iii) these differences induce wide variation in accuracy on link prediction and link description tasks. We introduce a new diagnostic for evaluating overfitting and underfitting in practice, and use it to roughly divide community detection methods into general and specialized learning algorithms. Across methods and inputs, Bayesian techniques based on the stochastic block model and a minimum description length approach to regularization represent the best general learning approach, but can be outperformed under specific circumstances. These results introduce both a theoretically principled approach to evaluate over and underfitting in models of network community structure and a realistic benchmark by which new methods may be evaluated and compared.

arXiv comment22 pages, 13 figures, 3 tables

References in corpus (44)

• Fast unfolding of communities in large networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Maps of random walks on complex networks reveal community structure
• Resolution limit in community detection
• Link Prediction in Complex Networks: A Survey
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• Finding statistically significant communities in networks
• Missing and spurious interactions and the reconstruction of complex networks
• Mixed membership stochastic blockmodels
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• Extracting the hierarchical organization of complex systems
• The ground truth about metadata and community detection in networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Highly comparative time-series analysis: The empirical structure of time series and their methods
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• A Bayesian Approach to Network Modularity
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Community detection in networks: Structural communities versus ground truth
• Stochastic blockmodels with growing number of classes
• Modeling homophily and stochastic equivalence in symmetric relational data
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Limited resolution in complex network community detection with Potts model approach
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Estimating the number of communities in a network
• Bayesian stochastic blockmodeling
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Guaranteed clustering and biclustering via semidefinite programming
• Consistencies and inconsistencies between model selection and link prediction in networks
• Improved Graph Clustering
• Estimating the number of communities in networks by spectral methods
• Assembling thefacebook: Using heterogeneity to understand online social network assembly
• Cross-validation estimate of the number of clusters in a network
• Spectral Clustering of Graphs with the Bethe Hessian
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Comparative analysis on the selection of number of clusters in community detection
• Comparison of Cross-Validation Methods for Stochastic Block Models
• A Tractable Fully Bayesian Method for the Stochastic Block Model

Cited by in corpus (36)

• Simplicial Closure and higher-order link prediction
• Consistency and differences between centrality measures across distinct classes of networks
• On community structure in complex networks: challenges and opportunities
• Stacking Models for Nearly Optimal Link Prediction in Complex Networks
• Statistical inference of assortative community structures
• Community structure: A comparative evaluation of community detection methods
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Link prediction with hyperbolic geometry
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Revealing consensus and dissensus between network partitions
• Disentangling homophily, community structure and triadic closure in networks
• Universality of the stochastic block model
• Meta-validation of bipartite network projections
• Mapping flows on sparse networks with missing links
• Mapping flows on weighted and directed networks with incomplete observations
• Micro, Meso, Macro: the effect of triangles on communities in networks
• Normalised Degree Variance
• Asymptotic resolution bounds of generalized modularity and multi-scale community detection
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Latent Poisson models for networks with heterogeneous density
• Explaining the emergence of complex networks through log-normal fitness in a Euclidean node similarity space
• Dual communities in spatial networks
• Exact and rapid linear clustering of networks with dynamic programming
• Stochastic Block Models are a Discrete Surface Tension
• Robust Deep Signed Graph Clustering via Weak Balance Theory
• The Atlas for the Aspiring Network Scientist
• Discovering Block Structure in Networks
• Single-trajectory map equation
• Overcoming Bias in Community Detection Evaluation
• Thermodynamics of the Minimum Description Length on Community Detection
• Systematic assessment of the quality of fit of the stochastic block model for empirical networks
• Opportunities and challenges in partitioning the graph measure space of real-world networks
• On a scalable entropic breaching of the overfitting barrier in machine learning
• Exploring complex networks with the ICON R package
• Effective Model Integration Algorithm for Improving Link and Sign Prediction in Complex Networks
• Domain matters: Towards domain-informed evaluation for link prediction