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_38_mallorca-titel_02

Bens kleines Laplace-Netz

Ben und Rike haben ein mittelgroßes Servernetz nach dem Einstein-Modell aufgebaut, getestet und simuliert. Als dann endlich alles lief, waren sie sehr glücklich. Sie haben ihre Präsi gehalten und sich ein paar Tage Auszeit gegönnt. Doch so einfach kann man nicht abschalten, wenn der Kopf voll mit Gedanken an Protokolle, Hard- und Software ist.

Ben mag Servernetze und liest alles, was es darüber gibt. Zwar kann sein Institut keine Rechnernetze aus 500 PCs aufbauen – nur so zum Test – aber mit wenigen PCs und vor allem mit Simulation könnte er noch viel größere Netze testen. Das geht natürlich auch am Strand. Jetzt hat er einen Artikel gefunden, wo man ein bisschen lineare Algebra, partielle DGln. und hyperbolische Geometrie zum Simulieren braucht. Da muss er doch Rike fragen.

Laplacian-based Network Embedding

Ben Hey, Rike, ich habe hier so ein Modell, wo ein Rechnernetz nach geometrischem und physikalischem Vorbild betrachtet wird – ein Laplacian-based Network Embedding.

Rike Aha! Wärmeleitungsgleichung?

Ben Stimmt!

Rike Klar, ist fast immer Wärmeleitungsgleichung, hab ich mir schon gedacht. Ein Server gibt seine Daten wie Wärme ab – stimmt‘s?

Ben Stimmt! Komm, lass uns doch mal das Modell durchgehen!

Rike Hey – ist das Deine Auszeit?

Ben Rike, glaubst Du, dass Informatiker wirklich Urlaub machen?

Rike lacht.

Ben Ich habe eine Arbeit von Gregorio Alanis-Lobato, Pablo Mier & Miguel A. Andrade-Navarro, verdammt noch mal! ….

Rike Sag das noch mal!

Ben Okay, lass es gut sein. Also die Drei starten mit einem Servernetz, das sich durch ungerichtete, ungewichtete Graphen beschreiben lässt. Das kleinste nichttriviale Netzwerk wäre so eins:

iv_38_netzwerk_eukl_waerme_02_02
Netzwerk mit 3 Servern, der mittlere ist mit den beiden anderen verbunden.

 

Den 1. Server – den mit den meisten Verbindungen – kann man als Wärmequelle interpretieren, wie Du Dir ja denken kannst.

Rike Ja – eine schöne Metapher. Für mich ist interessant, dass einige physikalische und mathematische Modelle, wie die Wärmeleitung, auch in der Informatik und in der künstlichen Intelligenz auftauchen und nützlich sind, als wären sie universell. Aber mal schauen, was es bringt.

iv_38_netzwerk_eukl_waerme_03_03
Dasselbe Netzwerk mit dem 1. Server als „Wärmequelle“ für die beiden anderen.

 

Herleitung Laplacian

Ben Schön. Aus diesem Graphen wird nun ein Laplacian hergeleitet, für diesen werden die Eigenwerte und -vektoren berechnet und die hyperbolische Einbettung aufgestellt.

Rike Okay, zeig mal …. Aha. Zuerst nummerierst Du alle Vertices nach ihrem Degree durch, klar, das hast Du ja schon gemacht:

i = 1 … der Server mit 2 Verbindungen
i = 2 … der Server mit einer Verbindung
i = 3 … der 2. Server mit einer Verbindung

Für den Graphen sollst Du 2 Matrizen formulieren, eine in Diagonalgestalt D, da stehen die Degrees des i-ten Vertex in der i-ten Zeile, und eine Matrix A, da soll an der Stelle ij eine 1 stehen, wenn der i-te mit dem j-ten Server verbunden sind, sonst sind überall Nullen.

Ben Okay, bei meinem 3er Beispiel ist das dann

iv_38_formel_02

und

iv_38_formel_01

Rike Gut. Jetzt geht es weiter. Du bildest den Laplacian:

iv_38_formel_03

Ben Ach, iss ja nur ne Matrix!

Rike Naja, immerhin beschreibt sie vollständig das Netzwerk und hat eine Analogie zum Laplace-Beltrami-Operator in der Differentialgeometrie.

Ben Na gut.

Rike Immerhin ist er positiv definit und hat nur nichtnegative reelle Eigenwerte. Die bilden sein Spektrum.

Ben Schön!

Verallgemeinerte Eigenwerte und -vektoren

Rike Jetzt sollst Du sogenannte verallgemeinerte Eigenwerte λ und Eigenvektoren finden:

