Unbiased sampling of network ensembles
From MaRDI portal
Abstract: Sampling random graphs with given properties is a key step in the analysis of networks, as random ensembles represent basic null models required to identify patterns such as communities and motifs. An important requirement is that the sampling process is unbiased and efficient. The main approaches are microcanonical, i.e. they sample graphs that match the enforced constraints exactly. Unfortunately, when applied to strongly heterogeneous networks (like most real-world examples), the majority of these approaches become biased and/or time-consuming. Moreover, the algorithms defined in the simplest cases, such as binary graphs with given degrees, are not easily generalizable to more complicated ensembles. Here we propose a solution to the problem via the introduction of a "Maximize and Sample" ("Max & Sam" for short) method to correctly sample ensembles of networks where the constraints are `soft', i.e. realized as ensemble averages. Our method is based on exact maximum-entropy distributions and is therefore unbiased by construction, even for strongly heterogeneous networks. It is also more computationally efficient than most microcanonical alternatives. Finally, it works for both binary and weighted networks with a variety of constraints, including combined degree-strength sequences and full reciprocity structure, for which no alternative method exists. Our canonical approach can in principle be turned into an unbiased microcanonical one, via a restriction to the relevant subset. Importantly, the analysis of the fluctuations of the constraints suggests that the microcanonical and canonical versions of all the ensembles considered here are not equivalent. We show various real-world applications and provide a code implementing all our algorithms.
Recommendations
Cites work
- A critical point for random graphs with a given degree sequence
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- A sequential importance sampling algorithm for generating random graphs with prescribed degrees
- Analytical maximum-likelihood method to detect patterns in real networks
- Connected components in random graphs with given expected degree sequences
- Constrained Markovian dynamics of random graphs
- Constructing and sampling directed graphs with given degree sequences
- Dynamical Processes on Complex Networks
- Networks. An introduction.
- The average distances in random graphs with given expected degrees
Cited in
(16)- Volume of the steady-state space of financial flows in a monetary stock-flow-consistent model
- Is breaking of ensemble equivalence monotone in the number of constraints?
- Covariance structure behind breaking of ensemble equivalence in random graphs
- Asymptotic equivalence of probability measures and stochastic processes
- Graph sampling for Internet topologies using normalized Laplacian spectral features
- Phases of small worlds: a mean field formulation
- Ensemble nonequivalence in random graphs with modular structure
- Switching edges to randomize networks : What goes wrong and how to fix it
- Randomized reference models for temporal networks
- Multilayer overlaps and correlations in the bank-firm credit network of Spain
- Analytical maximum-likelihood method to detect patterns in real networks
- Exact sampling of graphs with prescribed degree correlations
- Reconstructing production networks using machine learning
- Maximum Entropy Distributions with Applications to Graph Simulation
- Introduction to correlation networks: interdisciplinary approaches beyond thresholding
- Bootstrapping on undirected binary networks via statistical mechanics
This page was built for publication: Unbiased sampling of network ensembles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3387646)
