Network histograms and universality of blockmodel approximation
arXiv:1312.5306 · doi:10.1073/pnas.1400374111
Abstract
In this article we introduce the network histogram: a statistical summary of network interactions, to be used as a tool for exploratory data analysis. A network histogram is obtained by fitting a stochastic blockmodel to a single observation of a network dataset. Blocks of edges play the role of histogram bins, and community sizes that of histogram bandwidths or bin sizes. Just as standard histograms allow for varying bandwidths, different blockmodel estimates can all be considered valid representations of an underlying probability model, subject to bandwidth constraints. Here we provide methods for automatic bandwidth selection, by which the network histogram approximates the generating mechanism that gives rise to exchangeable random graphs. This makes the blockmodel a universal network representation for unlabeled graphs. With this insight, we discuss the interpretation of network communities in light of the fact that many different community assignments can all give an equally valid representation of such a network. To demonstrate the fidelity-versus-interpretability tradeoff inherent in considering different numbers and sizes of communities, we analyze two publicly available networks - political weblogs and student friendships - and discuss how to interpret the network histogram when additional information related to node and edge labeling is present.
arXiv comment27 pages, 4 figures; revised version with link to software
References in corpus (12)
- Community structure in social and biological networks
- Stochastic blockmodels and community structure in networks
- Mixed membership stochastic blockmodels
- Spectral redemption: clustering sparse networks
- Spectral clustering and the high-dimensional stochastic blockmodel
- Matrix estimation by Universal Singular Value Thresholding
- Consistency of community detection in networks under degree-corrected stochastic block models
- Stochastic blockmodels with growing number of classes
- Community extraction for social networks
- Nonparametric graphon estimation
- Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
- Co-clustering separately exchangeable network data
Cited by in corpus (45)
- Networks beyond pairwise interactions: structure and dynamics
- Rate-optimal graphon estimation
- Bayesian stochastic blockmodeling
- A Clarified Typology of Core-Periphery Structure in Networks
- On a 'Two Truths' Phenomenon in Spectral Graph Clustering
- Optimal Estimation and Completion of Matrices with Biclustering Structures
- Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
- A Consistent Histogram Estimator for Exchangeable Graph Models
- Statistical Inference, Learning and Models in Big Data
- Community Detection in Bipartite Networks with Stochastic Blockmodels
- A testing based extraction algorithm for identifying significant communities in networks
- Phase Transitions in Spectral Community Detection
- A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference
- Universality of the stochastic block model
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- Statistical inference for network samples using subgraph counts
- Estimating network edge probabilities by neighborhood smoothing
- Interplay between -core and community structure in complex networks
- A unified data representation theory for network visualization, ordering and coarse-graining
- Robust Vertex Classification
- Joint Network Topology Inference via a Shared Graphon Model
- Generalized linear models with low rank effects for network data
- Hierarchical community detection by recursive partitioning
- Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
- EM-Based Smooth Graphon Estimation Using Bayesian and Spline-Based Approaches
- Topology reveals universal features for network comparison
- Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
- Spectral clustering in the dynamic stochastic block model
- On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Models
- An Annotated Graph Model with Differential Degree Heterogeneity for Directed Networks
- Maximum Likelihood Estimation of Sparse Networks with Missing Observations
- On the Consistency of the Likelihood Maximization Vertex Nomination Scheme: Bridging the Gap Between Maximum Likelihood Estimation and Graph Matching
- Clustering of Diverse Multiplex Networks
- Null models for multi-optimized large-scale network structures
- Systematic assessment of the quality of fit of the stochastic block model for empirical networks
- Nonparametric Two-Sample Test for Networks Using Joint Graphon Estimation
- Strength of Connections in a Random Graph: Definition, Characterization, and Estimation
- Mixture Models and Networks -- Overview of Stochastic Blockmodelling
- Nonparametric regression for multiple heterogeneous networks
- Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels
- Approximate Fréchet Mean for Data Sets of Sparse Graphs
- Robustness on Networks
- Can smooth graphons in several dimensions be represented by smooth graphons on ?
- Tractably Modelling Dependence in Networks Beyond Exchangeability
- Two-sample Testing on Latent Distance Graphs With Unknown Link Functions