Entropy distribution and condensation in random networks with a given degree distribution

K. Anand, D. Krioukov, and G. Bianconi
Physical Review E
v.89, 062807, 2014
May 30, 2014

Abstract

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.

Related publications