Sparse maximum-entropy random graphs with a given power-law degree distribution

DOI10.1007/S10955-017-1887-7MaRDI QIDQ1756545zbMATH OpenOpenAlexFDO

Authors Gabor Lippner, Dmitri Krioukov, Pim Van der Hoorn

Publication date 21 December 2018

Published in Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.10261

zbMATH Keywords

sparse random graphsmaximum-entropy graphspower-law degree distributions

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Density (toughness, etc.) (05C42) Entropy in general topology (54C70)

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 $W$-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.

Recommendations

• An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
• An algorithm generating random graphs with power law degree distributions
• Uniform generation of random graphs with power-law degree sequences
• Conditional configuration graphs with discrete power-law distribution of vertex degrees
• Random graphs with a given degree sequence

Cites work

• scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• scientific article; zbMATH DE number 5950715 (Why is no real title available?)
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3896009 (Why is no real title available?)
• scientific article; zbMATH DE number 51089 (Why is no real title available?)
• scientific article; zbMATH DE number 1257656 (Why is no real title available?)
• scientific article; zbMATH DE number 1564259 (Why is no real title available?)
• scientific article; zbMATH DE number 1416626 (Why is no real title available?)
• A Mathematical Theory of Communication
• A critical point for random graphs with a given degree sequence
• An Exponential Family of Probability Distributions for Directed Graphs
• Analytical maximum-likelihood method to detect patterns in real networks
• Axiomatic derivation of the principle of maximum entropy and the principle of minimum cross-entropy
• Complex networks: structure and dynamics
• Connected components in random graphs with given expected degree sequences
• Consistency under sampling of exponential random graph models
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Estimating and understanding exponential random graph models
• Graph limits and exchangeable random graphs
• Graph properties, graph limits, and entropy
• Graphons, cut norm and distance, couplings and rearrangements
• Hamiltonian dynamics of preferential attachment
• Hyperbolic graph generator
• Information Theory and Statistical Mechanics
• Large networks and graph limits
• Latent Space Approaches to Social Network Analysis
• Limits of dense graph sequences
• Network science. With Márton Pósfai
• Networks. An introduction.
• Random Graphs
• Random graphs with a given degree sequence
• Representations for partially exchangeable arrays of random variables
• Singularities in the entropy of asymptotically large simple graphs
• Sparse exchangeable graphs and their limits via graphon processes
• Sparse graphs using exchangeable random measures
• The asymptotic number of labeled graphs with given degree sequences
• The average distances in random graphs with given expected degrees
• The large deviation principle for the Erdős-Rényi random graph
• The number of graphs and a random graph with a given degree sequence
• The phase transition in inhomogeneous random graphs

Cited in

(3)

• Random Simplicial Complexes: Models and Phenomena
• Asymptotic behavior of common connections in sparse random networks
• Limit theorems for assortativity and clustering in null models for scale-free networks

Describes a project that uses

Uses Software

• Hyperbolic graph generator

This page was built for publication: Sparse maximum-entropy random graphs with a given power-law degree distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1756545)