Classical information theory of networks

Existing information-theoretic frameworks based on maximum entropy network ensembles are not able to explain the emergence of heterogeneity in complex networks. Here, we fill this gap of knowledge by developing a classical framework for networks based on finding an optimal trade-off between the information content of a compressed representation of the ensemble and the information content of the actual network ensemble. We introduce a novel classical network ensemble satisfying a set of soft constraints and we find the optimal distribution of the constraints for this ensemble. We show that for the classical network ensemble in which the only constraints are the expected degrees a power-law degree distribution is optimal. Also, we study spatially embedded networks finding that the interactions between nodes naturally lead to non-uniform spread of nodes in the embedding space, leading in some cases to a fractal distribution of nodes. This result is consistent with the so called `blessing of non-uniformity' of data, i.e. the fact that real world data typically do not obey uniform distributions. The pertinent features of real-world air transportation networks are well described by the proposed framework.