Average distance in a general class of scale-free networks
OPEN ACCESS
Author / Producer
Date
2025-06
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
In Chung-Lu random graphs, a classic model for real-world networks, each vertex is equipped with a weight drawn from a power-law distribution, and two vertices forman edge independently with probability proportional to the product of their weights. Chung-Lu graphs have average distance O(log logn) and thus reproduce the small-world phenomenon, a key property of real-world networks. Modern, more realistic variants of this model also equip each vertex with a random position in a specific underlying geometry. The edge probability of two vertices then depends, say, inversely polynomially on their distance. In this paper we study a generic augmented version of Chung-Lu random graphs. We analyze a model where the edge probability of two vertices can depend arbitrarily on their positions, as long as the marginal probability of forming an edge (for two vertices with fixed weights, one fixed position, and one random position) is as in a Chung-Lu random graph. The resulting class contains Chung-Lu random graphs, hyperbolic random graphs, and geometric inhomogeneous random graphs as special cases. Our main result is that every random graph model in this general class has the same average distance as a Chung-Lu random graph, up to a factor of 1+o(1). This shows inparticular that specific choices, such as taking the underlying geometry to be Euclidean, do not significantly influence the average distance. The proof also shows that every random graph model in our class has a giant component and polylogarithmic diameter with high probability.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
57 (2)
Pages / Article No.
371 - 406
Publisher
Cambridge University Press
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Small-world graphs; complex networks; average distances
Organisational unit
03672 - Steger, Angelika (emeritus) / Steger, Angelika (emeritus)