Abstract

Bei der Erforschung von sozialen Netzwerken spielt das Entdecken von Communities eine große Rolle.

Mein Kapitel beschäftigt sich in dem Zusammenhang mit Random Walks, einer stochastischen Methode um in mathematischen Räumen Zusammenhänge zu erkennen und zu analysieren. Ein bekanntes Anwendungsbeispiel des Random Walks, wäre der Page-Rank Algorithmus, der Websites bei Suchanfragen nach ihrer Popularität sortiert. Ich analysiere dabei schon bekannte Implementierungen von Random Walks, unter anderem Time-Rank, ein Algorithmus der sich mit der dynamischen zeitlichen Entwicklung von Communities beschäftigt.

Außerdem untersuche ich eine verfeinerte Version des Info-Map Community Algorithmus, welcher über gewichtete Metadaten, in Abstimmung mit der Struktur der zu untersuchenden Communities, zusammenhängende Netzwerke erkennt.

Ich betrachte weiterhin einen auf dem Markov-Modell basierten Ansatz, welcher überlappende Communities in komplexeren Netzwerken findet und diese entwirrt bzw. strukturiert darstellt. In Summe gebe ich einen prägnanten Überblick über die wichtigsten Forschungsergebnisse auf diesem Gebiet.

1.Einleitung

Die Entdeckung von Communities bekommt eine immer größere Bedeutung für die Entwicklung unserer Welt durch die gängige Verwendung sozialer Netzwerke. Für die Analyse der sozialen Netzwerke verwendet man die Graphentheorie. Netzwerke wie Twitter und Facebook stellen das Konzept der Community-Struktur innerhalb des Netzwerks dar.

Ein soziales Netzwerk wird als Netzwerkdiagramm illustriert. Das Umfassen der Suche nach den dichten Knoten dient zur Erkennung der Communities. Überschneidende Gemeinschaften sind möglich, wenn ein Knoten Mitglied mehrerer Communitys ist. Das Entdecken von Communities in sozialen Netzwerken nimmt Bezug auf die Darbietung der Communities. Sie werden von gerichteten Graphen dargestellt, in denen Kanten die Relationen zwischen den Materien verkörpern und Knoten Personen illustrieren.

In dieser Arbeit werden verschiedene Ansätze zur Erkennung der sich überlappenden Gemeinschaften in den sozialen Netzwerken behandelt. Dieser Beitrag beschäftigt sich damit, die Fähigkeiten und Grenzen von “overlapping” Community-Erkennungsalgorithmen zu offerieren.

Ein präferierter Community-Erkennungsalgorithmus ist der Random Walk, den ich in dieser Arbeit erarbeite. Der Random Walk-Algorithmus (zufällige Schrittfolge) ist ein mathematischer Komplex für einen Ablauf, bei dem die individuellen Schritte sich zufällig ergeben.

Hierbei handelt es sich um einen Prozess aus der Stochastik, in der mit autonomen und identisch verteilten Zunahmen eine Bewegung in diskreter Zeit veranlasst wird. Er stellt zufällige Pfade in einem Diagramm dar.

Dieser sogenannte zufällige Spaziergang bedeutet, dass wir an einem Knoten beginnen, einen Nachbarn auswählen, zu dem wir zufällig oder basierend auf einer bereitgestellten Wahrscheinlichkeitsverteilung navigieren möchten, und dann dasselbe von diesem Knoten aus tun, wobei der resultierende Pfad in einer Liste beibehalten wird.

Abb.1: 2D Random Walk basierend auf:

Von

mit verschiedenen Basen

für jedes

Ein Schritt wird die in die Richtung gemacht

Aus Gründen der Klarheit

Der Schritt wird mit einem

Wert:

Der Random Walk wird häufig als ein Teil anderer Algorithmen verwendet als Teil der node2vec- und graph2vec-Algorithmen, die Knoteneinbettungen erstellen. Noch dazu kann es als Teil der Walk Trap und Info-Map Community Erkennungsalgorithmen verwendet werden.

Wenn ein zufälliger Spaziergang wiederholt wird, dann wird eine kleine Teilmenge von Knoten zurückgeben. Dies weist darauf hin, dass diese Knotengruppe möglicherweise eine Communitystruktur aufweist.

Der Random Walk-Algorithmus wird im Folgenden anhand eines Anwendungsbeispiels, dem PageRank Algorithmus erörtert, aufgefasst und graphisch illustriert. Zum Schluss werden die Resultate ausgewertet und summarisch dargestellt.

