Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
arXiv:1705.10261 · doi:10.1007/s10955-017-1887-7
Abstract
Even though power-law or close-to-power-law degree distributions are ubiquitously observed in a great variety of large real networks, the mathematically satisfactory treatment of random power-law graphs satisfying basic statistical requirements of realism is still lacking. These requirements are: sparsity, exchangeability, projectivity, and unbiasedness. The last requirement states that entropy of the graph ensemble must be maximized under the degree distribution constraints. Here we prove that the hypersoft configuration model (HSCM), belonging to the class of random graphs with latent hyperparameters, also known as inhomogeneous random graphs or -random graphs, is an ensemble of random power-law graphs that are sparse, unbiased, and either exchangeable or projective. The proof of their unbiasedness relies on generalized graphons, and on mapping the problem of maximization of the normalized Gibbs entropy of a random graph ensemble, to the graphon entropy maximization problem, showing that the two entropies converge to each other in the large-graph limit.
References in corpus (22)
- Clustering and preferential attachment in growing networks
- Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
- Connectivity of Growing Random Networks
- Hyperbolic Geometry of Complex Networks
- The statistical mechanics of networks
- The phase transition in inhomogeneous random graphs
- Class of correlated random networks with hidden variables
- Entropy measures for complex networks: Toward an information theory of complex topologies
- The entropy of network ensembles
- Estimating and understanding exponential random graph models
- The entropy of randomized network ensembles
- Analytical maximum-likelihood method to detect patterns in real networks
- Maximum likelihood: extracting unbiased information from complex networks
- Random graphs with a given degree sequence
- Consistency under sampling of exponential random graph models
- Breaking of ensemble equivalence in networks
- Clustering implies geometry in networks
- Hyperbolic Graph Generator
- Entropy distribution and condensation in random networks with a given degree distribution
- Singularities in the entropy of asymptotically large simple graphs
- Duality between equilibrium and growing networks
- Hamiltonian Dynamics of Preferential Attachment
Cited by in corpus (15)
- Network Geometry
- Link prediction with hyperbolic geometry
- Small worlds and clustering in spatial networks
- Meta-validation of bipartite network projections
- A geometry-induced topological phase transition in random graphs
- Random hyperbolic graphs in dimensions
- Weighted hypersoft configuration model
- Random Simplicial Complexes: Models and Phenomena
- Dynamic Hidden-Variable Network Models
- Multiscale network renormalization: scale-invariance without geometry
- Propinquity drives the emergence of network structure and density
- Entropy of labeled versus unlabeled networks
- On the External Validity of Average-Case Analyses of Graph Algorithms
- Random graphs and real networks with weak geometric coupling
- Sparse power-law network model for reliable statistical predictions based on sampled data