Как PageRank рассчитывается распределенным образом?

Question

Я понимаю идею, лежащую в основе PageRank, и реализовал ее (когда читал книгу "Программирование коллективного интеллекта").

Но я читал, что это может быть распределено по нескольким серверам (как я думаю, Google делает). Я немного сбит с толку, потому что, согласно моему пониманию, вам нужен весь график, чтобы сделать рейтинг страниц на нем, так как каждый рейтинг был относительно рейтинга других.

Я нашел статью в вики, но она мало что объясняла.

Любые предложения о том, как это возможно? Кроме того, бонусный вопрос: является ли метод, чтобы сделать распределенный PageRank исключительно для PageRank, или можно ли использовать этот метод для других алгоритмов машинного обучения, применяемых к графам?

Answer 1

Ультрасовременный способ расчета PageRank осуществляется с помощью каркаса Google Pregel. Я почти уверен, что у них есть что-то более сложное прямо сейчас, но это последнее опубликованное усилие.

Вы можете прочитать более подробную информацию об этом в блоге исследований. Или прочитайте опубликованную статью здесь.

Я работаю над открытой версией парадигмы Bulk Synchronous Parallel под названием Apache Hama. Существует также Apache Giraph, который фокусируется исключительно на сценариях использования графов и многих других.

Как упоминалось в mfrankli, существует также инфраструктура MapReduce (например, Apache Hadoop), которую можно использовать для вычисления PageRank, но она неэффективна для итерационных алгоритмов.

Следует отметить, что оба решения (MapReduce и BSP) являются пакетными, поэтому их можно использовать для пересчета PageRank для всего веб-графика. Поскольку обновления Google намного быстрее, чем пакетные алгоритмы, вы можете ожидать, что они часто пересчитывают PageRank для подграфов.

Answer 2

Позволять

| 0 0 0 1 0 |
| 0 0 0 1 0 |
| 0 0 0 1 1 |
| 1 1 1 0 0 |
| 0 0 1 0 0 |

матрица смежности (или граф). Тогда матрица переходаM в PageRank будет

| 0 0   0 1/3 0 |
| 0 0   0 1/3 0 |
| 0 0   0 1/3 1 |
| 1 1 1/2   0 0 |
| 0 0 1/2   0 0 |

который является столбцовым стохастическим, неприводимым и апериодическим.

MapReduce начинается отсюда. Сериализованный ввод для картографов будет похож на

1 -> 4
2 -> 4
3 -> 4 , 5
4 -> 1 , 2 , 3
5 -> 3

и картографы выдадут следующее:

< 1 , [4] >
< 4 , 1 >

< 2 , [4] >
< 4 , 1 >

< 3 , [4 , 5] >
< 4 , 1/2 >
< 5 , 1/2 >

< 4 , [1, 2, 3] >
< 1 , 1/3 >
< 2 , 1/3 >
< 3 , 1/3 >

< 5 , [3] >
< 3 , 1 >

Выводы Mapper будут сгруппированы по ключам и приняты редукторами. Если у нас будет 5 редукторов, это будет примерно так:

R1 takes [4]       , 1/3           then computes 1/5*(1/3)           =  2/30
R2 takes [4]       , 1/3           then computes 1/5*(1/3)           =  2/30
R3 takes [4, 5]    , 1/3 , 1       then computes 1/5*(1/3 + 1)       =  8/30
R4 takes [1, 2, 3] ,   1 , 1 , 1/2 then computes 1/5*(  1 + 1 + 1/2) = 15/30
R5 takes [3]       , 1/2           then computes 1/5*(1/2)           =  3/30

На этом первая (силовая) итерация окончена. Во время следующих заданий сокращения редюсеры будут излучать так же, как и преобразователи, однако вычисленное PR будет использоваться вместо 1:

< 1 , [4] >
< 4 , 2/30 >

< 2 , [4] >
< 4 , 2/30 >

< 3 , [4 , 5] >
< 4 , 4/30 >
< 5 , 4/30 >

< 4 , [1, 2, 3] >
< 1 , 5/30 >
< 2 , 5/30 >
< 3 , 5/30 >

< 5 , [3] >
< 3 , 3/30 >

Повторяйте сокращение заданий до тех пор, пока оно не сходится достаточно или вы не будете удовлетворены.

Answer 3

MapReduce предоставляет некоторые интересные сведения и может прояснить, как вы распараллелите эту задачу.