Zum Inhalt springen
Zurück zu den Suchergebnissen

Weighted PageRank

Eingeführt von
Xing, W. & Ghorbani, A.
Jahr
2004
Typ
Centrality measure / ranking algorithm
Familie
Network science

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

Schriftgröße

Was leistet sie?

Weighted PageRank erweitert den klassischen PageRank-Algorithmus auf Netzwerke, in denen Kanten unterschiedliche Stärken oder Frequenzen aufweisen.

Dabei wird die Wichtigkeit proportional zu den Gewichten der eingehenden und ausgehenden Kanten verteilt, anstatt alle Verbindungen gleich zu behandeln. Dies macht ihn in jedem Netzwerk, in dem die Verbindungsstärke von Bedeutung ist, wesentlich informativer als den binären PageRank.

Die Intuition hinter der Methode

Der klassische PageRank behandelt jede Hyperlink- oder Beziehungsstruktur identisch: Ein Knoten erhält von einer schwachen Verbindung genauso viel Ansehen wie von einer starken. Weighted PageRank korrigiert dies, indem er jede Stimme mit dem relativen Gewicht der Kante skaliert. Ein Knoten, der viele gewichtige eingehende Verbindungen von bereits wichtigen Knoten erhält, steigt in der Rangliste am höchsten auf, während ein Knoten mit zahlreichen, aber schwachen Verbindungen bescheiden bleibt. Dies spiegelt wider, wie Einfluss in den meisten realen Netzwerken tatsächlich akkumuliert, wo Interaktionshäufigkeit oder Transaktionsvolumen wahre Bedeutung signalisieren.

Geschichte

PageRank wurde 1998 von Brin und Page als Grundlage für die Google-Suche eingeführt, wobei alle Hyperlinks als gleichwertige Stimmen behandelt wurden. Weighted PageRank wurde 2004 von Xing und Ghorbani formalisiert und erweiterte den Algorithmus, um die Rangverteilung proportional zu den Kantengewichten zuzuweisen, basierend auf Eingewichts- und Ausgewichtungsbrüchen. Seitdem wurde er in der Zitationsanalyse, Bioinformatik, sozialen Netzwerkanalyse und Empfehlungssystemen angewendet, überall dort, wo die Link-Stärke ein aussagekräftiger Indikator für Einfluss ist.

Wann wird sie eingesetzt?

Verwenden Sie Weighted PageRank, wenn Ihr Netzwerk aussagekräftige Kantengewichte hat und Sie eine globale, flussorientierte Bedeutungseinstufung von Knoten benötigen. Es ist ideal für Zitationsnetzwerke mit gemeinsamen Zitationszahlen, Webgraphen mit Traffic-Volumen, biologische Interaktionsnetzwerke mit Expressionsniveaus, soziale Netzwerke mit Interaktionshäufigkeiten und Finanztransaktionsnetzwerke. Bevorzugen Sie Weighted PageRank gegenüber binärem PageRank immer dann, wenn das Ignorieren der Kantengewichtung den Fluss von Einfluss falsch darstellen würde. Vermeiden Sie es, wenn Kantengewichte unzuverlässig oder willkürlich zugewiesen sind, wenn das Netzwerk sehr dünn besetzt ist und Gewichte meist binär sind (einfacher PageRank genügt) oder wenn Sie ein rein lokales Zentralitätsmaß wie den gewichteten Grad benötigen. Es ist nicht geeignet für ungerichtete Netzwerke, bei denen die Flussrichtung konzeptionell bedeutungslos ist.

Grenzen und Hinweise

  • Erfordert, dass Kantengewichte aussagekräftig und zuverlässig gemessen sind; verrauschte oder willkürliche Gewichte verschlechtern die Ranking-Qualität.
  • Der Dämpfungsfaktor (d) ist ein freier Parameter; die üblichen 0,85 sind möglicherweise nicht optimal für Nicht-Web-Netzwerke.
  • Empfindlich gegenüber der gewählten Gewichtsnormierungsmethode; die Ergebnisse können unterschiedlich ausfallen, wenn Eingewichte und Ausgewichte unterschiedlich kombiniert werden.
  • Unterscheidet nicht zwischen verschiedenen Kantentypen; ein Einheitsmodell kann wichtige strukturelle Unterschiede verwischen.
  • Die Konvergenz kann bei sehr großen, dichten Netzwerken ohne effiziente Implementierungen für dünn besetzte Matrizen langsam sein.

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

