Entropy rate of non-equilibrium growing networks
arXiv:1109.0940 · doi:10.1103/PhysRevE.84.066113
Abstract
New entropy measures have been recently introduced for the quantification of the complexity of networks. Most of these entropy measures apply to static networks or to dynamical processes defined on static complex networks. In this paper we define the entropy rate of growing network models. This entropy rate quantifies how many labeled networks are typically generated by the growing network models. We analytically evaluate the difference between the entropy rate of growing tree network models and the entropy of tree networks that have the same asymptotic degree distribution. We find that the growing networks with linear preferential attachment generated by dynamical models are exponentially less than the static networks with the same degree distribution for a large variety of relevant growing network models. We study the entropy rate for growing network models showing structural phase transitions including models with non-linear preferential attachment. Finally, we bring numerical evidence that the entropy rate above and below the structural phase transitions follow a different scaling with the network size.
arXiv comment(8 pages, 4 figures)
References in corpus (25)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
- Connectivity of Growing Random Networks
- Organization of Growing Random Networks
- Bose-Einstein condensation in complex networks
- Evolution of reference networks with aging
- Entropy measures for complex networks: Toward an information theory of complex topologies
- The entropy of network ensembles
- The entropy of randomized network ensembles
- Assessing the relevance of node features for network structure
- Entropy Rate of Diffusion Processes on Complex Networks
- Efficient and exact sampling of simple graphs with given arbitrary degree sequence
- All scale-free networks are sparse
- The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
- The laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states
- The entropic origin of disassortativity in complex networks
- Maximal-entropy random walks in complex networks with limited information
- Gibbs entropy of networks ensembles by cavity methods
- Entropies of complex networks with hierarchically constrained topologies
- Some families of density matrices for which separability is easily tested
- Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure
- Tailored graph ensembles as proxies or null models for real networks II: results on directed graphs
- Finite-time fluctuations in the degree statistics of growing networks
Cited by in corpus (8)
- Complex Quantum Network Geometries: Evolution and Phase Transitions
- Supersymmetric multiplex networks described by coupled Bose and Fermi statistics
- Duality between equilibrium and growing networks
- Bipartite separability and non-local quantum operations on graphs
- Entropy rate of random walks on complex networks under stochastic resetting
- Entropy of labeled versus unlabeled networks
- Sparse power-law network model for reliable statistical predictions based on sampled data
- Evolution of robustness in growing random networks