Compressing network populations with modal networks reveals structural diversity
arXiv:2209.13827 · doi:10.1038/s42005-023-01270-5
Abstract
Analyzing relational data consisting of multiple samples or layers involves critical challenges: How many networks are required to capture the variety of structures in the data? And what are the structures of these representative networks? We describe efficient nonparametric methods derived from the minimum description length principle to construct the network representations automatically. The methods input a population of networks or a multilayer network measured on a fixed set of nodes and output a small set of representative networks together with an assignment of each network sample or layer to one of the representative networks. We identify the representative networks and assign network samples to them with an efficient Monte Carlo scheme that minimizes our description length objective. For temporally ordered networks, we use a polynomial time dynamic programming approach that restricts the clusters of network layers to be temporally contiguous. These methods recover planted heterogeneity in synthetic network populations and identify essential structural heterogeneities in global trade and fossil record networks. Our methods are principled, scalable, parameter-free, and accommodate a wide range of data, providing a unified lens for exploratory analyses and preprocessing large sets of network samples.
References in corpus (22)
- Multilayer Networks
- High-resolution measurements of face-to-face contact patterns in a primary school
- An information-theoretic framework for resolving community structure in complex networks
- Layer aggregation and reducibility of multilayer interconnected networks
- An Algorithm for Optimal Partitioning of Data on an Interval
- Network structure from rich but noisy data
- Clustering Network Layers With the Strata Multilayer Stochastic Block Model
- Hypergraph reconstruction from network data
- Estimating network structure from unreliable measurements
- Nonparametric Bayes Modeling of Populations of Networks
- Cross-Entropy Clustering
- Bayesian inference of network structure from unreliable data
- Mapping flows on hypergraphs
- Joint Embedding of Graphs
- Merge-split Markov chain Monte Carlo for community detection
- Inference for multiple heterogeneous networks with a common invariant subspace
- Representative community divisions of networks
- Spatial regionalization based on optimal information compression
- Large-scale network motif analysis using compression
- Model-based clustering for populations of networks
- Clustering of heterogeneous populations of networks
- Exact and rapid linear clustering of networks with dynamic programming