Skip to main content


Zutaten: Zucker, Kakaomasse (50%), Milchzucker, Weizenmehl, Vollmilchpulver, Magermilchpulver, Butterreinfett, Sahnepulver, Butter (1,4%)
Kann Spuren von Analysis und Geometrie enthalten.

iV_beitrag_33_titel_hyperbolisch

Hyperbolische Geometrie für Serververbindungen I

Ben hat in Nature Communications einen interessanten Artikel von Marián Boguñá und Kollegen über die Modellierung des Internets mit hyperbolischen Geometrien gelesen. Er versucht, das rechnerisch nachzuvollziehen, doch es ist schwieriger als erwartet. So fragt er Rike.

Ben Hi, Rike, ich hab‘ da so ein sogenanntes Einstein-Modell für das globale Internetsystem. Es geht darum, immer mehr Server zu verbinden, die Geometrie der Erde aufzugreifen und kurze Verbindungswege zu schaffen. Mit einer hyperbolischen Geometrie auf dem Kreis kann das sehr gut simuliert werden. Da passen (weiter draußen und am Rand) unendlich viele Punkte rein. Also genug Platz für zukünftige Server. Nur diese hyperbolische Geometrie, die macht mir echt zu schaffen.

Rike Na! Erklär doch mal das Einstein-Modell.

Ben Das geht so. Wir platzieren die Server der Welt auf einem Kreis. Eine Kugel wäre noch viel besser, aber wir fangen mit dem Kreis an. Wir könnten die Hälfte der Erde auf einen Halbkreis projizieren und die gegenüberliegende Seite au dem anderen Halbkreis. Okay?

Rike Klar! Aber das ist nicht das Problem?

Ein Netzwerk als Graph

Ben Nein. Zuerst haben wir so eine Art Graph. Die Vertices (Knoten) sind die Server, die Edges (Kanten) sind die Verbindungen. So, hier mal ein Beispiel.

iV_33_bild1_02
Vertices (gelb) und Edges (blau) eines Netzwerkes.

Rike Ich weiß.

Ben Jedem Vertex wird ein Degree k (Grad) zugeordnet. Das ist die Anzahl seiner Nachbarn, mit denen er verbunden ist.

Rike Na gut, in Deinem Beispiel ist

Ben Hast Du Dich schon mal mit Graphentheorie beschäftigt?

Rike Ach! Nö!

Das Einstein-Modell

Ben Okay. Jetzt wird im Einstein-Modell vorgeschrieben, dass die Vertices auf dem Kreis mit dem Mittelpunkt in Null gleichmäßig verteilt sind. Ungefähr so:

iv_33_Bild_8_04
Einstein-Modell mit 8 Vertices. 7 sind gleichmäßig auf dem Kreis mit dem Radius rj verteilt. θ01 ist der Winkel zwischen dem 0. und 1. Vertex.

Und die radiale Verteilung der Vertices wächst exponentiell zum Rand R hin. Dafür gibt es eine Formel:

Rike Gut. Das zeichne ich mal. Was ist α?

Ben α ist ein Parameter. Warte, ich liste alle Parameter auf:

Freie Parameter

N … Anzahl der Vertices des Netzwerkes
γ … Exponent der Verteilung der Degrees: p(k) ~ k, γ > 2
r … Radius eines Vertex, Abstand vom Mittelpunkt des Kreises
θij … Winkel zwischen den Verbindungen der Vertices Vi und Vj zum Nullpunkt
T … „Temperatur“ des Netzwerkes,

Abhängige Parameter

α … Parameter, aus γ zu berechnen:

… mittlerer Degree

c … Maß für Clusterbildung

R … Radius des Modells

Rike Ooooh! Das hast Du Dir ja was Tolles ausgesucht! Also für T = 0,5, γ = 2,5 kriege ich

R hängt von N und der Topologie ab.

Ben Richtig. Lass uns unser kleines Beispiel mit N = 8 nehmen.

Radiale Verteilung der Vertices

Die Dichte ρ wächst dann exponentiell mit dem Radius r. Das ist klar.

iV_33_dichte_radius_N_8_09
Verteilungsfunktion ρ der Vertices in Abhängigkeit von ihrer Entfernung r zu Null für N = 8, T = 0,5, γ = 2,5 und der Topologie von oben.

Hyperbolischer Abstand zweier Vertices

Jetzt fangen meine echten Schwierigkeiten an. Zwei Vertices Vi und Vj mit den Radien ri bzw. rj und dem Winkel θij zwischen ihnen bekommen den hyperbolischen Abstand xij, der soll so ausgerechnet werden:

Diese Formel überschaue ich nicht. Ich habe echt kein Gefühl dafür. Außerdem macht mir dieser Areakosinus ein paar Probleme.