Stärken

  • Berücksichtigt die Kantengewichtung direkt bei der Ausbreitung von Bedeutung und liefert realistischere Ranglisten als der binäre PageRank in gewichteten Netzwerken.
  • Erfasst die globale, netzwerkweite Prestige-Bewertung und nicht nur die lokale Konnektivität.
  • Bewahrt den Teleportationsmechanismus von PageRank, was ihn bei Korrektur gegen hängende Knoten und getrennte Komponenten robust macht.
  • Skaliert auf große Netzwerke durch effiziente iterative Berechnung; Operationen mit dünn besetzten Matrizen halten den Speicher beherrschbar.
  • Leicht interpretierbar: Ein hoher Score bedeutet, dass ein Knoten eine starke, gewichtete Bestätigung von anderen hoch bewerteten Knoten erhält.

Anwendungen

  • Identifizierung einflussreicher Arbeiten oder Autoren in gewichteten Zitations- und Ko-Autoren-Netzwerken.
  • Rangordnung von Webseiten oder Dokumenten, wenn das Verkehrsaufkommen von Hyperlinks oder Klickraten verfügbar ist.
  • Erkennung wichtiger Proteine oder Gene in gewichteten biologischen Interaktionsnetzwerken.
  • Priorisierung von Knoten in Finanztransaktionsnetzwerken nach dem Transaktionsvolumenfluss.
  • Rangordnung von Benutzern oder Inhalten in gewichteten Social-Media-Interaktionsgraphen.
  • Erstellung von Empfehlungssystemen, bei denen die Häufigkeit von Item-Kookkurenzen als Kantengewichte dient.

So funktioniert es

So funktioniert es

1

Stellen Sie das Netzwerk als Graph dar, bei dem jede Kante ein numerisches Gewicht trägt, das die Stärke der Verbindung widerspiegelt – wie z. B. Interaktionshäufigkeit, Transaktionsvolumen, Anzahl gemeinsamer Publikationen oder Ähnlichkeitswert. Der Algorithmus erfordert, dass diese Gewichte nicht-negativ sind; negative Gewichte müssen vor der Analyse transformiert werden.

2

Berechnen Sie für jede gerichtete Kante von Knoten v zu Knoten u zwei Gewichtsfaktoren: einen Eingewichtungsfaktor, der das Kantengewicht durch das gesamte eingehende Gewicht von u normalisiert, und einen Ausgewichtungsfaktor, der es durch das gesamte ausgehende Gewicht von v normalisiert. Diese Brüche bestimmen, wie viel von v's Rang über diese spezifische Kante an u verteilt wird.

Formel
W_{in}(v,u) = \frac{w(v,u)}{\sum_{k \in In(u)} w(k,u)}, \quad W_{out}(v,u) = \frac{w(v,u)}{\sum_{k \in Out(v)} w(v,k)}
3

Wenden Sie die Weighted PageRank-Formel iterativ an: Der Rang jedes Knotens entspricht einem Basis-Teleportations-Term (1 minus Dämpfungsfaktor d, typischerweise 0,85) plus d mal der Summe über alle eingehenden Nachbarn, deren Rang mit den beiden Gewichtsfaktoren skaliert wird. Dies verteilt den Rang proportional zur Kantengewichtung anstatt gleichmäßig.

Formel
WPR(u) = (1-d) + d \sum_{v \in In(u)} WPR(v) \cdot W_{in}(v,u) \cdot W_{out}(v,u)
4

