hide
Free keywords:
Computer Science, Discrete Mathematics, cs.DM,cs.SI
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 (for which
we fix an exponent $2 < \beta < 3$), and two vertices form an edge
independently with probability proportional to the product of their weights.
Modern, more realistic variants of this model also equip each vertex with a
random position in a specific underlying geometry, which is typically
Euclidean, such as the unit square, circle, or torus. The edge probability of
two vertices then depends, say, inversely polynomial on their distance.
We show that specific choices, such as the underlying geometry being
Euclidean or the dependence on the distance being inversely polynomial, do not
significantly influence the average distance, by studying a generic augmented
version of Chung-Lu random graphs. Specifically, 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 Chung-Lu
random graphs, i.e., proportional to the product of their weights. The
resulting class contains Chung-Lu random graphs, hyperbolic random graphs, and
geometric inhomogeneous random graphs as special cases. Our main result is that
this general model has the same average distance as Chung-Lu random graphs, up
to a factor $1+o(1)$. The proof also yields that our model has a giant
component and polylogarithmic diameter with high probability.
