{"id":6375,"date":"2015-03-15T08:10:06","date_gmt":"2015-03-15T07:10:06","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=6375"},"modified":"2016-01-07T19:49:29","modified_gmt":"2016-01-07T18:49:29","slug":"wer-ist-wichtig-in-einem-netz","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2015\/03\/wer-ist-wichtig-in-einem-netz.htm","title":{"rendered":"Wer ist wichtig in einem Netz?"},"content":{"rendered":"
(3 Kommentare.<\/a>)<\/small> <\/div>

In der 11. Klasse besch\u00e4ftigen sich Sch\u00fcler 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.<\/p>\n

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\u00fcler au\u00dferdem einige Methoden programmieren k\u00f6nnen, die man bei Graphen einsetzen kann.<\/p>\n

Hier ist ein Beispielgraph:<\/p>\n

\"graph_zentralitaet\"<\/a><\/p>\n

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\u00dft. Sie k\u00f6nnten bedeuten: „hat Telefonnummer von“, oder „will sitzen neben“ oder „l\u00e4sst Hausaufgaben abschreiben“.<\/p>\n

Programmieraufgaben bei Graphen<\/h3>\n

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 \u00fcberall im Labyrinth mal gewesen sein m\u00f6chte, etwa um nach einem Schatz oder Ausgang zu suchen, und ohne einen Knoten zu \u00fcbersehen?<\/p>\n

Am einfachsten ist da wohl ein Algorithmus, der „Tiefensuche“ hei\u00dft, und deshalb programmiert man meist den. Ein anderer, der Dijkstra-Algorithmus, sagt einem dar\u00fcber hinaus noch den k\u00fcrzesten Weg (statt eines x-beliebigen) vom Startknoten zu den anderen Knoten.<\/p>\n

Aber es gibt noch sch\u00f6ne andere Aufgaben, die man mit Sch\u00fclern mit einem Graphen programmieren kann. Die folgenden besch\u00e4ftigen sich alle damit, wie wichtig<\/em> ein Knoten im Graphen ist.<\/p>\n

\n

1. Welcher Knoten ist am h\u00e4ufigsten mit anderen Knoten verbunden? (Bei gerichteten Graphen: zu welchem Knoten gehen am meisten Kanten hin, von welchem f\u00fchren am meisten weg?) Damit misst man die Gradzentralit\u00e4t<\/strong>. Im Graph oben hat Linda eine degree centrality<\/em> von 7. Vielleicht ist sie die beliebteste Sch\u00fclerin?<\/p>\n

2. Andererseits ist der beliebteste Sch\u00fcler nicht unbedingt der wichtigste. Welcher Knoten ist derjenige, der allen anderen Knoten am n\u00e4chsten ist? Man k\u00f6nnte sich das so vorstellen: Mit welchem Knoten m\u00fcsste 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.
\nIm Durchschnitt ist allerdings Quentin am besten vernetzt: die Summe aller k\u00fcrzesten Wege von Quentin zu allen anderen Knoten betr\u00e4gt 38, bei Oscar 47, bei Linda 45, und Urmel ist mit 97 am schlechtesten integriert. Diese Art von Zentralit\u00e4t hei\u00dft farness<\/strong> beziehungsweise closeness.<\/strong>
\n(Damit Sch\u00fcler das berechnen k\u00f6nnen, m\u00fcssen sie erst einmal eine Methode zur Berechnung des k\u00fcrzesten Wegs haben. Dazu kommt man in der Schule oft nur theoretisch, die praktische Umsetzung in Programmcode kann man vorgeben.)<\/p>\n

3. Oder ist der Sch\u00fcler der wichtigste, der die anderen Knoten zusammenh\u00e4lt, ohne den am Ende der Graph in fast schon unabh\u00e4ngige Teilgraphen zerf\u00e4llt? Das hei\u00dft betweenness centrality<\/strong> und wird gemessen an der Anzahl der k\u00fcrzesten Wege, die durch diesen Knoten f\u00fchren. Der Beispielgraph besteht aus 21 Knoten, es gibt also insgesamt 210 (Formel: n*(n-1)\/2)<\/em> verschiedene Knotenkombinationen und ebenso viele k\u00fcrzeste Wege. Wenn man mal die abzieht, die ohnehin zu einem selber f\u00fchren, dann gehen 254 dieser anderen Wege \u00fcber Quentin, 158 \u00fcber Oscar, 155 \u00fcber Linda. Wenn ich mich nicht verrechnet habe, das ist kniffliger, als ich zuerst dachte, weil man im Prinzip nicht einen k\u00fcrzesten, sondern alle k\u00fcrzesten Pfade braucht (es kann ja gleich kurze geben). Auch hier braucht man wieder den Dijkstra.<\/p>\n

4. Wenn Google Webseiten bewertet, die ja mit (gerichteten) Kanten mit anderen Webseiten verbunden sind, nimmt Google wiederum eine andere M\u00f6glichkeit, Zentralit\u00e4t zu messen. Die basiert auf etwas, das eigenvector centrality<\/strong> hei\u00dft, aber das erfordert einen neuen Unterpunkt.<\/p>\n

Nachtrag: He, das \u00c4quivalent 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\u00f6chsten Rank, gefolgt von Ihsan, dann mit etwas Abstand Oscar.<\/em><\/p>\n

Eigenvector Centrality, und Google<\/h3>\n

Nehmen wir mal diesen gerichteten Graphen hier:<\/p>\n

\"graphen_beispiel\"<\/p>\n

NikelsenH, Creative-Commons-Lizenz Namensnennung – Weitergabe unter gleichen Bedingungen 3.0 nicht portiert<\/a><\/small><\/p>\n

Die h\u00f6chste Betweenness hat 3, die geringste Farness ebenfalls, die meisten hinf\u00fchrenden 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\u00e4t sagen da aber nicht viel aus. Zum Bewerten von Seiten nutzt Google noch weitere Kriterien, aber die H\u00e4ufigkeit der Verlinkung, und die Qualit\u00e4t der verlinkenden Seiten, spielen eine zentrale Rolle. Und diese Art von Zentralit\u00e4t hei\u00dft eigenvector centrality.<\/strong><\/p>\n

Kurze Frage: Bei dem Beispielgraph mit den nummerierten Knoten: Welche davon h\u00e4lt Google f\u00fcr am wichtigsten, welche f\u00fcr weniger bedeutsam?
\nAntwort: Wikipedia, wo ich den Graphen herhabe<\/a>, sagt: wichtig sind 7 und 8, am unwichtigsten 1 und 6.<\/p>\n

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\u00e4chte der Mathematik. Andererseits… umschrieben wird diese Eigenvektor-Zentralit\u00e4t oft als „Wahrscheinlichkeit, mit der man bei einem zuf\u00e4lligen Spaziergang im Graphen auf diesen Knoten st\u00f6\u00dft“. Wenn ich schon den Eigenvektor nicht programmieren kann: tausend Spazierg\u00e4nge der L\u00e4nge n in einem gegeben Graphen und z\u00e4hlen, wie oft ich bei einem Knoten vorbeikomme, das<\/em> kann ich noch. Also tausendmal einen zuf\u00e4lligen Startknoten ausgew\u00e4hlt, tausendmal bis zu n Schritte spaziert – und es kommt tats\u00e4chlich heraus, dass ich bei 7 und 8 am h\u00e4ufigsten und bei 1 und 6 am seltensten war!<\/p>\n

(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.)<\/p>\n

Google selber muss den page rank<\/em> einer Seite nat\u00fcrlich anhand des Graphen ausrechnen, die k\u00f6nnen nicht so experimentell herangehen wie ich. Die machen das mit Mathematik.<\/p>\n

Die Google-Matrix<\/h3>\n

Einen Graphen kann man nicht nur als Zeichnung darstellen, sondern auch in einer Form namens Adjazenzmatrix.<\/em> (Englisch: adjacent,<\/em> nebeneinanderliegend.) Die sieht f\u00fcr den allerersten Graphen oben so aus, aus Platzgr\u00fcnden nur der Anfang:<\/p>\n

    Arl Ben Car Dor Eli Fel Gue Hus Ihs Jak Kar Lin Mic \r\nArl  0                               1          \r\nBen      0   1\r\nCar      1   0\r\nDor              0                   1\r\nEli                  0       1\r\nFel                      0\r\nGue                  1       0                   1\r\nHus                              0               1\r\nIhs  1           1                   0   1  \r\nJak                                  1   0\r\nKar                                          0   1   1\r\nLin                          1   1           1   0   1\r\nMic                                          1   1   0\r\n<\/pre>\n
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.
\nGoogle benutzt genau so Adjazenzmatrix, oder doch so eine \u00e4hnliche, um den page rank<\/em> von Seiten zu bestimmen. Die ist nat\u00fcrlich Millionen von Zeilen breit und hoch. Und gr\u00fcn auf schwarz, wie sich das geh\u00f6rt.<\/p>\n
\"600px-Googlematrixwikipedia2009\"<\/p>\n
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)<\/small><\/p>\n
Links:<\/p>\n