Unbiased sampling of network ensembles

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.

arXiv commentMatLab code available at http://www.mathworks.it/matlabcentral/fileexchange/46912-max-sam-package-zip

References in corpus (27)

• Community detection in graphs
• Random graphs with arbitrary degree distributions and their applications
• Specificity and stability in topology of protein networks
• Prediction and predictability of global epidemics: the role of the airline transportation network
• Generation of uncorrelated random scale-free networks
• The statistical mechanics of networks
• Entropy measures for complex networks: Toward an information theory of complex topologies
• Cut-offs and finite size effects in scale-free networks
• The entropy of randomized network ensembles
• Analytical maximum-likelihood method to detect patterns in real networks
• A fitness model for the Italian Interbank Money Market
• Early-warning signals of topological collapse in interbank networks
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• Reciprocity of weighted networks
• Generalized Bose-Fermi statistics and structural correlations in weighted networks
• Randomizing world trade. I. A binary network analysis
• Randomizing world trade. II. A weighted network analysis
• Enhanced reconstruction of weighted networks from strengths and degrees
• Gibbs entropy of networks ensembles by cavity methods
• Entropies of complex networks with hierarchically constrained topologies
• Reconstructing the world trade multiplex: the role of intensive and extensive biases
• The weighted random graph model
• Null Models of Economic Networks: The Case of the World Trade Web
• Constrained Markovian dynamics of random graphs
• Multi-species grandcanonical models for networks with reciprocity
• Triadic motifs and dyadic self-organization in the World Trade Network
• Fluctuation-dissipation relations for complex networks

Cited by in corpus (43)

• The Statistical Physics of Real-World Networks
• Quantifying randomness in real networks
• Randomizing bipartite networks: the case of the World Trade Web
• Breaking of ensemble equivalence in networks
• Clustering implies geometry in networks
• Detecting early signs of the 2007-2008 crisis in the world trade
• Reconstructing commuters network using machine learning and urban indicators
• Breaking the spell of nestedness
• Randomized reference models for temporal networks
• Exact sampling of graphs with prescribed degree correlations
• Reconstructing networks
• Criminal Networks Analysis in Missing Data scenarios through Graph Distances
• Configuration model for correlation matrices preserving the node strength
• A faster horse on a safer trail: generalized inference for the efficient reconstruction of weighted networks
• Multiplexity and multireciprocity in directed multiplexes
• Ensemble nonequivalence in random graphs with modular structure
• Introduction to correlation networks: Interdisciplinary approaches beyond thresholding
• Centrality anomalies in complex networks as a result of model over-simplification
• The ambiguity of nestedness under soft and hard constraints
• Social dynamics of financial networks
• Strong ensemble nonequivalence in systems with local constraints
• Structural measures of similarity and complementarity in complex networks
• Pattern detection in bipartite networks: a review of terminology, applications and methods
• Weighted hypersoft configuration model
• Covariance structure behind breaking of ensemble equivalence in random graphs
• Analytical Formulation of the Block-Constrained Configuration Model
• Thermodynamics of network model fitting with spectral entropies
• Entropy of labeled versus unlabeled networks
• Ensemble nonequivalence and Bose-Einstein condensation in weighted networks
• The Fitness-Corrected Block Model, or how to create maximum-entropy data-driven spatial social networks
• Entropy of microcanonical finite-graph ensembles
• Phases of Small Worlds: A Mean Field Formulation
• Asymptotic equivalence of probability measures and stochastic processes
• Description length of canonical and microcanonical models
• Volume of the steady-state space of financial flows in a monetary stock-flow-consistent model
• Higher-order null models as a lens for social systems
• An impossibility result for Markov Chain Monte Carlo sampling from micro-canonical bipartite graph ensembles
• Linking Through Time: Memory-Enhanced Community Discovery in Temporal Networks
• Multilayer Network Analysis of European Regional Flows
• Deterministic, quenched and annealed parameter estimation for heterogeneous network models
• Gravity models of networks: integrating maximum-entropy and econometric approaches
• Local phase transitions in a model of multiplex networks with heterogeneous degrees and inter-layer coupling
• Italian Twitter semantic network during the Covid-19 epidemic