深入浅出PageRank算法 - SegmentFault

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/11900000007111281/18

深入浅出PageRank算法

Hujiawei233天前发布

推荐0推荐

收藏6收藏，1.3k浏览

PageRank算法

PageRank算法是谷歌曾经独步天下的“倚天剑”，该算法由LarryPage和Sergey

Brin在斯坦福大学读研时发明的，论文点击下载:ThePageRankCitation

Ranking:BringingOrdertotheWeb。

本文首先通过一些参考文献引出问题，然后给出了PageRank的几种实现算法，

最后将其推广至在MapReduce框架下如何实现PageRank算法。

PageRank的核心思想有2点：

1.如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是

pagerank值会相对较高；

2.如果一个pagerank值很高的网页链接到一个其他的网页，那么被链接到的网页

的pagerank值会相应地因此而提高。

下面是一张来自WikiPedia的图，每个球代表一个网页，球的大小反应了网页的

pagerank值的大小。指向网页B和网页E的链接很多，所以B和E的pagerank值较

高，另外，虽然很少有网页指向C，但是最重要的网页B指向了C，所以C的

pagerank值比E还要大。

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/11900000007111282/18

参考内容：

1.WikiaboutPageRank

2.Google的秘密-PageRank彻底解说中文版

3.数值分析与算法Page161应用实例：Google的PageRank算法

4.NumericMethodswithMatlab或者中文翻译版本Matlab数值计算

5.使用MapReduce思想计算PageRankPage62PageRank和马尔可夫链

1.问题背景

来自参考内容3

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/11900000007111283/18

2.数学建模

来自参考内容3，理解网页连接矩阵$G$，马尔科夫过程("网上冲浪")，转移矩阵

$A$，概率$p$为用户点击当前网页中的某个链接地址的概率(一般都为0.85)。

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/11900000007111284/18

最后得到一个等式$Ax=x$，这实际上就是求矩阵$A$的特征值为1的特征向量！

下面的内容使用圆盘定理解释了1是矩阵$A$的主特征值，所以我们可以使用幂

法来求解。

关于幂法的详细介绍参考另一篇文章NumericalMethodsUsingMatlab:第三章

矩阵特征值和奇异值求解

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/11900000007111285/18

3.求解PageRank

假设有如上图右侧所示的网页链接模型。

(1)幂法

wiki上有一个PageRank的简便算法，它不考虑转移概率，而是采用的是迭代的

方式，每次都更新所有网页的pagerank值，更新的方式就是将每个网页的

pagerank值平摊分给它指向的所有网页，每个网页累计所有指向它的网页平摊

给它的值作为它该回合的pagerank值，直到全部网页的pagerank值收敛了或者

满足一定的阈值条件就停止。

后面的MapReduce框架下PageRank算法的实现就采用了这个思想。考虑转移概

率的情况和这个算法类似，乘上一个转移概率再加上一个随机跳转的概率。

根据上面的思想，下面Matlab代码实现可以得到各个网页的PageRank值。

n=6;

i=[234456161];

j=[122333456];

G=sparse(i,j,1,n,n);

%Powermethod

forj=1:n

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/11900000007111286/18

得到的向量$x$保存了各个网页的pagerank值，虽然链接数目一样，但是网页①

比网页④和网页⑤都高，而网页②的pagerank值第二高，因为网页①链接到了

它上面，相当于沾了网页①的光。

这篇文章给出该算法的一个Python版本实现，该博主使用第三方模块python-

graph，python-graph模块实现了很多图算法，该模块的使用示例，使用前需要

先安装，代码如下：

Python版本的算法实现：

L{j}=find(G(:,j));

c(j)=length(L{j});

end

p=.85;

delta=(1-p)/n;

x=ones(n,1)/n;

z=zeros(n,1);

cnt=0;

whilemax(abs(x-z))>.0001

z=x;

x=zeros(n,1);

forj=1:n

ifc(j)==0

x=x+z(j)/n;%转移到任意一个网页

else

x(L{j})=x(L{j})+z(j)/c(j);%将上次的pagerank值平摊给所

有指向的网页

end

end

x=px+delta;

cnt=cnt+1;

end

