Short paths in scale-free percolation

Hao, Nannan (2023): Short paths in scale-free percolation. Dissertation, LMU München: Faculty of Mathematics, Computer Science and Statistics

Abstract

Graph distances in real-world networks, in particular social networks, have been always in the focus of network research since Milgram’s sociological experiment in 1960s. In this dissertation we specialize in a geometric random graph known as scale-free percolation, which shows a rich phase diagram regarding graph distances, and focus on short paths in it. In this model, x,y ∈ Zd are connected with probability depending on i.i.d weights Wx, Wy 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 long-range percolation. In the light tail regime, the correct exponent is identified. The following part of this dissertation investigates navigation possibility in the model. More precisely, we study the possibility to find short paths between two vertices given only local information (weights and locations of neighbors). In the regime where graph distances are poly-logarithmic we show that any algorithm based on local information takes at least polynomial steps to find the target. In contrast, in the regime where the graph distance is doubly logarithmic in the Euclidean distance, a short path with length of the same order can be found by a greedy routing algorithm.

• Item Type: Theses (Dissertation, LMU Munich)
• Subjects: 500 Natural sciences and mathematics; 500 Natural sciences and mathematics > 510 Mathematics
• Faculties: Faculty of Mathematics, Computer Science and Statistics
• Language: English
• Date of oral examination: 16. March 2023
• 1. Referee: Heydenreich, Markus
• Signature of the printed copy: 0001/UMC 29642