Network histograms and universality of blockmodel approximation

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.

27 pages, 4 figures; revised version with link to software

References in corpus (2)

• Stochastic blockmodels and community structure in networks
• Stochastic blockmodel approximation of a graphon: Theory and consistent estimation

Cited by in corpus (44)

• 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
• 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 $k$-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
• On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Models
• Spectral clustering in the dynamic stochastic block model
• An Annotated Graph Model with Differential Degree Heterogeneity for Directed Networks
• Clustering of Diverse Multiplex 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
• 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
• Mixture Models and Networks -- Overview of Stochastic Blockmodelling
• Strength of Connections in a Random Graph: Definition, Characterization, and Estimation
• 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 $[0,1]$?
• Tractably Modelling Dependence in Networks Beyond Exchangeability
• Two-sample Testing on Latent Distance Graphs With Unknown Link Functions