x=

0.2675

0.2524

0.1323

0.1698

0.0625

0.1156

easy_installpython-graph-core

easy_installpython-graph-dot

#coding=utf-8

#python-graphhttps://code.google.com/p/python-graph/

#Importgraphviz

importgraphvizasgv

#Importpygraph

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/11900000007111287/18

frompygraph.classes.digraphimportdigraph

frompygraph.readwrite.dotimportwrite

#Definepagerankfunction

defpagerank(graph,damping_factor=0.85,max_iterations=100,\

min_delta=0.00001):

"""

ComputeandreturnthePageRankinandirectedgraph.

@typegraph:digraph

@paramgraph:Digraph.

@typedamping_factor:number

@paramdamping_factor:PageRankdumpingfactor.

@typemax_iterations:number

@parammax_iterations:Maximumnumberofiterations.

@typemin_delta:number

@parammin_delta:Smallestvariationrequiredforanewiterati

on.

@rtype:Dict

@return:DictcontainingallthenodesPageRank.

"""

nodes=graph.nodes()

graph_size=len(nodes)

ifgraph_size==0:

return{}

#valuefornodeswithoutinboundlinks

min_value=(1.0-damping_factor)/graph_size

#itializethepagerankdictwith1/Nforallnodes

#pagerank=dict.fromkeys(nodes,1.0/graph_size)

pagerank=dict.fromkeys(nodes,1.0)

foriinrange(max_iterations):

diff=0#totaldifferencecomparedtolastiteraction

#computeseachnodePageRankbasedoninboundlinks

fornodeinnodes:

rank=min_value

forreferring_pageingraph.incidents(node):

rank+=damping_factorpagerank[referring_page]/

\

len(graph.neighbors(referring_page))

diff+=abs(pagerank[node]-rank)

pagerank[node]=rank

print''ThisisNO.%siteration''%(i+1)

printpagerank