Noch dazu werden verwandte Arbeiten wie der Anwendungsalgorithmus Info-Map, Time-Rank und das Markov-Modell näher beschrieben. Der motivierende Grundgedanke für die aktuelle Arbeit ist es, ein zeitliches Netzwerk einem gewichteten statischen Netzwerk zuzuordnen, in dem die Gewichtungen zeitliche Beziehungen erfassen.

Anschließend kann jeder vorhandene Algorithmus für die Community-Erkennung auf das statische Netzwerk angewendet werden, und schließlich können die Communities des statischen Netzwerks wieder dem ursprünglichen zeitlichen Netzwerk zugeordnet werden. Die Hauptbeiträge dieses Beitrags sind: PageRank, Time Rank, Info-Map und das Markov-Modell, welche zufällige Walk-Algorithmus für die dynamische Community-Erkennung sind, die auf vorausgehenden Algorithmen für die Community-Erkennung in multirelationalen Netzwerken basieren.

2.Verwandte Arbeiten

Der Info-Map-Algorithmus versucht, eine Kostenfunktion zu minimieren. Die Partitionierung basiert auf dem Fluss, der durch das Muster der Verbindungen in einem bestimmten Netzwerk induziert wird. Wenn man bedenkt, dass ein Absender vorgibt, einem Empfänger einen zufälligen Pfad innerhalb eines Netzwerks zu übermitteln, wird Folgendes angenommen:

Es soll die Größe dieser Nachricht reduziert werden. Eine immediate Strategie wäre, jedem Knoten einen anderen Code zuzuweisen und dem Empfänger die entsprechende Folge zu senden. Eine äquivalente Konzeption, das als Markov-Kette bezeichnet wird, war zuvor in der statistischen Literatur entwickelt worden. Eine Markov-Kette hat eine endliche Reihe von Paaren \(p(xy)\).

Für jedes Paar der Zustände \(x\) und \(y\) gibt es eine Übergangswahrscheinlichkeit, von Zustand \(x\) in den Zustand \(y\) zu wechseln, wo für jedes \(x\),\((-y)\) gilt: \(p\left(xy\right)=1\). Ein Random Walk in der Markov-Kette beginnt in einem bestimmten Zustand.

Zu einem bestimmten Zeitschritt, wenn es im Zustand \(x\) ist, wird der nächste Zustand \(y\) zufällig mit Wahrscheinlichkeit \(p(xy)\) ausgewählt. Eine Markov-Kette kann durch ein gerichtetes Diagramm mit einem Scheitelpunkt dargestellt werden, der jeden Zustand darstellt, und einer Kante mit der Gewichtung \(pxy\) von \(xx\) zu \(xy\). Wir sagen, dass die Markov-Kette verbunden ist, wenn die unterliegende gerichtete Graphik stark verbunden ist. Das heißt, wenn es einen gerichteten Pfad von jedem \(x\) zu jedem anderen \(x\) gibt. In diesem Abschnitt beschreiben wir die vorgeschlagene Methode, Time-Rank, einen zufälligen Walk-Algorithmus für die dynamische Community-Erkennung, der auf MutuRank basiert.

Die ersten beiden Dimensionen beziehen sich auf die Knoten und die dritte Dimension auf die Zeitrahmen, die im Wesentlichen die Zeitrahmen als Beziehungen behandeln. Ein Tensor “Slice” für einen bestimmten Zeitrahmen stellt die Adjazenz-Matrix des Netzwerks zu diesem Zeitpunkt dar. Der Unterschied in unserer Darstellung besteht darin, dass Knoten \(i\) in jedem Slice durch eine Reihe unterschiedlicher Knoten dargestellt wird, einen für jeden Zeitrahmen, den wir Knotenbilder nennen. Lassen Sie \(N\) die Anzahl der Knoten und \(T\) die Anzahl der Zeitrahmen sein. Dann wird Knoten \(i\) tatsächlich ein Satz der verschiedenen Bilder des Knotens sein, eines für jeden Zeitrahmen, \(i=i_1,i_2,\ldots,i_T\). Auf diese Weise ist die Anzahl der verschiedenen Knoten in unserer Darstellung \(N-T\). Die Abmessungen des neuen Tensors sind \(\left(N-T\right).\left(N^\prime T\right)^\prime\left(T\right)\).

3.Methodik

