March 24, 2014
The entropy of network ensembles characterizes the amount of information encoded in the network structure, and can be used to quantify network complexity, and the relevance of given structural properties observed in real network datasets with respect to a random hypothesis. In many real networks the degrees of individual nodes are not fixed but change in time, while their statistical properties, such as the degree distribution, are preserved. Here we characterize the distribution of entropy of random networks with given degree sequences, where each degree sequence is drawn randomly from a given degree distribution. We show that the leading term of the entropy of scale-free network ensembles depends only on the network size and average degree, and that entropy is self-averaging, meaning that its relative variance vanishes in the thermodynamic limit. We also characterize large fluctuations of entropy that are fully determined by the average degree in the network. Finally, above a certain threshold, large fluctuations of the average degree in the ensemble can lead to condensation, meaning that a single node in a network of size~$N$ can attract $O(N)$ links.
Similar papers 1
February 20, 2008
In this paper we generalize the concept of random networks to describe networks with non trivial features by a statistical mechanics approach. This framework is able to describe ensembles of undirected, directed as well as weighted networks. These networks might have not trivial community structure or, in the case of networks embedded in a given space, non trivial distance dependence of the link probability. These ensembles are characterized by their entropy which evaluate th...
August 1, 2007
Randomized network ensembles are the null models of real networks and are extensivelly used to compare a real system to a null hypothesis. In this paper we study network ensembles with the same degree distribution, the same degree-correlations or the same community structure of any given real network. We characterize these randomized network ensembles by their entropy, i.e. the normalized logarithm of the total number of networks which are part of these ensembles. We estima...
March 7, 2007
We present a statistical mechanics approach for the description of complex networks. We first define an energy and an entropy associated to a degree distribution which have a geometrical interpretation. Next we evaluate the distribution which extremize the free energy of the network. We find two important limiting cases: a scale-free degree distribution and a finite-scale degree distribution. The size of the space of allowed simple networks given these distribution is evaluat...
June 14, 2006
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...
September 14, 2013
Generalised degrees provide a natural bridge between local and global topological properties of networks. We define the generalised degree to be the number of neighbours of a node within one and two steps respectively. Tailored random graph ensembles are used to quantify and compare topological properties of networks in a systematic and precise manner, using concepts from information theory. We calculate the Shannon entropy of random graph ensembles constrained with a specifi...
April 20, 2019
Due to their conceptual and mathematical simplicity, Erd\"os-R\'enyi or classical random graphs remain as a fundamental paradigm to model complex interacting systems in several areas. Although condensation phenomena have been widely considered in complex network theory, the condensation of degrees has hitherto eluded a careful study. Here we show that the degree statistics of the classical random graph model undergoes a first-order phase transition between a Poisson-like dist...
August 12, 2009
We study the tailoring of structured random graph ensembles to real networks, with the objective of generating precise and practical mathematical tools for quantifying and comparing network topologies macroscopically, beyond the level of degree statistics. Our family of ensembles can produce graphs with any prescribed degree distribution and any degree-degree correlation function, its control parameters can be calculated fully analytically, and as a result we can calculate (a...
September 1, 2005
In the paper, we study fluctuations over several ensembles of maximum-entropy random networks. We derive several fluctuation-dissipation relations characterizing susceptibilities of different networks to changes in external fields. In the case of networks with a given degree sequence, we argue that the scale-free topologies of real-world networks may arise as a result of self-organization of real systems into sparse structures with low susceptibility to random external pertur...
June 10, 2002
Using a maximum entropy principle to assign a statistical weight to any graph, we introduce a model of random graphs with arbitrary degree distribution in the framework of standard statistical mechanics. We compute the free energy and the distribution of connected components. We determine the size of the percolation cluster above the percolation threshold. The conditional degree distribution on the percolation cluster is also given. We briefly present the analogous discussion...
April 4, 2002
We develop a statistical mechanics approach for random networks with uncorrelated vertices. We construct equilibrium statistical ensembles of such networks and obtain their partition functions and main characteristics. We find simple dynamical construction procedures that produce equilibrium uncorrelated random graphs with an arbitrary degree distribution. In particular, we show that in equilibrium uncorrelated networks, fat-tailed degree distributions may exist only starting...