Wiederholen Sie die Rangaktualisierung, bis die Änderung des Scores jedes Knotens unter eine kleine Toleranz (üblicherweise 1e-6) fällt. Die Konvergenz ist für stark verbundene Graphen garantiert; für Graphen mit hängenden Knoten oder isolierten Komponenten wenden Sie vor der Iteration die Standardkorrektur für hängende Knoten an.

5

Sobald die Scores konvergiert sind, sortieren Sie alle Knoten nach ihrem Weighted PageRank-Score in absteigender Reihenfolge. Diese Ränge spiegeln die globale strukturelle Bedeutung jedes Knotens wider, die sowohl die Netzwerktopologie als auch die Kantengewichtung berücksichtigt.

Häufige Fallstricke

  • Verwendung von rohen, unnormalisierten Kantengewichten ohne Überprüfung ihrer Skala – das Mischen von Werten im Zehner- und Millionenbereich verzerrt die Rangverteilung.
  • Vergessen, hängende Knoten (Knoten ohne ausgehende Kanten) zu behandeln, die den Rang aus dem gesamten Netzwerk abziehen können, wenn sie nicht korrigiert werden.
  • Annahme, dass der Standard-Dämpfungsfaktor von 0,85 universell geeignet ist; in Zitations- oder biologischen Netzwerken kann ein anderer Wert die Domäne besser widerspiegeln.
  • Interpretation von Weighted PageRank-Scores als absolute Wahrscheinlichkeiten anstatt als relative Ranglisten – nur ihre Reihenfolge ist über verschiedene Durchläufe stabil.
  • Vergleich von Weighted PageRank-Scores über Netzwerke unterschiedlicher Größe ohne Normalisierung.

Häufig gestellte Fragen

Wie unterscheidet sich Weighted PageRank von Standard PageRank?

Standard PageRank verteilt den Rang eines Knotens gleichmäßig an alle seine ausgehenden Nachbarn, unabhängig von der Kantengewichtung. Weighted PageRank skaliert diese Verteilung nach dem relativen Eingewicht und Ausgewicht jeder Kante, sodass stärkere Verbindungen proportional mehr Rang tragen.

Welchen Dämpfungsfaktor sollte ich verwenden?

Der übliche Wert ist 0,85, abgeleitet von Annahmen über das Surfen im Web. Für soziale, biologische oder Zitationsnetzwerke werden in der Literatur Werte zwischen 0,5 und 0,9 untersucht. Eine Sensitivitätsanalyse über einen Bereich von Dämpfungswerten wird empfohlen.

Kann Weighted PageRank auf ungerichtete Netzwerke angewendet werden?

Ja, indem jede ungerichtete Kante als ein Paar gerichteter Kanten mit demselben Gewicht dargestellt wird. Der Algorithmus erzeugt dann symmetrische Eingewichts- und Ausgewichtungsfaktoren, was zu einer Formel vereinfacht, die immer noch die Kantengewichtung berücksichtigt.

Wie gehe ich mit Kanten mit Nullgewicht um?

Kanten mit Nullgewicht tragen nichts zur Rangverteilung bei, daher können sie vor der Analyse entfernt werden. Wenn Nullgewichte strukturell bedeutsam sind (Abwesenheit versus fehlende Daten), dokumentieren Sie die Unterscheidung klar, bevor Sie sie entfernen.

Ist Weighted PageRank besser als gewichtete Gradzentralität?

Das hängt von der Forschungsfrage ab. Gewichtete Gradzentralität erfasst nur direkte Verbindungen, während Weighted PageRank den globalen Prestige-Wert erfasst, der über das gesamte Netzwerk verteilt wird. Verwenden Sie den gewichteten Grad für lokalen Einfluss und Weighted PageRank für netzwerkweite Bedeutung.

Verwandte Methoden

Quellen

  1. Xing, W., & Ghorbani, A. (2004). Weighted PageRank algorithm. Proceedings of the Second Annual Conference on Communication Networks and Services Research (CNSR '04), pp. 305–314. IEEE.

    DOI-Referenz öffnen
    Kopiert.
  2. PageRank. Wikipedia.

    Publikationsreferenz öffnen
    Kopiert.