Wie im Kapitel “Verwandte Arbeiten” schon erwähnt wurde, handelt es sich bei dem Algorithmus um eine von drei Anwendungsbeispielen des Random Walks. Während jedoch beim Time-Rank jeder Knoten nur ein Label hat, welches nach den am häufigsten vorkommenden Labeln seiner Nachbarn aktualisiert wird, wird beim PageRank jedem Knoten erlaubt alle nötigen Knoten auszulesen. Wir untersuchen das Verhalten von Netzwerk Diffusionen basierend auf dem zufälligen Walk von PageRank aus einer Reihe von Seed-Knoten. Diese Diffusionen sind dafür bekannt, kleine, lokalisierte Cluster (oder Communities) und auch große Cluster auf Makroebene aufzudecken, indem sie einen Parameter variieren, der eine duale Interpretation als Genauigkeitsgebunden und als Regularisierungsebene aufweist. Wir schlagen eine neue Methode vor, die das Ergebnis der Diffusion für alle Werte dieses Parameters schnell annähert. Unsere Methode generiert effizient einen ungefähren Lösungspfad oder Regularisierungspfad, der mit einer PageRank-Diffusion verknüpft ist, und zeigt Clusterstrukturen auf mehreren Größenskalen zwischen klein und groß. Wir zeigen eine Laufzeit gebunden auf diese Methode, die unabhängig von der Größe des Netzwerks ist, und wir untersuchen mehrere Optimierungen zu unserer Methode, die in einigen Einstellungen praktischer sein können. Wir zeigen, dass diese Methoden verfeinerte Clusterstrukturen in einer Reihe von realen Netzwerken mit bis zu 2 Milliarden Kanten identifizieren. Die Einschränkungen von PageRank gelten auch für Random Walks: Dead-Ends treten auf, wenn Seiten keine Out Links haben. In diesem Fall wird der zufällige Spaziergang abgebrochen, und ein Pfad, der nur den ersten Knoten enthält, wird zurückgegeben. Dieses Problem kann vermieden werden, indem die Richtung übergeben wird: BOTH-Parameter, so dass der zufällige Spaziergang Beziehungen in beide Richtungen durchläuft. Wenn innerhalb einer Gruppe von Seiten keine Links zu außerhalb der Gruppe vorhanden sind, wird die Gruppe als Spinnenfalle betrachtet. Zufällige Wanderungen, die von einem der Knoten in dieser Gruppe beginnen, werden nur zu den anderen in der Gruppe durchqueren - unsere Implementierung des Algorithmus erlaubt es nicht, dass ein zufälliger Spaziergang zu nicht benachbarten Knoten springt.

PageRank ist eine der Methoden, mit der Google die Relevanz oder Bedeutung einer Seite bestimmt. Es ist nur ein Teil der Geschichte, wenn es um die Google-Liste kommt, aber die anderen Aspekte werden an anderer Stelle diskutiert (und ändern sich ständig) und PageRank ist interessant genug, um ein eigenes Papier zu verdienen.

