2012-10-14 10 views
11

Ich verstehe die Idee hinter pagerank und habe sie implementiert (beim Lesen des Buches "Programmierung kollektiver Intelligenz").Wie wird der Pagerank verteilt berechnet?

Aber ich lese es könnte über mehrere Server verteilt werden (wie ich denke google macht). Ich bin ein wenig verwirrt, weil Sie meines Erachtens den gesamten Graphen brauchten, um einen Page Rank zu erstellen, da jedes Ranking relativ zu anderen Rankings war.

Ich fand die wiki article aber es hat nicht viel erklärt.

Irgendwelche Vorschläge, wie das möglich ist? Außerdem, Bonus-Frage: ist die Technik, verteilte pagerank exklusiv für pagerank zu tun oder kann die Methode verwendet werden, um andere maschinelle Lernalgorithmen für Graphen angewendet werden?

Antwort

8

Die hochmoderne Methode zur Berechnung von PageRank ist das Google Pregel-Framework. Ich bin mir ziemlich sicher, dass sie im Moment etwas anspruchsvoller sind, aber das ist die neueste Veröffentlichung.

Sie können mehr Details darüber in der research blog lesen. Oder lesen Sie das veröffentlichte Papier here.

Ich arbeite an einer Open-Source-Version des Bulk Synchronous Parallel Paradigma namens Apache Hama. Es gibt auch Apache Giraph, die sich ausschließlich auf die Graph-Anwendungsfälle und viele andere konzentriert.

Wie erwähnt, gibt es auch das MapReduce-Framework (Apache Hadoop zum Beispiel), das zur Berechnung von PageRank verwendet werden kann, aber für iterative Algorithmen nicht effizient ist.

Die erwähnenswerte Sache ist, dass beide Lösungen (MapReduce und BSP) Batch-Lösungen sind, so dass sie verwendet werden können, um den PageRank für den kompletten Webgraph neu zu berechnen. Da Google-Updates viel schneller sind als Batch-Algorithmen, können Sie erwarten, dass sie PageRank häufig auf Untergraphen neu berechnen.

0

MapReduce bietet einige interessante Hintergrund und könnte klären, wie Sie diese Aufgabe parallelisieren würde.

+2

Mapreduce ist übermäßig ineffizient zu berechnen PageRank –

+1

[Data-Intensive Text Processing mit MapReduce] (http://lintool.github.com/MapReduceAlgorithms/index.html) hat eine Menge MapReduce-Algorithmen einschließlich des PageRank. Wie von anderen erwähnt, ist MapReduce eine nicht effiziente Möglichkeit, den PageRank durchzuführen. Dieses [Papier] (http://arxiv.org/abs/1203.2081) vergleicht MapReduce und BSP. –