Wer ist wichtig in einem Netz?

In der 11. Klasse beschäftigen sich Schüler in Informatik mit Graphen. Keine Funktionsgraphen, wie man sie aus der Mathematik kennt, sondern Graphen, die aus einem Haufen Knoten bestehen, die durch einen Haufen Kanten mehr oder weniger miteinander verbunden sind.

Es geht dabei vor allem darum, Situationen mit Graphen zu modellieren (also: Textaufgaben), und dieses Modell dann mit einem Computer umzusetzen. Nach dem Erzeugen des Graphen sollen die Schüler außerdem einige Methoden programmieren können, die man bei Graphen einsetzen kann.

Hier ist ein Beispielgraph:

graph_zentralitaet

Die Kanten sind der Einfachheit halber ungerichtet, gelten also in beide Richtungen, und ungewichtet, sind also alle gleich „lang“, was auch immer das konkret heißt. Sie könnten bedeuten: „hat Telefonnummer von“, oder „will sitzen neben“ oder „lässt Hausaufgaben abschreiben“.

Programmieraufgaben bei Graphen

Im Lehrplan steht eine Methode zur „Traversion“ oder zum „Durchlauf“ eines Graphen. Dabei muss man jeden Knoten mindestens einmal besuchen. Man kann sich so einen Graphen als Labyrinth vorstellen, jede Kante ist eine Wegstrecke im Labyrinth und jeder Knoten eine Weggabelung oder eine Sackgasse. Nach welchem Algorithmus geht man vor, wenn man wirklich überall im Labyrinth mal gewesen sein möchte, etwa um nach einem Schatz oder Ausgang zu suchen, und ohne einen Knoten zu übersehen?

Am einfachsten ist da wohl ein Algorithmus, der „Tiefensuche“ heißt, und deshalb programmiert man meist den. Ein anderer, der Dijkstra-Algorithmus, sagt einem darüber hinaus noch den kürzesten Weg (statt eines x-beliebigen) vom Startknoten zu den anderen Knoten.

Aber es gibt noch schöne andere Aufgaben, die man mit Schülern mit einem Graphen programmieren kann. Die folgenden beschäftigen sich alle damit, wie wichtig ein Knoten im Graphen ist.


1. Welcher Knoten ist am häufigsten mit anderen Knoten verbunden? (Bei gerichteten Graphen: zu welchem Knoten gehen am meisten Kanten hin, von welchem führen am meisten weg?) Damit misst man die Gradzentralität. Im Graph oben hat Linda eine degree centrality von 7. Vielleicht ist sie die beliebteste Schülerin?

2. Andererseits ist der beliebteste Schüler nicht unbedingt der wichtigste. Welcher Knoten ist derjenige, der allen anderen Knoten am nächsten ist? Man könnte sich das so vorstellen: Mit welchem Knoten müsste man beginnen, etwa mit einem Telefonanruf, der von Knoten zu Knoten weitergereicht wird, um am schnellsten alle anderen Knoten erreicht zu haben? Im Graph oben ist Oscar der einzige, der maximal 3 Schritte von jedem anderen Knoten entfernt ist.
Im Durchschnitt ist allerdings Quentin am besten vernetzt: die Summe aller kürzesten Wege von Quentin zu allen anderen Knoten beträgt 38, bei Oscar 47, bei Linda 45, und Urmel ist mit 97 am schlechtesten integriert. Diese Art von Zentralität heißt farness beziehungsweise closeness.
(Damit Schüler das berechnen können, müssen sie erst einmal eine Methode zur Berechnung des kürzesten Wegs haben. Dazu kommt man in der Schule oft nur theoretisch, die praktische Umsetzung in Programmcode kann man vorgeben.)

3. Oder ist der Schüler der wichtigste, der die anderen Knoten zusammenhält, ohne den am Ende der Graph in fast schon unabhängige Teilgraphen zerfällt? Das heißt betweenness centrality und wird gemessen an der Anzahl der kürzesten Wege, die durch diesen Knoten führen. Der Beispielgraph besteht aus 21 Knoten, es gibt also insgesamt 210 (Formel: n*(n-1)/2) verschiedene Knotenkombinationen und ebenso viele kürzeste Wege. Wenn man mal die abzieht, die ohnehin zu einem selber führen, dann gehen 254 dieser anderen Wege über Quentin, 158 über Oscar, 155 über Linda. Wenn ich mich nicht verrechnet habe, das ist kniffliger, als ich zuerst dachte, weil man im Prinzip nicht einen kürzesten, sondern alle kürzesten Pfade braucht (es kann ja gleich kurze geben). Auch hier braucht man wieder den Dijkstra.

4. Wenn Google Webseiten bewertet, die ja mit (gerichteten) Kanten mit anderen Webseiten verbunden sind, nimmt Google wiederum eine andere Möglichkeit, Zentralität zu messen. Die basiert auf etwas, das eigenvector centrality heißt, aber das erfordert einen neuen Unterpunkt.