print''''

#stopifPageRankhasconverged

ifdiff
break

returnpagerank

#Graphcreation

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/11900000007111288/18

经过32次迭代之后得到的结果如下，和前面的结果一致：

(2)利用马尔可夫矩阵的特殊结构

来自参考内容4，其中$\delta=\frac{1-p}{n}$

也就是将矩阵$A$进行分解，并不需要显示求出矩阵$A$，然后便是求解一个线

性方程组即可。

gr=digraph()

#Addnodesandedges

gr.add_nodes(["1","2","3","4"])

gr.add_edge(("1","2"))

gr.add_edge(("1","3"))

gr.add_edge(("1","4"))

gr.add_edge(("2","3"))

gr.add_edge(("2","4"))

gr.add_edge(("3","4"))

gr.add_edge(("4","2"))

#DrawasPNG

#dot=write(gr)

#gvv=gv.readstring(dot)

#gv.layout(gvv,''dot'')

#gv.render(gvv,''png'',''Model.png'')

pagerank(gr)

ThisisNO.32iteration

{''1'':0.2675338708706491,''3'':0.13227261904986046,''2'':0.25240379

02400518,''5'':0.062477242064127136,''4'':0.1697488529161491,''6'':

0.1155828978186352}

functionx=pagerank1(G)

%PAGERANK1Google''sPageRankmodifiedversion1-hujiawei

%ifnargin<3,p=.85;end

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/11900000007111289/18

(3)巧妙解法：逆迭代算法

巧妙利用Matlab中的精度误差导致原本是一个奇异矩阵的$I-A$变成一个非奇异

矩阵，运行时只是会有些警告提示，但是运行结果和其他算法一样。

p=0.85;

%Eliminateanyself-referentiallinks

G=G-diag(diag(G));

%c=out-degree,r=in-degree

[n,n]=size(G);

c=sum(G,1);%eachrow''ssum

r=sum(G,2);%eachcol''ssum

%Scalecolumnsumstobe1(or0wheretherearenooutlinks).

k=find(c~=0);

D=sparse(k,k,1./c(k),n,n);

%Solve(I-pGD)x=e

e=ones(n,1);

I=speye(n,n);

x=(I-pGD)\e;

%Normalizesothatsum(x)==1.

x=x/sum(x);

functionx=pagerank2(G)

%PAGERANK1Google''sPageRankmodifiedversion2-hujiawei

%usinginverseiterationmethod

%ifnargin<3,p=.85;end

p=0.85;

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/119000000071112810/18

最后，附上参考内容4中给出的一份好代码，用于模拟随机冲浪生成矩阵$G$的

代码

%Eliminateanyself-referentiallinks

G=G-diag(diag(G));

%c=out-degree,r=in-degree

[n,n]=size(G);

c=sum(G,1);%eachrow''ssum

r=sum(G,2);%eachcol''ssum

%Scalecolumnsumstobe1(or0wheretherearenooutlinks).

k=find(c~=0);

D=sparse(k,k,1./c(k),n,n);

%Solve(I-pGD)x=e

e=ones(n,1);

I=speye(n,n);

%x=(I-pGD)\e;

delta=(1-p)/n;

A=pGD+delta;

x=(I-A)\e;

%Normalizesothatsum(x)==1.

x=x/sum(x);

function[U,G]=surfer(root,n)

%SURFERCreatetheadjacencygraphofaportionoftheWeb.

%[U,G]=surfer(root,n)startsattheURLrootandfollows

%Weblinksuntilitformsanadjacencygraphwithnnodes.

%U=acellarrayofnstrings,theURLsofthenodes.

%G=ann-by-nsparsematrixwithG(i,j)=1ifnodejislinked

tonodei.

%

%Example:[U,G]=surfer(''http://www.harvard.edu'',500);

%SeealsoPAGERANK.

%

%Thisfunctioncurrentlyhastwodefects.(1)Thealgorithmfo

r

%findinglinksisnaive.Wejustlookforthestring''http:''.

%(2)AnattempttoreadfromaURLthatisaccessible,butvery

slow,

%mighttakeanunacceptablylongtimetocomplete.Insomecas

es,

%itmaybenecessarytohavetheoperatingsystemterminateMAT

LAB.

%KeywordsfromsuchURLscanbeaddedtotheskiplistinsurf

er.m.

%Initialize

clf

shg

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/119000000071112811/18

set(gcf,''doublebuffer'',''on'')

axis([0n0n])

axissquare

axisij

boxon

set(gca,''position'',[.12.20.78.78])

uicontrol(''style'',''frame'',''units'',''normal'',''position'',[.01.09.98

.07]);

uicontrol(''style'',''frame'',''units'',''normal'',''position'',[.01.01.98

.07]);

t1=uicontrol(''style'',''text'',''units'',''normal'',''position'',[.02.10

.94.04],...

''horiz'',''left'');

t2=uicontrol(''style'',''text'',''units'',''normal'',''position'',[.02.02

.94.04],...

''horiz'',''left'');

slow=uicontrol(''style'',''toggle'',''units'',''normal'',...

''position'',[.01.24.07.05],''string'',''slow'',''value'',0);

quit=uicontrol(''style'',''toggle'',''units'',''normal'',...

''position'',[.01.17.07.05],''string'',''quit'',''value'',0);

U=cell(n,1);

hash=zeros(n,1);

G=logical(sparse(n,n));

m=1;

U{m}=root;

hash(m)=hashfun(root);

j=1;

whilej
%Trytoopenapage.

try

set(t1,''string'',sprintf(''%5d%s'',j,U{j}))

set(t2,''string'','''');

drawnow

page=urlread(U{j});

catch

set(t1,''string'',sprintf(''fail:%5d%s'',j,U{j}))

drawnow

continue

end

ifget(slow,''value'')

pause(.25)

end

%Followthelinksfromtheopenpage.

forf=findstr(''http:'',page);

%Alinkstartswith''http:''andendswiththenextquote.