Ben Na schön, dieses D auf der rechten Seite wird schon seinen Grund haben, wenn das Netzwerk seine Daten abgibt, ist es sinnvoll, λ-Fache der Diagonalmatrix angewendet auf zu suchen.

Rike Bloß gut, dass Du ein kleines Netz hast, hier kann ich Dir die λ's ausrechnen, für größere Netzwerke brauchst Du ein intelligentes Programm. Du musst

lösen, das gibt ein Polynom in λ vom Grad 3 und bei N Servern eben vom Grad N.

Ben Hmm. Und dann?

Rike Dann löst Du für jedes λ die Vektorgleichung

Aber warte mal, hier, Alanis-Lobato scheibt, dass Du hier nur 2 Eigenwerte und die dazugehörigen Eigenvektoren brauchst, die kleinsten positiven.

Ich rechne das mal aus, warte,…, okay, hier haben wir die Eigenwerte

Die Eigenvektoren zu den positiven Eigenwerten sind:
iv_38_formel_05

und

iv_38_formel_04

Ben Rike, toll, wie Du das machst, ich hasse lineare Algebra!

Rike Ja, ich weiß, wie alle Informatiker, wer will schon Determinanten ausrechen und lineare Gleichungen lösen!

Ben Genau! Und wie geht’s weiter?

Winkel der Einbettung

Rike Die beiden verallgemeinerten Eigenvektoren zeigen in spezielle Richtungen und beschreiben, in welche Richtung der Laplacian wirkt. Ja, die Verhältnisse der Koordinaten ergeben die Einbettungswinkel θ1i in der hyperbolischen Ebene:

 

iv_38_netzwerk_hyperbol_05_04
Hyperbolische Einbettung mit Winkeln θ1i , den Radien R und ri des i-ten Vertex

 

Bei uns ist das

Ben Super!

Rike Jetzt fehlen noch die Radien.

Ben Klar, das kriege ich hin, da gibt es explizite Formeln. Anders als beim Einstein-Modell werden hier die Server mit gleichen Degrees nicht auf einem Radius angeordnet, hier werden die Radien immer größer, sie hängen von ein paar Konstanten ab:

Parameter des Netzes

γ ist ein Parameter des Netzwerkes, γ > 2, wie beim Einstein-Modell, er ist eigentlich ein Faktor zur Beschreibung der Verteilung der Grade, aus ihm wird der nächste Parameter β berechnet:

Dann haben wir noch:

… Anzahl der Vertices
…“Temperatur“ des Netzes,
… ist der mittlere Degree der Vertices

Radien der Einbettung

Den Radius des hyperbolischen Kreises können wir jetzt berechnen, die Formel lautet:

Weiter, der Radius ri  jedes Vertex wird so berechnet:

Rike Warte, ich berechne Dir das. Was sollen wir für γ und T nehmen?

Ben Wie beim letzten Mal:

Rike Okay, dann hast Du:

Ben Schön, das Netzwerk mit der Laplace-Einbettung selbst entsteht durch Verbindung aller Server i zu j, i > j:

iv_38_netzwerk_hyperbol_05_03
Laplacian-based Network Embedding

 

Hyperbolische Abstände und Verbindungswahrscheinlichkeiten

Die hyperbolischen Abstände xij zwischen den Servern i und j sind wieder:

 

iv_38_hyper_abstand_05
Hyperbolischer Abstand xij der Vertices ij für T= 0,5, γ = 2,5

 

Daraus berechnen wir die Verbindungswahrscheinlichkeiten pij der Serververbindung ij mit derselben Exponentialverteilung und kriegen:

iv_38_exponentielle_wahrscheinlichkeit_05
Verbindungswahrscheinlichkeit pij der Server i und j nach der Exponentialverteilung und denselben Parametern

 

Ben Nicht schlecht! Die Verbindungswahrscheinlichkeit für die ersten beiden Server ist 0,75, für den 1. und 3. ist sie etwas kleiner: 0,64 und für den 2. und 3. Server ist sie 0,32. Das macht Sinn, das gefällt mir! Rike, jetzt verstehe ich es ganz gut, aber wer hilft mir, diese Eigenwerte und Eigenvektoren für größere Netze auszurechnen?

Rike Ich glaube, das hat schon jemand implementiert, Du brauchst es nur runterzuladen!

Ben Ooooh, dann tue ich das mal und wir können unsere kleine Auszeit fortsetzen!

Rike Hahaha!

***

Übungsaufgaben

  1. Wie drückt sich die Metapher der Wärmeleitungsgleichung mathematisch aus?
  2. Bleibt die Topologie des Netzes beim Laplacian-based Network Embedding unverändert?

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.