Nachtrag: He, das Äquivalent zum Google PageRank zu berechnen, ist gar nicht so schwer, siehe Link in den Kommentaren. Auch wenn es bei einem ungerichteten Graphen vielleicht weniger Sinn macht: Linda hat den höchsten Rank, gefolgt von Ihsan, dann mit etwas Abstand Oscar.

Eigenvector Centrality, und Google

Nehmen wir mal diesen gerichteten Graphen hier:

graphen_beispiel

NikelsenH, Creative-Commons-Lizenz Namensnennung – Weitergabe unter gleichen Bedingungen 3.0 nicht portiert

Die höchste Betweenness hat 3, die geringste Farness ebenfalls, die meisten hinführenden Kanten hat 7. Wenn man sich jetzt vorstellt, die Knoten stellen Webseiten dar und die Kanten Links auf andere Webseiten, dann versucht Google herauszufinden, welcher Knoten wohl der wichtigste ist. Betweenness und Farness und Gradzentralität sagen da aber nicht viel aus. Zum Bewerten von Seiten nutzt Google noch weitere Kriterien, aber die Häufigkeit der Verlinkung, und die Qualität der verlinkenden Seiten, spielen eine zentrale Rolle. Und diese Art von Zentralität heißt eigenvector centrality.

Kurze Frage: Bei dem Beispielgraph mit den nummerierten Knoten: Welche davon hält Google für am wichtigsten, welche für weniger bedeutsam?
Antwort: Wikipedia, wo ich den Graphen herhabe, sagt: wichtig sind 7 und 8, am unwichtigsten 1 und 6.

Wie rechnet man das aus? Uh, mh, siehe Google. Irgendwann mache ich das nochmal, aber vorerst muss ich passen. Irgendwas mit Eigenvektor, Eigenwert, Matrizen und Vektoren. Geheime MMächte der Mathematik. Andererseits… umschrieben wird diese Eigenvektor-Zentralität oft als „Wahrscheinlichkeit, mit der man bei einem zufälligen Spaziergang im Graphen auf diesen Knoten stößt“. Wenn ich schon den Eigenvektor nicht programmieren kann: tausend Spaziergänge der Länge n in einem gegeben Graphen und zählen, wie oft ich bei einem Knoten vorbeikomme, das kann ich noch. Also tausendmal einen zufälligen Startknoten ausgewählt, tausendmal bis zu n Schritte spaziert – und es kommt tatsächlich heraus, dass ich bei 7 und 8 am häufigsten und bei 1 und 6 am seltensten war!

(Pro Spaziergang bin ich maximal einmal bei 5 oder 6, denn von da aus komme ich nicht mehr anderswohin, und zwischen und 7 und 8, wenn ich erst mal dahin gekommen bin, pendle ich dann ziemlich oft hin und her, weil ich ja sonst nirgendwo hin spazieren kann.)

Google selber muss den page rank einer Seite natürlich anhand des Graphen ausrechnen, die können nicht so experimentell herangehen wie ich. Die machen das mit Mathematik.

Die Google-Matrix

Einen Graphen kann man nicht nur als Zeichnung darstellen, sondern auch in einer Form namens Adjazenzmatrix. (Englisch: adjacent, nebeneinanderliegend.) Die sieht für den allerersten Graphen oben so aus, aus Platzgründen nur der Anfang:

    Arl Ben Car Dor Eli Fel Gue Hus Ihs Jak Kar Lin Mic 
Arl  0                               1          
Ben      0   1
Car      1   0
Dor              0                   1
Eli                  0       1
Fel                      0
Gue                  1       0                   1
Hus                              0               1
Ihs  1           1                   0   1  
Jak                                  1   0
Kar                                          0   1   1
Lin                          1   1           1   0   1
Mic                                          1   1   0

Eine 1 bedeutet, dass eine Kante von dem einen Knoten zum anderen existiert. Weil der Graph oben ungerichtet ist, ist die Adjazenmatrix symmetrisch zur Diagonalen, da wo die ganzen Nuller sind.
Google benutzt genau so Adjazenzmatrix, oder doch so eine ähnliche, um den page rank von Seiten zu bestimmen. Die ist natürlich Millionen von Zeilen breit und hoch. Und grün auf schwarz, wie sich das gehört.

600px-Googlematrixwikipedia2009

Google matrix of Wikipedia (2009), taken from L.Ermann, A.D.Chepelianksii, D.L.Shepelyansky, „Towards two-dimensional search engines‘, arXiv:1106.6215; http://arxiv.org/abs/1106.6215 (GNU Free Documentation License)

Links:

3 Gedanken zu “Wer ist wichtig in einem Netz?

Schreibe einen Kommentar

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