pageRank算法是Google对网页重要性的打分算法。

一个用户浏览一个网页时,有85%的可能性点击网页中的超链接,有15%的可能性转向任意的网页。pageRank算法就是模拟这种行为。

同步图计算实现pageRank算法-LMLPHP

R:定点V的pageRank

L:定点V的出度(出边的条数)

B(u):定点u的入邻居集合

d:点击超链接的概率

N:总定点个数

当N非常大时,数据的精度可能不够,所以公式进行变换,两边同时扩大N倍。

同步图计算实现pageRank算法-LMLPHP

最后公式变为

同步图计算实现pageRank算法-LMLPHP

R:定点V的pageRank*N

L:定点V的出度(出边的条数)

B(u):定点u的入邻居集合

d:点击超链接的概率

N:总定点个数

初始化:所有定点的pageRank=1;

迭代:用上述公式迭代直至收敛。

引用论文:

“Pregel: a system for large-scale graph processing.”
Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, et al.
SIGMOD 2010.

开源实现: Apache Giraph, Apache Hama

顶点算法通常步骤:

1、接收上个超步发出的消息

2、计算当前定点的值

3、向邻居发送消息

double sum = 0.0;
for (每一个入邻居) {
sum += 入邻居传递的值;
}
pagerank = 0.15 + 0.85 * sum;

终止条件是所有顶点的值都不再变化。

04-13 13:18