Short paths in scale-free percolation

Hao, Nannan (2023): Short paths in scale-free percolation. Dissertation, LMU München: Fakultät für Mathematik, Informatik und Statistik

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.

• Dokumententyp: Dissertationen (Dissertation, LMU München)
• Themengebiete: 500 Naturwissenschaften und Mathematik ; 500 Naturwissenschaften und Mathematik > 510 Mathematik
• Fakultäten: Fakultät für Mathematik, Informatik und Statistik
• Sprache der Hochschulschrift: Englisch
• Datum der mündlichen Prüfung: 16. März 2023
• 1. Bericht­erstatter:in: Heydenreich, Markus