Page Rank Algorithmus implementieren

[Prinz]

Also der Algorithmus ist folgender:

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

Hierbei ist:
PR(A) der PageRank einer Seite A,
PR(Ti) der PageRank der Seiten Ti, von denen ein Link auf die Seite A zeigt,
C(Ti) die Gesamtanzahl der Links auf Seite Ti und
d ein Dämpfungsfaktor (Damping Factor), wobei 0 <= d <= 1 ist.


für alle A Element Seiten


Ich hab Datebanktabelle mit den 2 Atributen

- Knoten (Wäre dan A)

- Referenz von anderem Knoten (Wäre Ti)



Habt ihr Vorschläge welche Datenstrukturen da am geeignetsten wären.
Ich will das Programm möglichst effizient. Sind da HashMaps geeignet?

 

[SlaterB]

das hängt ja stark davon ab, was du mit den Daten tun willst
wie oft speichern/ laden,
nur komplette Durchläufe oder Springen/ Suchen/ ..

falls du Knoten-Ids kennst und dazu den Knoten haben willst,
dann sind Maps gut, ja,
außerdem die Knoten-Objekte untereinander verknüpfen,
das klingt recht praktisch

 

[Prinz]

Der Algorithmus konvergiert sehr schnell. Ich denke 10 Durchläufe sind genug.
Maximal 30


Insgesamt habe ich ca. 30.000 Knoten. Könnten aber auch 10mal soviel werden.
Die Knoten Id's kenne ich natürlich.


Also untereinander verknüpfen? Bin mir nicht sicher ob der Stack das mitmacht, da ich ja dann alle Objekte reinladen muss.

Andererseits ist es wahrscheinlich auch recht langsam jedes Objekt aus der Datenbank zu holen.

 

[SlaterB]

wenns an die Grenzen geht, dann Komfort über Board werden und speicherfreundlich arbeiten,

spontage Idee: einige int-Arrays:

ein Array enthält pro Knoten hintereinander weg die Index2 der verbundenen Knoten + Trennzeichen,
wird sehr lang und unterschiedlich lang pro Knoten

Index2 bezieht sich auf die Position im zweiten Array


ein zweites Array mit 2 Feldern pro Knoten:
die erste enthält den Index1 des Knotens im ersten Array,
die zweite den bisherigen Page-Rank


nun kann man das zweite Array durchlaufen,
zu jedem Knoten im ersten Array die zugehörigen Knoten im zweiten Array suchen und deren Page-Ranks lesen

----

dazu noch Zusatz-Infos wie Name pro Knoten in anderen Arrays oder in der DB

wenn die Arrays zu lang sind, dann mehrere Arrays und in den Positionen sowohl den Index als auch die Array-Nummer kodieren,

-------

ist dann nicht mehr wirklich objektorientiert

-------

sobald es wirklich mehr Daten werden als gleichzeitig verarbeitet werden können,
dann muss zwangsläufig nachgeladen werden,
dann gibt es hoffentlich sowas wie Lokalität,
bei komplett zufälliger Vermaschung wirds bizar

 

[Prinz]

mit arrays wollte ich sowieso nicht arbeiten.

Würde dann eher eine Liste verwenden. Arrays taugen mir garnicht

 

[Gast]

hey, gibt es inzwischen ein java programm / eine klasse die den pagerank für eine übergebene url berechnet?

 

[Tobias]

Da der Google-Pagerank-Algorithmus Firmengeheimnis ist - nein.

mpG
Tobias

 

[tincup]

Hi.

Also nur mal aus eigener Erfahrung: Wir haben diese Pagerank-Idee mal für Proteinhomologien implementiert. Nannte sich da Rankprop. Das Problem sind eben die vielen Verknüpfungen, die du halten musst. Eine direkte 2D-Matrix (= Array) wäre das allerschnellste. Die fällt aber natürlich flach, weil sie viel zu groß werden würde, nämlich Objekte*Objekte Zellen.

Die Verbindungsmatrix ist aber sehr "sparse", also dünn besiedelt. Das heisst jedes Objekt hat in der Regel nur Verknüpfungen mit wenigen Partner im Vergleich zur Gesamtmenge. Haben dann tatsächlich eine Implementation mit Arrays hergenommen in etwa wie sie unten beschrieben war.

Weiss es grad nicht mehr ganz exakt (müsste nachgucken), aber es war schon pro Knoten zwei Arrays, jeweils mit der PartnerID und dem Pagerank. Diese beiden listen dann noch nach PartnerID sortiert für schnelle binäre Suche.

Mein genereller Tip auch aus der konkreten Erfahrung: Wenn es wirklich viele Daten werden wird das ganze verdammt groß. Dann solltest oder musst du leider auf entsprechende "schöne" Java Klassen wie List<E>, HashMap<K,V> etc. verzichten. Diese Datenstrukturen und vor allem die zugrundeliegenden Objekte (Integer statt int, Float statt float etc.) rauben dir dein letztes Byte :wink: