page rank mit "Random Walk" Methode ermitteln

Nathalie

Hallo,

kann mir jemand etwas über die Random Walk Methode erzählen, wie man damit den Pagerank ermittelt und wie genau das funktioniert?

Das einzige was ich dazu weiß ist, dass dabei eine zufällige Seite ausgewählt wird, man n- Links folgt und notiert wie oft jede Seite besucht wurde..

Aber das reicht wohl kaum aus als Erklärung?!

Kann mir das jemand näher erläutern mit der Random Walk Methode?

Gruß
Nathalie

Da die Pagerankanzeige "veraltet" ist und von Google nicht mehr gepflegt wird wirst Du mit keiner Methode vernünftige Ergebnisse erzielen.
Was willst Du denn erreichen?

Nathalie hat geschrieben:Hallo,

kann mir jemand etwas über die Random Walk Methode erzählen, wie man damit den Pagerank ermittelt und wie genau das funktioniert?

Das einzige was ich dazu weiß ist, dass dabei eine zufällige Seite ausgewählt wird, man n- Links folgt und notiert wie oft jede Seite besucht wurde..

Aber das reicht wohl kaum aus als Erklärung?!

Kann mir das jemand näher erläutern mit der Random Walk Methode?

Gruß
Nathalie

hanneswobus

diese methode hat nichts mit dem pr zu tun. du meinst doch: https://de.wikipedia.org/wiki/Random_Walk, oder?

chris21

Das könnte als zitierwürdiger Ansatz helfen:

https://wwwhome.math.utwente.nl/~litvakn/mc.pdf

(Vorausgesetzt, Dir geht es nicht um den eigentlichen Pagerank Algorithmus, sondern um eine Pagerank Annährung über Random Walk durch einen Monte Carlo Algorithmus)

Nathalie

mwitte hat geschrieben:Da die Pagerankanzeige "veraltet" ist und von Google nicht mehr gepflegt wird wirst Du mit keiner Methode vernünftige Ergebnisse erzielen.
Was willst Du denn erreichen?

Nathalie hat geschrieben:Hallo,

kann mir jemand etwas über die Random Walk Methode erzählen, wie man damit den Pagerank ermittelt und wie genau das funktioniert?

Das einzige was ich dazu weiß ist, dass dabei eine zufällige Seite ausgewählt wird, man n- Links folgt und notiert wie oft jede Seite besucht wurde..

Aber das reicht wohl kaum aus als Erklärung?!

Kann mir das jemand näher erläutern mit der Random Walk Methode?

Gruß
Nathalie

Ich möchte damit auch gar keine Ergebnisse erzielen oder diese Methode anwenden...das ist aber eine eventuelle Klausurfrage und da sollte ich dann einfach diese Random Walk Methode erklären können...

Übrigens, danke für eure bisherigen Antworten!

Nathalie

Hannes, wie meinst du das, dass diese Methode nichts mit dem Pagerank zu tun hat?

Die Klausurfrage (von einer alten Klausur muss ich hinzufügen) lautet wortwörtlich:

"Wie kann der Pagerank mit der "Random Walk" Methode ermittelt werden" ?

Es handelt sich hierbei übrigens um das Fach Online Marketing

hanneswobus

nathalie,
kennst du konkrete anwendungsbeispiele von der "random walk" - methode? hast du hierzu konkrete dinge programmieren duerfen?
gruß

chris21

@hannes: habe oben ein Beispiel verlinkt.

Kurz zum Verständnis: der originale Pagerank Algorithmus hat ein nicht zu unterschätzende Komplexität - d.h.: stark steigender Anstieg des Aufwandes bei vielen Domains/Seiten im Untersuchungsset.

Daher gibt es Versuche, durch einfachere Algorithmen die Komplexität (d.h. den Berechnungsaufwand) zu senken und dabei Annährungswerte zu dem tatsächlich errechenbaren Pagerank Wert zu erhalten. Hier können Random Walk Algorithmen helfen.

@Nathalie:

Steht in der Frage Random Walk oder Random Surfer?

Für den originalen Pagerank wird ein Random Surfer Modell verwendet, daher ist jetzt nicht ganz klar, ob ihr den Pagerank selbst erläutern sollt oder Methoden, wie eine Pagerank Annährung errechnet werden kann (über einen Random Walk Algorithmus).

Bei "Online Marketing" habe ich ja eher das Gefühl, dass ihr weniger auf die technischen Seiten einsteigen werdet (Information Retrieval in der Informatik). D.h.: je nach Hintergrund des Dozenten, der die Klausur formuliert hat, will er vll. einfach nur eine einfache Pagerank Beschreibung von Euch?