Rike Hey, Ben, paß auf. Ich zeichne Dir mal den Sinus hyperbolicus und den Kosinus hyperbolicus. Die kriegen für Dein R = 7,43 schon sehr große Werte nahe 800 und unterscheiden sich kaum noch.

iV_33_sinh_N_8__radius_07
Sinus hyperbolicus für 0 ≤ r ≤ R

 

iV_33_cosh_N_8_radius_07
Kosinus hyperbolicus für 0 ≤ r ≤ R

 

Bei Null (r = 0) kannst Du sie unterscheiden, wenn Du genau hinsiehst, denn es ist

Und wenn Du die Umkehrfunktion von Kosinus hyperbolicus bildest, für

ist das

Diese Areakosinus hyperbolicus-Funktion ist nur für Werte f ≥ 1 erklärt. Verstehst Du, wenn die Werte für cosh xij kleiner als 1 werden, kannst Du keinen Areakosinus hyperbolicus bilden. Dann hast Du eine paar Ungenauigkeiten in Deiner Rechnung.

iV_33_arccosh_radius_06
Areakosinus hyperbolicus für 1 ≤ f ≤ cosh R

Ben Aaah, numerische Instabilität beim Punkt (1, 0), das muss ich prüfen. Doch ich habe immer noch keine Vorstellung von diesem hyperbolischen Abstand.

Spezialfall: 2 Vertices auf dem Durchmesser

Rike Weißt Du was, wir rechnen mal den Fall, wenn 2 Server auf dem Durchmesser des Kreises liegen.

Ben Ja, schön!

iv_333_hyperbol_abstand_theta_1_05
Spezialfall zur Berechnung des hyperbolischen Abstandes der Vertices i und j

 

Rike Dann ist dieser Winkel θij zwischen ihnen

Ben Ja, dann wird

Rike Stimmt. Weiter!

Jetzt nehmen wir ein Additionstheorem für die Hyperbelfunktionen:

Ben Mensch, Rike! Ich Idiot nutze immer nur die Formel, ich implementiere die direkt, aber Du hast noch mehr Informationen, dann kannst Du die Fomel vereinfachen!

Rike Haha, quick and dirty! Die Informatiker! Lass mich das zu Ende bringen. Wir greifen die Formel für xij wieder auf:

Jetzt wendest Du auf beide Seiten die Umkehrfunktion nur für nichtnegative Werte an und kriegst

Richtig? xij soll nichtnegativ sein?

Ben Ja! Na! Jetzt habe ich den Abstand der beiden Punkte, der ist der Abstand der Radien, schön, aber der sieht mir doch recht euklidisch aus! Wo ist denn jetzt das hyperbolische?

Rike Auf dem Durchmesser ist er euklidisch. Der maximale Abstand auf dem unteren Halbkreis ist R und der minimale ist 0.

Hyperbolischer Abstand in Abhängigkeit vom Winkel

Ben Und wie ändert sich der Abstand zweier Vertices auf einem Kreis, wenn ich den Winkel vergrößere?

Rike Ach, wenn Du Deinen Computer einmal im Kreis herumschiebst?

Ben Rike, nein, einmal durch Europa!

Rike Haha, also wir setzen dann die beiden Radien gleich und lassen den i. Server stehen und der andere mit der Nummer j fährt im Kreis herum?

iv_333_hyperbol_abstand_theta_0_08
Setting zur Untersuchung der Abhängigkeit des hyperbolischen Abstandes xij vom Winkel θij.

Ben Ja!

Rike Okay, analytisch vereinfacht sich nicht viel. Für

kriegen wir

Weißt Du, da nehmen wir wieder ein Additionstheorem für die Hyperbelfunktionen:

Das stellen wir nach dem Kosinus hyperbolicus um und kriegen:

und das setzen wir in Deine Abstandsformel ein:

und schließlich

Tolle Sache!

Ben Was???

Rike Das können wir numerisch berechnen, hier, ist doch kein Problem!

Ben Was hast Du für einen Radius für die Kreisfahrt genommen?

Rike Warte, für verschiedene Radien r kriege ich verschiedene Kurven.

iv_33_abstand_theta_8_12
Hyperbolischer Abstand xij des Einstein-Modells in Abhängigkeit vom Winkel θij.

Ben Okay, weiter draußen sind die Abstände viel größer, schon bei der kleinsten Drehung! Ja gefällt mir, dieser hyperbolische Abstand. Super!

***

Übungsaufgaben

  1. Wie vereinfacht sich die Formel für xij auf dem oberen Halbkreis?
  2. Wie verändert sich R in Abhängigkeit von N und c?
  3. Wie wirkt sich das auf den Abstand xij aus?

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Wir freuen uns, dass Du einen Kommentar hinterlassen möchtest. Denk bitte daran, dass Du dich durch das Abschicken des Kommentars mit unseren Nutzungsbedingungen einverstanden erklärst.