The entropy of network ensembles

Abstract

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 the cardinality of networks in the ensemble. The general framework we present in this paper is able to describe microcanonical ensemble of networks as well as canonical or hidden variables network ensemble with significant implication for the formulation of network constructing algorithms. Moreover in the paper we define and and characterize in particular the "structural entropy", i.e. the entropy of the ensembles of undirected uncorrelated simple networks with given degree sequence. We discuss the apparent paradox that scale-free degree distribution are characterized by having small structural entropy but are so widely encountered in natural, social and technological complex systems. We give the proof that while scale-free networks ensembles have small structural entropy, they also correspond to the most likely degree distribution with the corresponding value of the structural entropy.

(10 pages)

References in corpus (28)

• Emergence of scaling in random networks
• Community structure in social and biological networks
• The architecture of complex weighted networks
• Hierarchical organization of modularity in metabolic networks
• Specificity and stability in topology of protein networks
• Comparing community structure identification
• Network robustness and fragility: Percolation on random graphs
• Critical phenomena in complex networks
• Dynamical and correlation properties of the Internet
• New Model of Internet Topology Using k-shell Decomposition
• MEDUSA - New Model of Internet Topology Using k-shell Decomposition
• k-core organization of complex networks
• Mixture models and exploratory analysis in networks
• Class of correlated random networks with hidden variables
• A General Formalism for Inhomogeneous Random Graphs
• The entropy of randomized network ensembles
• Entropy Rate of Diffusion Processes on Complex Networks
• Maximum likelihood: extracting unbiased information from complex networks
• Statistical ensemble of scale-free random graphs
• Correlated random networks
• Solution of the 2-star model of a network
• Glassiness in a model without energy barriers
• Local structure of directed networks
• Entropies of complex networks with hierarchically constrained topologies
• Principles of statistical mechanics of random networks
• Homogeneous complex networks
• A statistical mechanics approach for scale-free networks and finite-scale networks
• Transition from small to large world in growing networks

Cited by in corpus (105)

• Hyperbolic Geometry of Complex Networks
• Mathematical Formulation of Multi-Layer Networks
• Social physics
• The Statistical Physics of Real-World Networks
• Entropy measures for complex networks: Toward an information theory of complex topologies
• Small-world behavior in time-varying graphs
• The Physics of Financial Networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Assessing the relevance of node features for network structure
• Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
• Analytical maximum-likelihood method to detect patterns in real networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Tolerating the Community Detection Resolution Limit with Edge Weighting
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• Randomizing bipartite networks: the case of the World Trade Web
• 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
• The noisy voter model on complex networks
• Enhanced reconstruction of weighted networks from strengths and degrees
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Emergence of overlap in ensembles of spatial multiplexes and statistical mechanics of spatial interacting networks ensembles
• Gibbs entropy of networks ensembles by cavity methods
• Evolution of robust network topologies: Emergence of central backbones
• Measure for degree heterogeneity in complex networks and its application to recurrence network analysis
• Extracting Information from Multiplex Networks
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Constrained Markovian dynamics of random graphs
• Mesoscopic Structures Reveal the Network Between the Layers of Multiplex Datasets
• Constructing and sampling directed graphs with given degree sequences
• Critical fluctuations in spatial complex networks
• Complex Networks and Symmetry I: A Review
• Stochastic pair approximation treatment of the noisy voter model
• Enhancing neural-network performance via assortativity
• Complex Quantum Networks: a Topical Review
• Does the brain behave like a (complex) network? I. Dynamics
• Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure
• Configuration model for correlation matrices preserving the node strength
• Layer Communities in Multiplex Networks
• Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
• Emergence of robustness against noise: A structural phase transition in evolved models of gene regulatory networks
• What is the Entropy of a Social Organization?
• Bipartite quantum states and random complex networks
• Classical Information Theory of Networks
• Percolation on correlated random networks
• Approximate entropy of network parameters
• Characterization of graphs for protein structure modeling and recognition of solubility
• Low-temperature behaviour of social and economic networks
• Information sharing in Quantum Complex Networks
• Entropy rate of non-equilibrium growing networks
• Analysis of the convergence of the degree distribution of contracting random networks towards a Poisson distribution using the relative entropy
• Weighted hypersoft configuration model
• Percolation transition in correlated hypergraphs
• Spatial networks with wireless applications
• A geometric entropy detecting the Erdös-Rényi phase transition
• Smart random walkers: the cost of knowing the path
• Atomic subgraphs and the statistical mechanics of networks
• Latent Poisson models for networks with heterogeneous density
• Entropy of labeled versus unlabeled networks
• Controlling network ensembles
• Grand canonical ensembles of sparse networks and Bayesian inference
• Entropy rate of random walks on complex networks under stochastic resetting
• Clarifying How Degree Entropies and Degree-Degree Correlations Relate to Network Robustness
• Duality between predictability and reconstructability in complex systems
• Plasticity-rigidity cycles: A general adaptation mechanism
• The configuration multi-edge model: Assessing the effect of fixing node strengths on weighted network magnitudes
• Sample-to-sample fluctuations in real-network ensembles
• 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
• Entropy of microcanonical finite-graph ensembles
• Quantifying information loss on chaotic attractors through recurrence networks
• Pathlength scaling in graphs with incomplete navigational information
• Exactly scale-free scale-free networks
• Generating random networks that consist of a single connected component with a given degree distribution
• The von Neumann entropy of networks
• A Gaussian integral that counts regular graphs
• Ranking nodes according to their path-complexity
• Geometric randomization of real networks with prescribed degree sequence
• Ensemble equivalence for distinguishable particles
• Entropy in Social Networks
• Graph Entropy Guided Node Embedding Dimension Selection for Graph Neural Networks
• Null models for multi-optimized large-scale network structures
• Network Null Model based on Maximal Entropy and the Rich-Club
• Nodal statistics-based equivalence relation for graph collections
• Tsallis mapping in growing complex networks with fitness
• Edge based stochastic block model statistical inference
• The complex social network from The Lord of The Rings
• Optimal scales in weighted networks
• Characterization and space embedding of directed graphs and social networks through magnetic Laplacians
• Relative Canonical Network Ensembles -- (Mis)characterizing Small-World Networks
• Catching homologies by geometric entropy
• Ensembles based on the Rich-Club and how to use them to build soft-communities
• Quantifying metadata relevance to network block structure using description length
• Transition to congestion in communication/computation networks: from ideal to realistic resource allocation via Montecarlo simulations
• Graph model selection by edge probability sequential inference
• Structural Entropy of the Stochastic Block Models
• A Formal Critique of the Value of the Colombian Páramo
• Interplay between Network Topology and Dynamics in Neural Systems
• Complex distributions emerging in filtering and compression
• Detectability threshold in weighted modular networks
• Irregular Metamaterial Networks
• Thermodynamic stability and structural transitions in virus-host networks
• Legendre transformation and information geometry for the maximum entropy theory of ecology