e=min([findstr(''"'',page(f:end))findstr('''''''',page(f:end))])

;

ifisempty(e),continue,end

url=deblank(page(f:f+e-2));

url(url<'''')=''!'';%Nonprintablecharacters

ifurl(end)==''/'',url(end)=[];end

%Lookforlinksthatshouldbeskipped.

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/119000000071112812/18

skips={''.gif'',''.jpg'',''.pdf'',''.css'',''lmscadsi'',''cybernet'',.

..

''search.cgi'',''.ram'',''www.w3.org'',...

''scripts'',''netscape'',''shockwave'',''webex'',''fansonly''}

;

skip=any(url==''!'')|any(url==''?'');

k=0;

while~skip&(k
k=k+1;

skip=~isempty(findstr(url,skips{k}));

end

ifskip

ifisempty(findstr(url,''.gif''))&isempty(findstr(url,''.jp

g''))

set(t2,''string'',sprintf(''skip:%s'',url))

drawnow

ifget(slow,''value'')

pause(.25)

end

end

continue

end

%Checkifpageisalreadyinurllist.

i=0;

fork=find(hash(1:m)==hashfun(url))'';

ifisequal(U{k},url)

i=k;

break

end

end

%Addanewurltothegraphthereifarefewerthann.

if(i==0)&(m
m=m+1;

U{m}=url;

hash(m)=hashfun(url);

i=m;

end

%Addanewlink.

ifi>0

G(i,j)=1;

set(t2,''string'',sprintf(''%5d%s'',i,url))

line(j,i,''marker'',''.'',''markersize'',6)

drawnow

ifget(slow,''value'')

pause(.25)

end

end

end

j=j+1;

end

delete(t1)

delete(t2)

delete(slow)

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/119000000071112813/18

4.MapReduce框架下PageRank算法的实现

利用前面wiki上的迭代(或者幂法)的思想来实现MapReduce框架下PageRank算

法很简单，可以先阅读下参考内容5。

这篇文章using-mapreduce-to-compute-pagerank更加详细，可以参考

以下是我的大数据的一次作业，要求是参考wiki上的简便算法，实现MapReduce

框架下的PageRank算法。给的数据集是Twitter的用户之间的关系，可以看做是

网页之间的关系，但是助教没要求写代码以及运行这个数据集(有1G多)，所以下

面只是一个Python版本的理想可行版本，并没有通过实际大数据集的验证，另

外，博主暂时还不太会Python的mapreduce框架中的一些函数，所以实现的是一

个简明的可以测试的PageRank算法。

1.输入输出格式

map函数的输入是<节点，从该节点引出的边列表>，其中节点是一个类，

包含了其当前的pagerank值，输出是<节点，反向节点pagerank值/反向节

点引出边的总数>；

reduce函数的输入是<节点，反向节点pagerank值/反向节点引出边的总数

>，输出是<节点，从该节点引出的边列表>，其中节点包含了其更新后的

pagerank值。

伪代码：[一时犯二写了个英文形式的]

set(quit,''string'',''close'',''callback'',''close(gcf)'',''value'',0)

%------------------------

functionh=hashfun(url)

%Almostuniquenumerichashcodeforpagesalreadyvisited.

h=length(url)+1024sum(url);

processthedatatotheformof{nodei:[itsadjacentnodelist],..

.}

whilethesumofdifferencebetweenthelasttwopagerankvalues<

threshold

map({nodei:[itsadjacentnodelist],...}):

map_output={}

foreverynodejinadjacentnodelist:

putorsumup{j:(i,PageRank(i)/length(adjacentnodel

ist))}intomap_output

returnmap_output

reduce(map_output):

reduce_output={}

foreveryentry{j:(i,PageRank(i)/length(adjacentnodelis

t))}inmap_output:

putorsumupallvaluespagerankvaluesfornodejwit

hitsadjacentnodelistintoreduce_output

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/119000000071112814/18

2.示例演示

假设用户1，2，3，4是如下图所示的关系：

假设有2个mapper(A和B)和1个reducer(C)，初始时4个节点的pagerank值都是

0.25

其中，关于用户1和2的数据被mapperA读取并处理，关于用户3和4的数据被

mapperB读取并处理[经验证，即使一个用户的数据是由不同的mapper来读取

的，最终收敛到的结果差不多]

map的输入输出结果如下：

returnreduce_output

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/119000000071112815/18

reduce的输入输出结果如下，输入是2个mapper的输出，输出的结果中更新了节

点的pagerank值

reducer处理完了之后又将它的结果输入给mapper处理，直到迭代的次数超过了

设定值或者两次迭代之后得到的所有节点的pagerank值之差的总和(也可以是取

二范数)小于设定的阈值。

3.示例的实验结果

(1)首先是使用Matlab采用幂法的方式计算出在p=1.0的情况下示例得到的结果

[它的主要作用是验证后面python版本的正确性]

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/119000000071112816/18

matlab源码如下：

结果为：

(2)matlab版本的pagerank没有采用mapreduce的思想进行迭代，所以我另外写

了一个python版本的利用mapreduce思想实现的pagerank算法(注：我并没有使

用python的map和reduce函数去实现，而是使用更加容易明白的实现)，使用的

阈值为0.0001，最多迭代的次数为100次。

n=4;

i=[23434412];

j=[11122334];

G=sparse(i,j,1,n,n);

[n,n]=size(G);

forj=1:n

L{j}=find(G(:,j));

c(j)=length(L{j});

end

%Powermethod

p=1.0;

delta=(1-p)/n;

x=ones(n,1)/n;

z=zeros(n,1);

cnt=0;

whilemax(abs(x-z))>.0001

z=x;

x=zeros(n,1);

forj=1:n

ifc(j)==0

x=x+z(j)/n;

else

x(L{j})=x(L{j})+z(j)/c(j);

end

end

x=px+delta;

cnt=cnt+1;

end

sprintf(''pagerankresult:'')

x

0.1072

0.3571

0.2143

0.3214

#coding=utf-8

__author__=''hujiawei''

__doc__=''pagerankmapreduce''

classNode:

def__init__(self,id,pk):

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/119000000071112817/18

self.id=id

self.pk=pk

defpk_map(map_input):

map_output={}

fornode,outlinksinmap_input.items():

forlinkinoutlinks:

size=len(outlinks)

iflinkinmap_output:

map_output[link]+=(float)(node.pk)/size

else:

map_output[link]=(float)(node.pk)/size

returnmap_output

defpk_reduce(reduce_input):

forresultinreduce_input:

fornode,valueinresult.items():

node.pk+=value

defpk_clear(nodes):

fornodeinnodes:

node.pk=0

defpk_last(nodes):

lastnodes=[]

fornodeinnodes:

lastnodes.append(Node(node.id,node.pk))

returnlastnodes

defpk_diff(nodes,lastnodes):

diff=0

foriinrange(len(nodes)):

print(''nodepk%f,lastnodepk%f''%(nodes[i].pk,lastno

des[i].pk))

diff+=abs(nodes[i].pk-lastnodes[i].pk)

returndiff

defpk_test1():

node1=Node(1,0.25)

node2=Node(2,0.25)

node3=Node(3,0.25)

node4=Node(4,0.25)

nodes=[node1,node2,node3,node4]

threshold=0.0001

max_iters=100

foriter_countinrange(max_iters):

iter_count+=1

lastnodes=pk_last(nodes)

print(''============mapcount%d=================''%(iter

_count))

in1={node1:[node2,node3,node4],node2:[node3,node4]}

in2={node3:[node1,node4],node4:[node2]}

mapout1=pk_map(in1)

mapout2=pk_map(in2)

fornode,valueinmapout1.items():

printstr(node.id)+''''+str(value)

fornode,valueinmapout2.items():

2014年10月11日深入浅出PageRank算法-SegmentFault

http://segmentfault.com/blog/hujiaweibujidao/119000000071112818/18

androidopencv

得到的结果为如下，总共迭代了15次

上面的结果和Matlab用幂法得到的pagerank值差别很小，可以认为是正确的，

所以说明了使用这种mapreduce输入输出格式的正确性。

OK，差不多了，希望对需要理解PageRank算法的人有帮助！:-)

printstr(node.id)+''''+str(value)

print(''============reducecount%d=================''%(i

ter_count))

reducein=[mapout1,mapout2]

pk_clear(nodes)

pk_reduce(reducein)

fornodeinnodes:

printstr(node.id)+''''+str(node.pk)

diff=pk_diff(nodes,lastnodes)

ifdiff
break

if__name__==''__main__'':

pk_test1()

10.107138774577

20.35712924859

30.214296601128

40.321435375705