Seite 1 von 1

Implementierung PageRank

Verfasst: 21. Jun 2010 03:31
von DerWildeKaiser
Ich habe den PageRank nach der Formel aus der Vorlesung implementiert und mich für eine iterative Methode entschieden. Laut Informationen, die ich mir im Internet zusammengetragen habe sollten 100 Iterationen auf jeden Fall ausreichen.
Außerdem sollte mit der Verwendeten Formel am Ende die Summe über von allen PageRanks genau 1 ergeben.
Ich bekomme allerdings als Summe 0.299843263535 heraus.

Hat noch jemand dieses Problem? Mit einem einfachen Graph (3 Knoten, 5 Kanten) funktioniert das ganze Problemlos. Kann es evtl. an den "isolierten" Kanten liegen, auf die keine Links vorliegen (11, 12, 14, 15)?

Re: Implementierung PageRank

Verfasst: 21. Jun 2010 09:39
von Patr0rc
DerWildeKaiser hat geschrieben:Ich habe den PageRank nach der Formel aus der Vorlesung implementiert und mich für eine iterative Methode entschieden.
Wie hast du denn überhaupt angefangen? Wenn du allein die "Formel" aus der Vorlesung benutzt, hast du ja nicht mal einen Initialwert für den PageRank... Ich hab es wie auf Wikipedia gemacht, indem ich die PageRanks aller Knoten mit 1/N initialisiert habe.
DerWildeKaiser hat geschrieben:Laut Informationen, die ich mir im Internet zusammengetragen habe sollten 100 Iterationen auf jeden Fall ausreichen.
Außerdem sollte mit der Verwendeten Formel am Ende die Summe über von allen PageRanks genau 1 ergeben.
Ich bekomme allerdings als Summe 0.299843263535 heraus.
Das muss ich gleich mal überprüfen... ;)

Ansonsten kann dir hoffentlich jemand anderes weiterhelfen, denn ich kann es im Moment nicht... *sry*

Re: Implementierung PageRank

Verfasst: 21. Jun 2010 10:55
von DerWildeKaiser
Patr0rc hat geschrieben:
DerWildeKaiser hat geschrieben:Ich habe den PageRank nach der Formel aus der Vorlesung implementiert und mich für eine iterative Methode entschieden.
Wie hast du denn überhaupt angefangen? Wenn du allein die "Formel" aus der Vorlesung benutzt, hast du ja nicht mal einen Initialwert für den PageRank... Ich hab es wie auf Wikipedia gemacht, indem ich die PageRanks aller Knoten mit 1/N initialisiert habe.
Ich habe diese Seite durchgearbeitet, die das Thema PageRank sehr gut erfasst:
http://pr.efactory.de/d-pagerank-algorithmus.shtml

Dort wird mit einem PageRank pro Seite von '1' gestartet. Wenn ich mit einem PageRank von '1/N' starte komme ich auf genau das gleiche Ergebnis...

Re: Implementierung PageRank

Verfasst: 21. Jun 2010 11:03
von Patr0rc
Ich hab eben auch mal die Summe der PageRanks errechnen lassen und bekomme 0.28... heraus. Muss mal nachsehen, woran das liegt, bin mir aber sicher, dass der Code stimmt...

Re: Implementierung PageRank

Verfasst: 21. Jun 2010 12:11
von DerWildeKaiser
Gut, dann gehe ich mal davon aus, dass mein Code auch stimmt...
Die Werte für die Summe liegen ja doch ziemlich nahe zusammen...

Re: Implementierung PageRank

Verfasst: 24. Jun 2010 22:19
von levitin
Zitat aus dem oben erwähnten Link:

PR(A) = (1-d) / N + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

Hierbei ist N die Anzahl aller Seiten des Webs. Diese zweite Version des PageRank-Algorithmus unterscheidet sich allerdings nicht grundlegend von der ersten. In der zweiten Version beschreibt der PageRank einer Seite im Sinne des Random Surfer Modells lediglich die tatsächliche Wahrscheinlichkeit, mit der der Zufalls-Surfer nach dem Verfolgen vieler Links eine Seite erreichen wird. Dieser Algorithmus bildet damit eine Wahrscheinlichkeitsverteilung über alle Seiten des Webs ab. Die Summe aller PageRank-Werte des Webs ist damit bei dieser Version des Algorithmus gleich 1.

bei mir auch variiert die Summe je nachdem welches d ich wähle: bei d = 0.0 ist die Summe tatsächlich 1
bei d = 0.85 ist die Summe aller PR-Werte ca. 0.28
bei d = 0.95 ist die Summe aller PR-Werte ca. 0.109...