# Network histograms and universality of blockmodel approximation

arXiv: https://arxiv.org/abs/1312.5306 · HTML: https://mlsanity.com/paper/1312.5306/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Dec 2013.

## Built on by (most cited first, 20 of 20)

- [Joint Network Topology Inference via a Shared Graphon Model](https://mlsanity.com/paper/2209.08223/) (2022)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths](https://mlsanity.com/paper/2112.00183/) (2021)
- [Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection](https://mlsanity.com/paper/2210.09186/) (2022)
- [Transfer Learning for Latent Variable Network Models](https://mlsanity.com/paper/2406.03437/) (2024)
- [Theoretical analysis and computation of the sample Frechet mean for sets of large graphs based on spectral information](https://mlsanity.com/paper/2201.05923/) (2022)
- [Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels](https://mlsanity.com/paper/2304.03590/) (2023)
- [Network two-sample test for block models](https://mlsanity.com/paper/2406.06014/) (2024)
- [Modularity maximisation for graphons](https://mlsanity.com/paper/2101.00503/) (2021)
- [Systematic assessment of the quality of fit of the stochastic block model for empirical networks](https://mlsanity.com/paper/2201.01658/) (2022)
- [Graphon-aided Joint Estimation of Multiple Graphs](https://mlsanity.com/paper/2202.05686/) (2022)
- [Higher-order accurate two-sample network inference and network hashing](https://mlsanity.com/paper/2208.07573/) (2022)
- [When does the mean network capture the topology of a sample of networks?](https://mlsanity.com/paper/2408.03461/) (2024)
- [Approximate Fr'echet Mean for Data Sets of Sparse Graphs](https://mlsanity.com/paper/2105.04062/) (2021)
- [Adversarial contamination of networks in the setting of vertex nomination: a new trimming method](https://mlsanity.com/paper/2208.09710/) (2022)
- [Estimation of the Sample Frechet Mean: A Convolutional Neural Network Approach](https://mlsanity.com/paper/2210.07401/) (2022)
- [Estimating Dyadic Treatment Effects with Unknown Confounders](https://mlsanity.com/paper/2405.16547/) (2024)
- [The Spectral Barycentre of a Set of Graphs with Community Structure](https://mlsanity.com/paper/2502.00038/) (2025)
- [Network Learning with Semi-relaxed Gromov-Wasserstein](https://mlsanity.com/paper/2606.02223/) (2026)
- [Attention Graphons: A Graph Limit Perspective on Graph Transformers](https://mlsanity.com/paper/2609.35620/) (2026)

## Abstract (arXiv)

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.