Universität zu Köln

Zufallsgraphen liefern einen grundlegenden Rahmen für das Verständnis des Verhaltens komplexer Netzwerke, einschließlich biologischer und sozialer Netzwerke. Solche Netzwerke teilen typischerweise zwei wesentliche Eigenschaften: (i) die Verbindungseigenschaften werden durch „Nähe" beeinflusst, wobei dies sowohl physische als auch abstrakte Nähe bedeuten kann; und (ii) nicht alle Knoten haben dieselbe Neigung, Verbindungen einzugehen. Zu den Auswirkungen dieser Eigenschaften gehören die Bildung von Klustern und grosse Abweichungen von Knotengraden. In dieser Dissertation untersuchen wir räumliche inhomogene Zufallsgraphmodelle, die sowohl Geometrie als auch Inhomogenität berücksichtigen, um die Eigenschaften (i) und (ii) zu erfassen. Eine reichhaltige Klasse solcher Modelle bilden die gewichtsabhängigen zufälligen Verbindungsmodelle (weight-dependent random connection models), die sich wie folgt beschreiben lassen. Die Knotenmenge ist ein Standard-Poisson-Punktprozess auf dem dd d-dimensionalen Torus mit Volumen nn n, und jedem Knoten wird unabhängig ein Gewicht mit schwerem Tail (heavy-tailed) zugewiesen. Je zwei verschiedene Knoten bilden unabhängig voneinander eine Kante mit einer Wahrscheinlichkeit, die eine Funktion der Gewichte und des Abstands der beiden Knoten ist, sodass kurze Kanten sowie Kanten zwischen Knoten mit hohem Gewicht bevorzugt werden. Während das typische Verhalten solcher Modelle bereits umfassend untersucht wurde, ist über ihr Verhalten unter seltenen oder extremen Ereignissen weitaus weniger bekannt. Wir betrachten das seltene Ereignis, dass die Anzahl der Kanten, bezeichnet mit |E_n|, untypisch gross ist. Da sich |E_n| als Summe der Knotengrade schreiben lässt und der Grad eines Knotens bedingt auf sein Gewicht eine poisson-artige Verteilung besitzt, deren Erwartungswert eine monoton wachsende Funktion des Gewichts ist, beweisen wir zunächst ein Prinzip grosser Abweichungen (large deviation principle) für die Summe von n unabhängigen heavy-tailed Zufallsvariablen, die einer wandernden Trunkierung an der Stelle n unterliegen. Aufbauend auf diesem Resultat bestimmen wir die obere Wahrscheinlichkeit grosser Abweichungen für die Anzahl der Kanten in räumlichen inhomogenen Zufallsgraphmodellen, wenn das Raumvolumen gegen unendlich strebt. Unser Ergebnis umfasst mehrere Modelle, darunter die skalenfreie Perkolation (scale-free percolation), das Boolesche Modell mit heavy-tailed Radiusverteilung sowie das altersabhängige zufällige Verbindungsmodell (age-dependent random connection model). In all diesen Fällen wird die grosse Abweichung durch ein Kondensationsphänomen bestimmt, bei dem eine endliche Anzahl von Knoten zufällig ausgewählt wird und aussergewöhnlich grosse Gewichte annimmt. Diese Knoten verbinden sich dann mit einem makroskopischen Anteil der Knoten des Graphen, während die übrigen Knoten nahezu typische Grade beibehalten und ihren erwarteten Beitrag liefern. Der Kondensationsmechanismus führt somit zur Entstehung einiger weniger stark verbundener Hubs, wodurch der Graph mit hoher Wahrscheinlichkeit zusammenhängend wird. Dies wirft natürlicherweise die Frage auf, wie sich der Zusammenhang verhält, wenn die Kanten des Graphen nicht statisch sind und zeitlichen Einschränkungen unterliegen. Um dies zu untersuchen, betrachten wir zeitliche zufällige geometrische Graphen (temporal random geometric graphs), in denen jede Kante mit einem gleichverteilten zufälligen Zeitstempel versehen ist, welcher den Zeitpunkt der Interaktion zwischen zwei Knoten darstellt. Wir bestimmen einen Schwellenwert für die Existenz monoton wachsender Pfade zwischen allen Paaren von Knoten in zeitlichen zufälligen geometrischen Graphen. Unsere Resultate zeigen, dass zeitlicher Zusammenhang bei einer signifikant grösseren Kantendichte auftritt als der gewöhnliche Zusammenhang des zugrunde liegenden zufälligen geometrischen Graphen.

German