Falls es tatsächlich darum geht, wie über einen Random Walk Algo eine Pagerank-Berechnungs-Annährung erreicht werden kann, würde auch dieses Beispiel helfen: https://www2003.org/cdrom/papers/refere ... eboul.html

Nathalie

In der Frage steht Random Walk..

Ich habe doch die exakte Fragestellung hier schon reingeschrieben.

Also, es handelt sich um die Klausur des Fachs online marketing, ein Wahlfach des Studiengangs Wirtschaftsinformatik ...die ich leider nachshreiben muss.

Auf technische Sachen, sind wir da nicht so sehr eingegangen. ein paar Sachen haben wir schon ausgerechnet, also auch zu anderen Themen.

Ich habe hier mal noch 2 Bilder. Sieht ein wenig Chaotisch aus, aber das war damals das einzige, was wir zu page rank und random walk aufgeschrieben hatten.

Und die frage lautete:

"Wie kann man den Pagerank mit der "Random Walk" Methode ermitteln?

Ich habe mal noch die Fotos hochgeladen. Mehr hatten wir zu dem Thema Google Page Rank eigentlich auch nicht gemacht.

Es kann ja irgendwie nicht sein, dass dieser kleiner Text über Random Walk, der auf dem ersten Blatt steht ausreicht um diese Frage zu beantworten oder?

hanneswobus

beim ersten bild verstehe ich nicht "notieren wie oft eine seite besucht wurde". wie das technisch funktioniert ist natuerlich klar, aber ich verstehe nicht den zusammenhang mit der metrik "pagerank". @nathalie. ist das ganze als "ueberwachungsprozedur" zu begreifen, also als eine art periodisch wiederkehrende existenzpruefung von linkxyz?

chris21 · Zuletzt geändert von chris21 am 25.01.2015, 18:55, insgesamt 2-mal geändert.

"notieren wie oft eine seite besucht wurde"

das wäre genau ein Teilstück aus der Random Walk Methode aus meinem ersten Link ( https://wwwhome.math.utwente.nl/~litvakn/mc.pdf )

Damit scheint es Eurem Prof darum zu gehen.

Dann kann ich die vll. mal in einfachen Worten erläutern:

Du hast ein Set aus URLs (Domains und deren Unterseiten) n.

Du startest jetzt zufälliges "Gehen" durch dieses Set nach folgenden Regeln:

a) Bei einer beliebigen Seite starten (Warscheinlichkeit für diese Seite: 1/n ).

Auf dieser Seite gibt es m Links.

b) Einem dieser Links folgen (Warscheinlichkeit 1/m) (Wenn die Seite keine ausgehenden Links hat wieder bei a) starten)

Variante zu b): entweder einem diesem Links folgen oder "Teleportieren" - Warscheinlichkeit dann z.B. 1/m+1. Teleportieren bedeutet: Random Walk hier abbrechen und woanders wieder neu starten (also neu bei a) beginnen - vergleichbar ist dies mit dem sog. Dämpfungsfaktor im Pagerank-Algorithmus)

c) Für jede Seite merken, wie oft sie von einem Random Walker besucht wurde (vgl. Deine Notizen).

Dieser Wert kann da bei entsprechend vielen Durchläufen Aufschluss auf den Pagerank geben, d.h. Seiten mit hohem Pagerank haben dann einen hohen Wert an Besuchern des Random Walkers, so dass die durch die Random Walks entstehende Skala entsprechend an die Pagerank Skala von 0-10 umgerechnet werden kann. Hierbei wird dann der BesucheWert durch die Anzahl durchgeführter Random Walks geteilt und man erreicht bei entsprechend vielen Durchläufen eine schöne Annährung zum Pagerank mit weniger Aufwand.

Berechnungs-Vorteil ggü Pagerank: Es können massiv viele Random Walks parallel gestartet werden.

@Hannes: es geht hier allgemein darum, dass der Pagerank Algorithmus zwar bekannt ist, es aber sehr aufwändig ist, ihn für ein großes Set an Daten (=URLs) zu berechnen (weil der Pagerank ja rekursiv für jede Seite den Pagerank der linkgebenden Seite(n) kennen muss).

Der eingesetzte Random Walk Algorithmus zur Annährung an einen PageRank ist weniger aufwändig, daher leichter zu berechnen, bringt aber im allgemeinen gute, ähnliche Werte wie der PageRank zustande. Vorteil also=weniger Berechnungsaufwand bei fast gleich guter Wertigkeit der errechneten Daten ggü. dem original Pagerank Algo.

hanneswobus

chris,
ah - verstanden u. hab dank fuer die inspiration.
gruß