Description
Graph distances in real networks, in particular social networks, have been always in the focus of network research since Milgram's experiment in 60s. In this talk we specialise in a geometric random graph known as scale-free percolation, which shows a rich phase diagram, and focus on short paths in it. In this model, $x,y \in \mathbb{Z}^d$ are connected with probability depending on i.i.d weights and their Euclidean distance $|x-y|$.
First we study asymptotic distances in a regime where graph distances are poly-logarithmic in Euclidean distance. With a multi-scale argument we obtain improved bounds on the logarithmic exponent. In the heavy tail regime, improvement of the upper bound shows a discrepancy with the long-range percolation. In the light tail regime, the correct exponent is identified.
In the following part we investigate navigation possibility in the model. More precisely, we study whether it is possible to find the shortest paths between two vertices, given only local information (weights and locations of neighbors). In the doubly logarithmic regime, a greedy routing algorithm enables us to find a comparably long path as the shortest one up to the prefactor.