PageRank wird auch auf der Symbolleiste Ihres Browsers angezeigt, wenn Sie die Google-Symbolleiste (https://toolbar.google.com/) installiert haben.

Aber der Toolbar PageRank geht nur von 0 bis 10 und scheint so etwas wie eine logarithmische Skala zu sein:

Toolbar PageRank $$ (log base 10) Real PageRank 0 0 - 10

1 100 - 1,000

2 1,000 - 10,000

3 10,000 - 100,000

4 and so on…

Aus https://www.cs.princeton.edu/~chazelle/courses/BIB/pagerank.htm

Wir können die genauen Details der Skala nicht kennen, denn wie wir später sehen werden, ändert sich der maximale PR aller Seiten im Web jeden Monat, wenn Google seine Neuindizierung durchsetzt. Wenn wir davon ausgehen, dass die Skala logarithmisch ist, dann könnte Google einfach der höchsten tatsächlichen PR-Seite eine Symbolleiste PR von 10 geben und den Rest entsprechend skalieren.

PageRank ist eine “Abstimmung”, von allen anderen Seiten im Web, darüber, wie bedeutsam eine Webseite ist. Ein Link zu einer Seite zählt als Unterstützungsvotum. Wenn es keinen Link gibt, gibt es keine Unterstützung.

Aus dem ursprünglichen Google-Papier zitiert: ,,Wir gehen davon aus, dass Seite A die Seiten \(T_1,\ldots,T_k\)hat, die auf A verlinken . Der Parameter \(d\) ist ein Dämpfungsfaktor, der zwischen 0 und 1 eingestellt werden kann. Normalerweise setzen wir \(d\) auf 0,85. Weitere Details zu \(d\) finden Sie im nächsten Abschnitt. Auch \(C(A)\) ist definiert als die Anzahl der Links, die von Seite \(A\) ausgehen. Der PageRank einer Seite \(A\) wird wie folgt angegeben: \(PR(A)=(1-d)+d(PR(T_1) C(T_1) +\ldots+PR(T_k) C(T_k)\)

PageRank oder \(PR(A)\) kann mit einem einfachen Algorithmus berechnet werden.

\(PR(T_k)\) - Jede Seite hat ihre eigene Vorstellung von Selbstbedeutung. Dies ist “\(PR(T_1)\) “ für die erste Seite im Web bis hin zu “\(PR(T_k)\) “ für die letzte Seite.

\(C(T_n)\) - Jede Seite verteilt ihre Stimme gleichmäßig unter allen ausgehenden Links. Die Anzahl oder Anzahl der ausgehenden Links für Seite 1 ist “\(C(T_1)\)”, “\(C(T_n)\)” für Seite n usw. für alle Seiten.

• \(\ PR(T_k)/C(T_k)\) - wenn also unsere Seite (Seite A) einen Back link von Seite “k” hat,

erhält der Anteil der Abstimmungsseite A “ \(PR(k)/C(T_k)\) “

• d (… - Alle diese Stimmenfraktionen werden addiert, aber um zu verhindern,

  dass die anderen Seiten zu viel Einfluss haben, wird diese Gesamtstimme durch Multiplikation mit 0,85 “gedämpft” (der Faktor “d“) ist der Dampffaktor \((1 - d)\) Der PR jeder Seite hängt von den PR der Seiten ab, die darauf verweisen. Jedoch wissen wir nicht, welchen PR diese Seiten haben, bis die Seiten, die auf sie zeigen, ihr PR berechnet haben. Das bedeutet für, dass wir einfach weitermachen und die PR einer Seite berechnen können, ohne den Endwert der PR der anderen Seiten zu kennen. Das scheint seltsam, aber im Grunde, jedes Mal, wenn wir die Berechnung ausführen, bekommen wir eine nähere Schätzung des Endwerts. Also alles, was wir tun müssen, ist, sich den einzelnen Wert, den wir berechnen, zu merken und die Berechnungen so oft zu wiederholen, bis die Zahlen aufhören, proportional zu steigen. Beispielnetzwerk: zwei Seiten, die jeweils auf die andere zeigen: Jede Seite hat einen ausgehenden Link (ausgehende Anzahl: \(1, C\left(A\right)=1\) und \(C\left(B\right)=1).\) d=0.85 \(PR(A)=(1-d)+d(PR(B)/1) PR(B)=(1-d)+d(PR(A)/1)\) Also gilt: \(PR(A)=0,15+0,85(PR(B)) PR(B)=0,15+0,85(PR(A)\) Nach einer Initialisierung der beiden PageRanks mit jeweils 0,5 ergibt sich nach mehreren Iterationen: \(PR(A)=PR(B)=1\) Hier lässt sich auch leicht erkennen, dass dies die endgültigen Werte der PageRanks der beiden Seiten sind. Aus https://www.cs.princeton.edu/~chazelle/courses/BIB/pagerank.htm

4.Funktionsweise von PageRank

Das Grundprinzip ist, dass je mehr Links auf eine Seite verweisen, desto höher ist der PageRank. Denn wenn der PageRank hoch ist, dann hat die Webseite eine große Bedeutung und wird bei der Google-Suche ganz oben angezeigt.

Der PageRank bezieht sich bei seiner Auswahl nicht auf die Qualität der Webseite. Zurzeit ist es jedoch so, dass der PageRank seine Wert verloren hat, da zur heutigen Zeit viele verschiedene Faktoren, die Rankings von Webseiten dirigieren.

Pseudocode: (PageRank) Die hier im Pseudocode verwendete Formel für den PageRank ist eine etwas abgewandelte Version der oben genannten Formel, wodurch jeder PageRank einen stochastischen Wert hat.

Wobei hier \(P\) die Menge aller Knoten des Graphen \(G\) sind, welcher das vorliegende Netzwerk modelliert. procedure PageRank (𝐺,𝑖𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛)

𝑑=0,85
𝑜ℎ=𝐺.𝑜𝑢𝑡𝑙𝑖𝑛𝑘𝐶𝑜𝑢𝑛𝑡𝐻𝑎𝑠ℎ
𝑖ℎ=𝐺.𝑖𝑛𝑙𝑖𝑛𝑘𝐶𝑜𝑢𝑛𝑡𝐻𝑎𝑠ℎ
𝑛=𝐺.𝑔𝑒𝑡𝑁𝑜𝑑𝑒𝐶𝑜𝑢𝑛𝑡
𝐟𝐨𝐫 𝐚𝐥𝐥 p in the Graph 𝐝𝐨
𝑝𝑟[𝑝]=1/𝑛			//PageRank
 
𝐞𝐧𝐝 𝐟𝐨𝐫
𝐰𝐡𝐢𝐥𝐞 𝑖𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛>0 𝐝𝐨
𝑑𝑝=0					//modification adder

𝐟𝐨𝐫 𝐚𝐥𝐥  𝑝 ℎ𝑎𝑠 𝑛𝑜 𝑜𝑢𝑡𝑙𝑖𝑛𝑘𝑠 𝐝𝐨
	
	𝑑𝑝=𝑑𝑝+𝑑∗𝑝𝑟[𝑝]/𝑛		//modification for pages without outgoing links

𝐞𝐧𝐝 𝐟𝐨𝐫

𝐟𝐨𝐫 𝐚𝐥𝐥 𝑝 in G 𝐝𝐨	
𝑛𝑝𝑟[𝑝]=𝑑𝑝+(1−𝑑)/𝑛 		//npr = modificated PageRank
𝐟𝐨𝐫 𝐚𝐥𝐥 𝑝_𝑖  in 𝑖ℎ[𝑝_𝑖 ]  𝐝𝐨
𝑛𝑝𝑟[𝑝]=𝑛𝑝𝑟[𝑝]+(𝑑∗𝑝𝑟[𝑝_𝑖 ])/𝑜ℎ[𝑝_𝑖 ]
	𝐞𝐧𝐝 𝐟𝐨𝐫

𝐞𝐧𝐝 𝐟𝐨𝐫
          
          𝑝𝑟=𝑛𝑝𝑟
          
          𝑖𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛=𝑖𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛−1
𝐞𝐧𝐝 𝐰𝐡𝐢𝐥𝐞
𝐞𝐧𝐝 𝐩𝐫𝐨𝐜𝐞𝐝𝐮𝐫𝐞

Die einzureichende Java Implementierung liegt in einer extra Datei vor.

5.Laufzeit

Bei einer Analyse des obigen Pseudocodes ergibt sich im Worst-Case eine asymptotische Laufzeit von O(n^2) , falls n die die Anzahl der Knoten ist. Diese Laufzeit kommt dadurch zustanden, dass es insgesamt bei \(i\) Iterationen im Worst-Case zu \((n+i+(n*n))\) Änderungen des PageRanks kommt, was dann asymptotisch die schon erwähnte Laufzeit von \(O(n^2)\) ergibt. Hier ist aber zu beachten, dass der analysierte Pseudocode eine recht naive Implementierung des PageRanks ist, wodurch die Laufzeit in realen Implementierungen deutlich besser ist. Hier ergeben sich Laufzeiten von \(O(n+m)\), wobei m die Anzahl der Kanten des Graphen, also die Links ist. Die Analyse vom obigen Pseudocode weist nach, dass \(n\) Knoten die Laufzeit \(-> n+ Iteration*(n²)\) im Worst-Case beträgt. Somit ergibt sich bei diesem Pseudocode \(O(n²)\). Da der Pseudocode eine naive Implementierung hat, kann es sein,dass es bei anderen Implementierungen \(O(nO(n^2)+M\)

6.Vergleich PageRank mit Time Rank

Wenn man beide Algorithmen miteinander vergleicht, dann ergibt sich, dass in PageRank, jedem Knoten erlaubt wird alle nötigen Knoten auszulesen und bei Time Rank, dass jeder Knoten nur einem Label zugewiesen wird, welches sich nach den häufigsten vorkommenden Labeln seiner Nachbarn aktualisiert wird.

7.Vergleich PageRank mit Info Map

Bei einem Vergleich der beiden Algorithmen PageRank und Info Map zeigt sich auf, dass bei PageRank es so ist, dass je mehr Links auf einer Webseite zeigen, desto höher ist der PageRank der Seite und bei Info Map wird das Verhalten vom Informationsfluss, der Webseiten nachgewiesen.

8.Zusammenfassung und Ausblick

Dieses Paper beschreibt den Random Walk und erklärt dessen Grundidee. Der Random Walk ist eine gute Möglichkeit, durchschnittliches humanes Sozialverhalten in sozialen Netzwerken zu simulieren. Eines der bekanntesten Anwendungsbeispielen ist der PageRank, der seine Bedeutung verloren hat.

9.Referenzen