Zum Inhalt springen
Zurück zu den Suchergebnissen

PageRank-Zentralität

Eingeführt von
Page, Brin, Motwani & Winograd
Jahr
1999
Typ
Iterative link-based centrality algorithm
Familie
Centrality

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

PageRank ist ein linkbasierter Zentralitätsalgorithmus, der jedem Knoten in einem gerichteten Graphen einen Wichtigkeitswert zuweist, indem er misst, wie viele qualitativ hochwertige Knoten auf ihn verweisen.

Eingeführt von Larry Page, Sergey Brin, Rajeev Motwani und Terry Winograd an der Stanford University im Jahr 1999, wurde er zur mathematischen Grundlage der Google-Suchmaschine und bleibt einer der einflussreichsten Algorithmen in der Netzwerkwissenschaft und Informationsbeschaffung.

Die Intuition hinter der Methode

Stellen Sie sich einen zufälligen Web-Surfer vor, der Links zufällig anklickt und gelegentlich zu einer völlig zufälligen Seite springt, anstatt einem Link zu folgen. Der Bruchteil der Zeit, den dieser Surfer auf jeder Seite verbringt, nach unendlich vielen Klicks, ist der PageRank dieser Seite. Eine Seite, die oft besucht wird – weil viele populäre Seiten auf sie verlinken – erhält eine hohe Punktzahl. Der Dämpfungsfaktor (typischerweise 0,85) modelliert die Wahrscheinlichkeit, weiterzuklicken, anstatt zu springen.

Geschichte

PageRank wurde an der Stanford University von Larry Page und Sergey Brin als Kern-Ranking-Mechanismus ihres BackRub-Suchprojekts entwickelt, das 1998 zu Google wurde. Der grundlegende technische Bericht, mitverfasst von Rajeev Motwani und Terry Winograd, wurde 1999 veröffentlicht. Der Algorithmus popularisierte die Verwendung von eigenvector-basierter Zentralität in groß angelegten gerichteten Netzwerken und inspirierte direkt nachfolgende Link-Analyse-Algorithmen, einschließlich HITS und TrustRank.

Wann wird sie eingesetzt?

PageRank ist geeignet, wenn Sie Knoten in einem gerichteten Graphen nach globaler struktureller Bedeutung einstufen müssen, insbesondere wenn die Kantenrichtung Zustimmung oder Einfluss kodiert (Hyperlinks, Zitate, soziale Follower). Er geht davon aus, dass der Graph als Markov-Kette modelliert werden kann und erfordert eine verbundene oder stark verbundene Komponente für eine saubere Konvergenz. Er ist weniger geeignet für ungerichtete Netzwerke, bei denen HITS oder Betweenness-Zentralität bevorzugt werden könnten, und er kann empfindlich auf Link-Spam oder künstlich aufgeblähten In-Degree reagieren.

Grenzen und Hinweise

  • Erfordert einen gerichteten Graphen; die Anwendung auf ungerichtete Netzwerke erfordert Konventionsentscheidungen
  • Die Konvergenzgeschwindigkeit hängt vom spektralen Abstand der Übergangsmatrix ab und kann bei schlecht verbundenen Graphen langsam sein
  • Empfindlich gegenüber der Wahl des Dämpfungsfaktors d; unterschiedliche Werte können Ranglisten erheblich verändern
  • Anfällig für Link-Farm-Manipulationen und künstlich konstruierte In-Links

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Prinzipielle probabilistische Grundlage über das Random-Surfer-Markov-Ketten-Modell
  • Skaliert auf sehr große Graphen durch dünne Matrix-Vektor-Produkte und Potenziteration
  • Erfasst die globale Graphentopologie und belohnt Knoten, die von anderen hoch bewerteten Knoten unterstützt werden
  • Weitgehend validiert in Web-, Zitations-, biologischen und sozialen Netzwerdomänen

Anwendungen

  • Ranking von Web-Suchmaschinen: Reihenfolge von Suchergebnissen nach der globalen Autorität von Webseiten
  • Analyse wissenschaftlicher Zitationen: Identifizierung einflussreicher Arbeiten oder Zeitschriften in wissenschaftlichen Literatur-Netzwerken
  • Messung des Einflusses in sozialen Netzwerken: Rangfolge von Benutzern nach dem Prestige ihrer Follower
  • Analyse biologischer Netzwerke: Identifizierung von Hub-Proteinen oder -Genen in Protein-Interaktions- und Genregulationsnetzwerken
  • Empfehlungssysteme: Weitergabe von Präferenzsignalen durch bipartite Benutzer-Artikel-Graphen

So funktioniert es

So funktioniert es

1

Jeder Knoten im Graphen beginnt mit einem gleichen PageRank-Wert von 1/N, wobei N die Gesamtzahl der Knoten ist. Diese gleichmäßige Initialisierung stellt sicher, dass kein Knoten einen künstlichen Vorsprung hat und liefert eine gültige Wahrscheinlichkeitsverteilung über das Netzwerk vor der ersten Iteration.

