Scale-free percolation on finite domains
Final Report Abstract
Skalenfreie Perkolation ist ein mathematisches Modell für Zufallsgraphen, welche eine Reihe typischer Eigenschaften realer Netzwerken aufweist: Knoten haben eine polynomial abfallende Gradverteilung (“scale-free”) und weit entfernte Punkte sind durch kurze Pfade im Netzwerk verbunden (“small world”). Dabei konzentrieren wir uns insbesondere auf einen Parameterbereich, in dem weit auseinanderliegende Punkte x und y einen Graphenabstand der Größenordnung (log |x — y|)^θ(1) haben, also poly-logarithmischen Abstand. Wir erweitern Verfahren aus der statistischen Mechanik um in diesem Zufallsgraphenmodell verbesserte Asymptotiken für den Graphenabstand zu erzielen. Darüber hinaus adressieren wir die Frage der Navigierbarkeit von skalenfreier Perkolation: gibt es Algorithmen, die einen kurzen Weg finden wenn nur lokale Informationen zur Verfügung stehen? Hierbei identifizieren wir eine Dichotomie: Wenn der Graphenabstand zwischen x und y von der Größenordnung log log |x — y| ist (also extrem kurz), dann existieren lokale Algorithmen, welche einen solchen kurzen Weg finden. Andererseits ist es im oben skizzierten (poly-)logarithmischen Regime so, dass jeder lokale Algorithmus bestenfalls einen Weg mit polynomialer Länge findet; in diesem Regime ist skalenfreie Perkolation also nicht navigierbar. Unsere Resultate legen nahe, dass eine solche Unterscheidung auch in größerer Allgemeinheit gilt.
Publications
- (2022). Graph distances in scale-free percolation: the logarithmic case. J. Appl. Probab.
N. Hao and M. Heydenreich
(See online at https://doi.org/10.1017/jpr.2022.44)
