CWYAlpha

Just another WordPress.com site

Thought this was cool: PageRank的Mapreduce实现

leave a comment »


pagerank算大的天然特性使得他很容易用Mapreduce实现。

pr_i=a*sum(pr_j/C_j)+(1-a)/N

一般的话两层mapreduce就好了,第一层是准备数据阶段;第二层就是迭代计算每个节点的PR值了。

重点说下第二层的mapper和reducer:

mapper:

输入:vi,pr_i(初值化,可以用0.5等),<v_j1, v_j2,v _jk…>(v_jk是vi的所有目标节点,也就是vi->v_jk)

输出:v_j1,vi,pr_i/n (这里的n就是vi节点的出度啊,可以数数上面几个v_jk)

v_j2,vi,pr_i/n

v_jk,vi,pr_i/n

………

还要输出: vi, -1, 0, <v_j1, v_j2,v _jk…>

特别重要一点,这里要继续把上面的vi指向的所有节点输入一遍,为了后面迭代重新构建输入;好多地方这里描述不严谨。为了你后面处理的方便,可以将部分field填成容易判断的字符,你可以发现这一条数据。我就将第二,第三个字段分别填上-1,0,到时候判别field2==“-1”,那么vi指向的所有目标节点就是field4.

reducer就很简单了,接收到每个节点的输入节点,根据公式计算就可以了。

Output:vi, new_pr, <v_j1, v_j2,v _jk…>

然后就可以继续迭代了,直到收敛或达到迭代次数。

==

需要思考一会儿的就是mapper中飘红的那些,怎么保留住一个节点的所有目标节点。

您可能也喜欢:


单源最短路径BFS的Mapreduce实现


MapReduce与自然语言处理


Hadoop Streaming的使用


搜索引擎的星星之火


回顾一下SIGIR’08文章之微软的BrowseRank

无觅

相关文章

from 丕子: http://www.zhizhihu.com/html/y2012/4041.html

Written by cwyalpha

十月 28, 2012 在 12:53 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: