Implementierung PageRank

Moderator: Web Mining

Benutzeravatar
DerWildeKaiser
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 16. Jan 2008 12:29

Implementierung PageRank

Beitrag 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)?

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Implementierung PageRank

Beitrag 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*

Benutzeravatar
DerWildeKaiser
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 16. Jan 2008 12:29

Re: Implementierung PageRank

Beitrag 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...

Benutzeravatar
Patr0rc
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 260
Registriert: 8. Feb 2008 11:43

Re: Implementierung PageRank

Beitrag 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...

Benutzeravatar
DerWildeKaiser
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 16. Jan 2008 12:29

Re: Implementierung PageRank

Beitrag 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...

levitin
Kernelcompilierer
Kernelcompilierer
Beiträge: 435
Registriert: 7. Okt 2007 15:36
Wohnort: Darmstadt

Re: Implementierung PageRank

Beitrag 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...

Antworten

Zurück zu „Web Mining“