The entropy of randomized network ensembles

Assessing whether a given network is typical or atypical for a random-network ensemble (i.e., network-ensemble comparison) has widespread applications ranging from null-model selection and hypothesis testing to clustering and classifying networks. We develop a framework for network-ensemble comparison by subjecting the network to stochastic rewiring. We study two rewiring processes, uniform and degree-preserved rewiring, which yield random-network ensembles that converge to t...

Stochastic blockmodels are generative network models where the vertices are separated into discrete groups, and the probability of an edge existing between two vertices is determined solely by their group membership. In this paper, we derive expressions for the entropy of stochastic blockmodel ensembles. We consider several ensemble variants, including the traditional model as well as the newly introduced degree-corrected version [Karrer et al. Phys. Rev. E 83, 016107 (2011)]...

Statistical ensembles of networks, i.e., probability spaces of all networks that are consistent with given aggregate statistics, have become instrumental in the analysis of complex networks. Their numerical and analytical study provides the foundation for the inference of topological patterns, the definition of network-analytic measures, as well as for model selection and statistical hypothesis testing. Contributing to the foundation of these data analysis techniques, in this...

Why are most empirical networks, with the prominent exception of social ones, generically degree-degree anticorrelated, i.e. disassortative? With a view to answering this long-standing question, we define a general class of degree-degree correlated networks and obtain the associated Shannon entropy as a function of parameters. It turns out that the maximum entropy does not typically correspond to uncorrelated networks, but to either assortative (correlated) or disassortative ...

In order to detect patterns in real networks, randomized graph ensembles that preserve only part of the topology of an observed network are systematically used as fundamental null models. However, their generation is still problematic. The existing approaches are either computationally demanding and beyond analytic control, or analytically accessible but highly approximate. Here we propose a solution to this long-standing problem by introducing an exact and fast method that a...

Entropic measures of complexity are able to quantify the information encoded in complex network structures. Several entropic measures have been proposed in this respect. Here we study the relation between the Shannon entropy and the Von Neumann entropy of networks with a given expected degree sequence. We find in different examples of network topologies that when the degree distribution contains some heterogeneity, an intriguing correlation emerges between the two entropies. ...

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 example...

In this paper we describe the emergence of scale-free degree distributions from statistical mechanics principles. We define an energy associated to a degree sequence as the logarithm of the number of indistinguishable simple networks it is possible to draw given the degree sequence. Keeping fixed the total number of nodes and links, we show that the energy of scale-free distribution is much higher than the energy associated to the degree sequence of regular random graphs. Thi...

We present a method to construct a network null-model based on the maximum entropy principle and where the restrictions that the rich-club and the degree sequence impose are conserved. We show that the probability that two nodes share a link can be described with a simple probability function. The null-model closely approximates the assortative properties of the network.

Complex networks are now being studied in a wide range of disciplines across science and technology. In this paper we propose a method by which one can probe the properties of experimentally obtained network data. Rather than just measuring properties of a network inferred from data, we aim to ask how typical is that network? What properties of the observed network are typical of all such scale free networks, and which are peculiar? To do this we propose a series of methods t...