Graph distances in scale-free percolation: the logarithmic case

Abstract

Scale-free percolation is a stochastic model for complex networks. In this spatial random graph model, vertices $x,y\in {\mathbb{Z}}^d$ are linked by an edge with probability depending on i.i.d.\ vertex weights and the Euclidean distance $|x-y|$. Depending on the various parameters involved, we get a rich phase diagram. We study graph distances and compare it to the Euclidean distance of the vertices. Our main attention is on a regime where graph distances are (poly-)logarithmic in the Euclidean distance. We obtain improved bounds on the logarithmic exponents. In the light tail regime, the correct exponent is identified.

20 pages, 3 figures

References in corpus (5)

• A lower bound for the chemical distance in sparse long-range percolation models
• Percolation phase transition in weight-dependent random connection models
• Greedy Routing and the Algorithmic Small-World Phenomenom
• Distance evolutions in growing preferential attachment graphs
• Scale-free percolation in continuum space: quenched degree and clustering coefficient