Classical Information Theory of Networks

Abstract

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. In this way not only we introduce a novel classical network ensemble satisfying a set of soft constraints but we are also able to calculate the optimal distribution of the constraints. 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 space, with pairs of nodes at a given distance not necessarily obeying a power-law distribution. The pertinent features of real-world air transportation networks are well described by the proposed framework.

arXiv comment(19 pages, 4 figures)

References in corpus (23)

• Emergence of scaling in random networks
• Finding and evaluating community structure in networks
• The architecture of complex weighted networks
• Benchmark graphs for testing community detection algorithms
• Defining and identifying communities in networks
• Hyperbolic Geometry of Complex Networks
• The statistical mechanics of networks
• Emergence of network features from multiplexity
• The Statistical Physics of Real-World Networks
• Entropy measures for complex networks: Toward an information theory of complex topologies
• Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
• The entropy of network ensembles
• Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
• Scale-free Networks Well Done
• Spectral entropies as information-theoretic tools for complex network comparison
• Stochastic thermodynamics of computation
• Generalized Bose-Fermi statistics and structural correlations in weighted networks
• Entropy of stochastic blockmodel ensembles
• Breaking of ensemble equivalence in networks
• Gibbs entropy of networks ensembles by cavity methods
• A statistical mechanics approach for scale-free networks and finite-scale networks
• Reducing Degeneracy in Maximum Entropy Models of Networks
• Statistical Mechanics of Multi-Edge Networks

Cited by in corpus (8)

• Entropic dynamics on Gibbs statistical manifolds
• Multiscale network renormalization: scale-invariance without geometry
• Grand canonical ensembles of sparse networks and Bayesian inference
• Clarifying How Degree Entropies and Degree-Degree Correlations Relate to Network Robustness
• Entropy of labeled versus unlabeled networks
• Quantum entropy couples matter with geometry
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Legendre transformation and information geometry for the maximum entropy theory of ecology