Komplexe Netzwerke sind in Natur und Gesellschaft allgegenwärtig. Sie tauchen in unterschiedlichsten Domänen auf, wie zum Beispiel als soziale Netzwerke, biologische Interaktionen oder Kommunikationsnetzwerke. Trotz ihrer verschiedenen Ursprünge haben diese Netzwerke jedoch viele strukturelle Gemeinsamkeiten. So sind die Grade der Knoten typischerweise Pareto-verteilt. Das heißt, der Anteil an Knoten mit k Nachbarn ist proportional zu k^-β, wobei β eine beliebige Konstante ist. Weiterhin haben solche Netzwerke einen hohen Clusterkoeffizienten, was bedeutet, dass zwei benachbarte Knoten viele gemeinsame Nachbarn haben.

Um das Verhalten solcher Netzwerke mathematisch zu studieren, werden sie häufig als Zufallsgraphen modelliert. Klassische Modelle wie inhomogene Zufallsgraphen oder das Preferential-Attachment-Modell erzeugen Graphen mit Pareto-verteilten Knotengraden. Cluster sind darin jedoch häufig nicht vorhanden, oder werden durch das Hinzufügen unnatürlicher Strukturen künstlich erzeugt.

Hyperbolische Zufallsgraphen lösen dieses Problem, indem sie dem Graphen eine Geometrie zugrunde legen. Jeder Knoten erhält hyperbolische Koordinaten, und zwei Knoten sind verbunden, wenn ihre hyperbolische Distanz klein ist. Cluster entstehen dann natürlich, da benachbarte Knoten samt ihrer Nachbarschaften in der Geometrie nah beieinander liegen, und die Pareto-Verteilung der Knotengrade folgt aus der exponentiellen Expansion des hyperbolischen Raumes. Durch die hyperbolische Geometrie wird jedoch auch die mathematische Analyse des Modells schnell kompliziert.

In dieser Arbeit studieren wir die strukturellen und algorithmischen Eigenschaften von hyperbolischen Zufallsgraphen. Wir beginnen mit der Analyse von Cliquen. Wir beobachten, dass wenn der Pareto-Exponent β zwischen 2 und 3 liegt, es Cliquen von polynomieller Größe in n gibt. Mit β >= 3 ist die größte Clique noch logarithmisch groß, was früheren Modellen mit konstanter Cliquengröße stark widerspricht. Wir geben auch einen effizienten Algorithmus zur Cliquenfindung an, wenn die Koordinaten der Knoten bekannt sind. Als Zweites analysieren wir den Durchmesser, also den längsten kürzesten Pfad in hyperbolischen Zufallsgraphen. Wir beweisen, dass er O(log^2/3-β n) lang ist, wenn 2 < β < 3, und O(log n) falls β > 3. Komplementär dazu zeigen wir, dass der Durchmesser mindestens Ω(log n) beträgt. Als Drittes entwickeln wir einen Algorithmus, der reale Netzwerke in die hyperbolische Ebene einbettet. Um eine gute Qualität zu gewährleisten, evaluieren wir den Algorithmus auf über 6000 zufällig generierten hyperbolischen Graphen. Weiterhin betten wir exemplarisch den Produktempfehlungsgraphen von Amazon ein und beobachten, dass Produkte aus gleichen Kategorien in der Einbettung nah beieinander liegen.