Formel
PR^{(0)}(v_i) = \frac{1}{N}, \quad \forall\, i \in \{1, \ldots, N\}
2

Eine spaltenstochastische Übergangsmatrix M wird aus der Adjazenzstruktur des Graphen aufgebaut. Jeder Eintrag M_ij ist gleich 1 geteilt durch den Out-Degree von Knoten j, wenn eine Kante von j nach i existiert, und andernfalls Null. Hängende Knoten (ohne ausgehende Kanten) werden typischerweise behandelt, indem ihre Punktzahl gleichmäßig auf alle Knoten verteilt wird.

Formel
M_{ij} = \begin{cases} \frac{1}{\text{out}(v_j)} & \text{if } (v_j \to v_i) \in E \\ 0 & \text{otherwise} \end{cases}
3

Der PageRank-Vektor wird iterativ mit der Random-Surfer-Formel aktualisiert. Mit dem Dämpfungsfaktor d (Standard 0,85) erhält jeder Knoten eine Basis-Teleportationswahrscheinlichkeit von (1-d)/N plus d mal die gewichtete Summe der Punktzahlen, die von allen Knoten beigetragen werden, die auf ihn verlinken. Dieser Schritt wird wiederholt, bis sich die Punktzahlen stabilisieren.

Formel
PR^{(t+1)}(v_i) = \frac{1-d}{N} + d \sum_{v_j \in \mathcal{B}(v_i)} \frac{PR^{(t)}(v_j)}{\text{out}(v_j)}
4

Nach jeder Iteration wird die L1-Norm der Änderung des Punktzahlvektors mit einer kleinen Toleranz epsilon (z. B. 1e-6) verglichen. Wenn die Änderung unter diesen Schwellenwert fällt, ist der Algorithmus konvergiert und der aktuelle Punktzahlvektor wird als endgültige PageRank-Verteilung zurückgegeben.

Formel
\left\| PR^{(t+1)} - PR^{(t)} \right\|_1 < \varepsilon

Häufige Fallstricke

  • Das Ignorieren von hängenden Knoten (Knoten ohne ausgehende Kanten) kann die stochastische Eigenschaft der Übergangsmatrix brechen und zu falschen Punktzahlen führen
  • Die Anwendung von PageRank auf ungerichtete Graphen ohne Umwandlung in ein symmetrisches Übergangsmodell kann irreführende Zentralitätsschätzungen ergeben
  • Das Festlegen einer zu lockeren Toleranz führt zu vorzeitiger Konvergenz; eine zu enge erhöht die Berechnung ohne sinnvolle Punktzahländerungen
  • Interpretation von PageRank als absolute Wichtigkeitsmetrik anstelle einer relativen Rangfolge im spezifischen Kontext eines Graphen

Häufig gestellte Fragen

Was repräsentiert der Dämpfungsfaktor d und wie sollte er gewählt werden?

Der Dämpfungsfaktor d (typischerweise 0,85) ist die Wahrscheinlichkeit, dass der zufällige Surfer einem Link folgt, anstatt zu einem zufälligen Knoten zu teleportieren. Werte nahe 1 machen den Algorithmus empfindlicher für die Graphenstruktur, aber langsamer in der Konvergenz und anfälliger für Rank Sinks; Werte nahe 0 nähern sich einem gleichmäßigen Ranking. Der Wert 0,85 wurde von Page und Brin empirisch für den Web-Graphen validiert und ist der Standard-Standardwert.

Wie unterscheidet sich PageRank von der Grad-Zentralität?

Die Grad-Zentralität zählt nur die direkte Anzahl eingehender Links zu einem Knoten und behandelt alle Quellen gleich. PageRank gewichtet jeden eingehenden Link mit der Punktzahl des verlinkenden Knotens, sodass eine Unterstützung von einem hochrangigen Knoten mehr beiträgt als von einem niedrigrangigen Knoten. Diese rekursive Definition erfasst die globale Graphenstruktur und nicht nur die lokale Konnektivität.

Kann PageRank auf ungerichtete Graphen angewendet werden?

Ja, aber mit Einschränkungen. Ein ungerichteter Graph muss in eine gerichtete Darstellung umgewandelt werden, indem jede ungerichtete Kante durch zwei gerichtete Kanten ersetzt wird. Die resultierenden PageRank-Werte entsprechen dann einer Funktion des Knotengrades, wodurch der Algorithmus auf eine gewichtete Grad-Zentralität reduziert wird. Für ungerichtete Netzwerke sind alternative Zentralitätsmaße wie Eigenvektor-Zentralität oder Betweenness-Zentralität oft aussagekräftiger.

Verwandte Methoden

Quellen

  1. Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report.

    Publikationsreferenz öffnen
    Kopiert.