Entropy distribution and condensation in random networks with a given degree distribution
arXiv:1403.5884 · doi:10.1103/PhysRevE.89.062807
Abstract
The entropy of network ensembles characterizes the amount of information encoded in the network structure, and can be used to quantify network complexity, and the relevance of given structural properties observed in real network datasets with respect to a random hypothesis. In many real networks the degrees of individual nodes are not fixed but change in time, while their statistical properties, such as the degree distribution, are preserved. Here we characterize the distribution of entropy of random networks with given degree sequences, where each degree sequence is drawn randomly from a given degree distribution. We show that the leading term of the entropy of scale-free network ensembles depends only on the network size and average degree, and that entropy is self-averaging, meaning that its relative variance vanishes in the thermodynamic limit. We also characterize large fluctuations of entropy that are fully determined by the average degree in the network. Finally, above a certain threshold, large fluctuations of the average degree in the ensemble can lead to condensation, meaning that a single node in a network of size~ can attract links.
arXiv comment(9 pages, 1 figure)
References in corpus (27)
- Statistical mechanics of complex networks
- Community detection in graphs
- Hyperbolic Geometry of Complex Networks
- Bose-Einstein condensation in complex networks
- The statistical mechanics of networks
- Popularity versus Similarity in Growing Networks
- Entropy measures for complex networks: Toward an information theory of complex topologies
- Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
- The entropy of randomized network ensembles
- Assessing the relevance of node features for network structure
- Maximum likelihood: extracting unbiased information from 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 entropic origin of disassortativity in complex networks
- Entropy of stochastic blockmodel ensembles
- Randomizing world trade. I. A binary network analysis
- Randomizing world trade. II. A weighted network analysis
- Number of loops of size h in growing scale-free networks
- Emergence of large cliques in random scale-free network
- Gibbs entropy of networks ensembles by cavity methods
- Evolution of robust network topologies: Emergence of central backbones
- Entropies of complex networks with hierarchically constrained topologies
- Constrained Markovian dynamics of random graphs
- Statistical Mechanics of Multi-Edge Networks
- Bipartite quantum states and random complex networks
- Fluctuations analysis in complex networks modeled by hidden variable models. Necessity of a large cut-off in hidden-variable models
Cited by in corpus (15)
- The Statistical Physics of Real-World Networks
- Clustering implies geometry in networks
- Scale-free networks with exponent one
- Entropic Dynamic Time Warping Kernels for Co-evolving Financial Time Series Analysis
- Thermodynamic characterization of networks using graph polynomials
- Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
- Meta-validation of bipartite network projections
- Weighted hypersoft configuration model
- The role of adjacency matrix degeneration in maximum entropy weighted network models
- Statistical mechanics of random geometric graphs: Geometry-induced first order phase transition
- Entropy of labeled versus unlabeled networks
- Condensation of degrees emerging through a first-order phase transition in classical random graphs
- Hamiltonian Dynamics of Preferential Attachment
- Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
- A Quantum-inspired Similarity Measure for the Analysis of Complete Weighted Graphs