Entropy measures for complex networks: Toward an information theory of complex topologies

Abstract

The quantification of the complexity of networks is, today, a fundamental problem in the physics of complex systems. A possible roadmap to solve the problem is via extending key concepts of information theory to networks. In this paper we propose how to define the Shannon entropy of a network ensemble and how it relates to the Gibbs and von Neumann entropies of network ensembles. The quantities we introduce here will play a crucial role for the formulation of null models of networks through maximum-entropy arguments and will contribute to inference problems emerging in the field of complex networks.

(4 pages, 1 figure)

References in corpus (9)

• Critical phenomena in complex networks
• The entropy of network ensembles
• The entropy of randomized network ensembles
• Entropy Rate of Diffusion Processes on Complex Networks
• Maximum likelihood: extracting unbiased information from complex networks
• Generalized Bose-Fermi statistics and structural correlations in weighted networks
• Spectra of Sparse Random Matrices
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Entropies of complex networks with hierarchically constrained topologies

Cited by in corpus (100)

• The structure and dynamics of multilayer networks
• Hyperbolic Geometry of Complex Networks
• Mathematical Formulation of Multi-Layer Networks
• The Statistical Physics of Real-World Networks
• Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
• Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
• Sparse graphs using exchangeable random measures
• The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
• The entropic origin of disassortativity in complex networks
• Entropy of stochastic blockmodel ensembles
• A Survey on Centrality Metrics and Their Implications in Network Resilience
• Higher-order simplicial synchronization of coupled topological signals
• Interdisciplinary and physics challenges of Network Theory
• Emergence of overlap in ensembles of spatial multiplexes and statistical mechanics of spatial interacting networks ensembles
• Breaking of ensemble equivalence in networks
• Gibbs entropy of networks ensembles by cavity methods
• Clustering implies geometry in networks
• Weighted simplicial complexes and their representation power of higher-order network data and topology
• Unbiased sampling of network ensembles
• Entropy of dynamical social networks
• Multiplex networks with heterogeneous activities of the nodes
• Link prediction based on path entropy
• Exponential Random Simplicial Complexes
• Understanding interdependency through complex information sharing
• Mapping and discrimination of networks in the complexity-entropy plane
• Complex Quantum Networks: a Topical Review
• Thermodynamic characterization of networks using graph polynomials
• Entropy distribution and condensation in random networks with a given degree distribution
• Clustering of random scale-free networks
• Laplacian paths in complex networks: information core emerges from entropic transitions
• Configuration model for correlation matrices preserving the node strength
• Correlations between weights and overlap in ensembles of weighted multiplex networks
• Grand canonical validation of the bipartite International Trade Network
• Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
• Ensemble nonequivalence in random graphs with modular structure
• Meta-validation of bipartite network projections
• From Relational Data to Graphs: Inferring Significant Links using Generalized Hypergeometric Ensembles
• Superstripes and complexity in high-temperature superconductors
• Bipartite quantum states and random complex networks
• Classical Information Theory of Networks
• Entropy of Spatial Network Ensembles
• Bipartite separability and non-local quantum operations on graphs
• Duality between equilibrium and growing networks
• Entropy-based link prediction in weighted networks
• Information sharing in Quantum Complex Networks
• Characterization of graphs for protein structure modeling and recognition of solubility
• Entropy rate of non-equilibrium growing networks
• USER: Unsupervised Structural Entropy-based Robust Graph Neural Network
• Analysis of heat kernel highlights the strongly modular and heat-preserving structure of proteins
• Weighted hypersoft configuration model
• Random Simplicial Complexes: Models and Phenomena
• Characterization and comparison of large directed graphs through the spectra of the magnetic Laplacian
• Synchronization Invariance Under Network Structural Transformations
• Algorithmic complexity of multiplex networks
• Threshold-free estimation of entropy from a Pearson matrix
• Entropy of labeled versus unlabeled networks
• Grand canonical ensembles of sparse networks and Bayesian inference
• Clarifying How Degree Entropies and Degree-Degree Correlations Relate to Network Robustness
• Information inequalities and Generalized Graph Entropies
• Models, Entropy and Information of Temporal Social Networks
• Entropy rate of random walks on complex networks under stochastic resetting
• Hamiltonian Dynamics of Preferential Attachment
• Duality between predictability and reconstructability in complex systems
• Quantum entropy couples matter with geometry
• Network science Ising states of matter
• Spacing ratio statistics of multiplex directed networks
• Sparse power-law network model for reliable statistical predictions based on sampled data
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Topological Signals of Singularities in Ricci Flow
• Time Evolution of Entropy in a Growth model: Dependence on the Description
• Entropy of microcanonical finite-graph ensembles
• Quantifying information loss on chaotic attractors through recurrence networks
• The Quantum Theil Index: Characterizing Graph Centralization using von Neumann Entropy
• Pattern recognition at different scales: a statistical perspective
• A new structure entropy of complex networks based on Tsallis nonextensive statistical mechanics
• A Gaussian integral that counts regular graphs
• Fast computation of von Neumann entropy for large-scale graphs via quadratic approximations
• Ranking nodes according to their path-complexity
• Entropic Dynamics of Networks
• Random walk in degree space and the time-dependent Watts-Strogatz model
• Entropy in Social Networks
• Characterizing spatial point processes by percolation transitions
• Fast Incremental von Neumann Graph Entropy Computation: Theory, Algorithm, and Applications
• Network Null Model based on Maximal Entropy and the Rich-Club
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• A null model for Dunbar's circles
• Malleability of complex networks
• From Sharma-Mittal to von-Neumann Entropy of a Graph
• Characterization and space embedding of directed graphs and social networks through magnetic Laplacians
• Local phase transitions in a model of multiplex networks with heterogeneous degrees and inter-layer coupling
• Beyond holography: the entropic quantum gravity foundations of image processing
• Computational Human Dynamics
• Predicting the Popularity of Topics based on User Sentiment in Microblogging Websites
• Symmetric Laplacians, Quantum Density Matrices and their Von-Neumann Entropy
• Interplay between Network Topology and Dynamics in Neural Systems
• Entropy NAND: Early Functional Completeness in Entropy Networks
• Tsallis entropy of complex networks
• Econoinformatics meets Data-Centric Social Sciences
• Network-ensemble comparisons with stochastic rewiring and von Neumann entropy
• Quantitative Graph Theory: A new branch of graph theory and in network science