Unbiased sampling of network ensembles

Squartini, Tiziano; Mastrandrea, Rossana; Garlaschelli, Diego
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. A key requirement is that the sampling process is unbiased and efficient. The main approaches are microcanonical, i.e. they sample graphs that exactly match the enforced constraints. Unfortunately, when applied to strongly heterogeneous networks (including most real-world graphs), 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') method to correctly sample ensembles of networks where the constraints are `soft' i.e. they are realized as ensemble averages. Being based on exact maximum-entropy distributions, our approach is 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-strengths sequences and full reciprocity structure, for which no alternative method exists. Our method can also be turned into a microcanonical one, via a restriction to the relevant subset. We show various applications to real-world networks and provide a code implementing all our algorithms.
Year:
2014
Type of Publication:
Article
Keywords:
complex networks; ensemble nonequivalence; maximum entropy principle; null models of graphs; sampling network ensembles
Journal:
New Journal of Physics
Volume:
17
Number:
2
Pages:
23052
ISSN:
1367-2630
DOI:
10.1088/1367-2630/17/2/023052
Hits: 888

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information