python实现PageRank计算

1、#coding=utf-8# Filename:pr.pyS=0,0,0,0,0.3333,0,0,1,0.3333,0.5,0,0,0.3333,0.5,1,0 #原始矩阵U=1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 #全部都为1的矩阵f=1,1,1,1 #物征向量alpha=0.85 # a 值 0-1之间的小数n=len(S) #网页数'''aS a权重值 由google决定值大小，0-1之间，S为原始矩阵 '''def multiGeneMatrix(gene,Matrix): mullist=0*len(Matri

2、x) for row in range(len(Matrix) #定义新的矩阵大小，初始化为0 for i in range(0,len(Matrix): for j in range(0,len(Matrix): mullistij += Matrixij*gene return mullist '''两个矩阵相加'''def addMatrix(Matrix1,Matrix2): if len(Matrix10)!=len(Matrix2): print "这两个矩阵无法相加." return addlist=0*len(

3、Matrix1) for row in range(len(Matrix1) #定义新的矩阵大小 for i in range(0,len(Matrix1): for j in range(0,len(Matrix2): addlistij=Matrix1ij+Matrix2ij return addlist'''矩阵与向量相乘'''def multiMatrixVector(m,v): rv=range(len(v) for row in range(0,len(m): temp=0 for col in range(0,len(m1): te

4、mp+=mrowcol*vcol rvrow=temp return rv #公式f1=multiGeneMatrix(alpha,S)f2=multiGeneMatrix(1-alpha)/len(S0),U)G=addMatrix(f1,f2)print G #google矩阵#迭代过程count=0while(True): count=count +1 pr_next=multiMatrixVector(G,f) print "第 %s 轮迭代" % count print str(round(pr_next0,5) +"t" + str(roun

5、d(pr_next1,5) + "t" + str(round(pr_next2,5) + "t" + str(round(pr_next3,5) if round(f0,5)=round(pr_next0,5) and round(f1,5)=round(pr_next1,5) and round(f2,5)=round(pr_next2,5) and round(f3,5)=round(pr_next3,5): #当前向量与上次向量值偏差不大后，停止迭 break f=pr_nextprint "Page Rank值已计算完成"运

6、行结果：第 1 轮迭代0.15 1.2833 0.8583 1.70831第 2 轮迭代0.15 1.64455 0.7379 1.46746第 3 轮迭代0.15 1.43983 0.89143 1.51864第 4 轮迭代0.15 1.48333 0.80442 1.56213第 5 轮迭代0.15 1.5203 0.82291 1.50666第 6 轮迭代0.14999 1.47315 0.83862 1.53809第 7 轮迭代0.14999 1.49986 0.81858 1.5314第 8 轮迭代0.14999 1.49418 0.82993 1.52572第 9 轮迭代0.149

7、99 1.48935 0.82751 1.53295第 10 轮迭代0.14999 1.4955 0.82546 1.52885第 11 轮迭代0.14999 1.49201 0.82807 1.52971第 12 轮迭代0.14999 1.49274 0.82659 1.53045第 13 轮迭代0.14999 1.49337 0.8269 1.5295第 14 轮迭代0.14999 1.49256 0.82717 1.53003第 15 轮迭代0.14999 1.49301 0.82682 1.52991第 16 轮迭代0.14999 1.49291 0.82701 1.52981第 17

8、 轮迭代0.14999 1.49282 0.82697 1.52993第 18 轮迭代0.14999 1.49292 0.82693 1.52986第 19 轮迭代0.14999 1.49286 0.82697 1.52987第 20 轮迭代0.14999 1.49287 0.82695 1.52987第 21 轮迭代0.14999 1.49287 0.82695 1.52985第 22 轮迭代0.14999 1.49285 0.82695 1.52986第 23 轮迭代0.14999 1.49286 0.82694 1.52985第 24 轮迭代0.14999 1.49285 0.82694

9、 1.52984第 25 轮迭代0.14999 1.49284 0.82694 1.52984第 26 轮迭代0.14999 1.49284 0.82694 1.52983第 27 轮迭代0.14998 1.49284 0.82693 1.52983第 28 轮迭代0.14998 1.49283 0.82693 1.52982第 29 轮迭代0.14998 1.49283 0.82693 1.52982Page Rank值已计算完成#coding=utf-8# FileName:MapReducePageRank.py'''模拟map-reduce的思想，实现AB物理节

10、点的分布计算。'''#矩阵与乘因子def multiGeneMatrix(gene,Matrix): result=0*len(Matrix0) for row in range(len(Matrix0) #定义大小一样新的矩阵，初始化为0 for i in range(0,len(Matrix0): for j in range(0,len(Matrix0): resultij=Matrixij*gene return result#两个矩阵相加def addMatrix(Matrix1,Matrix2): if len(Matrix10)!=len(Matrix21

11、): print "这两个矩阵无法相加." return addList=0*len(Matrix10) for row in range(len(Matrix10) for i in range(0,len(Matrix10): for j in range(0,len(Matrix20): addListij=Matrix1ij+Matrix2ij return addList#两个矩阵合并def addColumnMatrix(Matrix1,Matrix2): result=Matrix1+Matrix2 return result#矩阵与向量相乘def multi

12、MatrixVector(m,v): rv = range(len(m) for row in range(0,len(m): temp=0 for col in range(0,len(m1): temp +=mrowcol*vcol rvrow=temp return rv'''按照map-reduce的思想，现在假设有物理节点A，B参与计算，其中网页1、2保存于A，网页3、4保存于B，试述完整的pagerank计算过程 '''alpha=0.85 #定义google 权重值aS=0,0,0.3333,0,0.3333,0.5,0.3333,

13、0.5 #假设A节点存放 page1 page2网页 原始矩阵bS=0,0,0,1,0,0,1,0 #假设B节点存放 page3 page4 网页 原始矩阵U=1,1,1,1,1,1,1,1 #全部为1的矩阵n=len(aS) #得到网页个数#计算A节点的G 矩阵fa1=multiGeneMatrix(alpha,aS) #google权重值 与 原始矩阵fa2=multiGeneMatrix(1-alpha)/n,U) #(1-a)/n*UaG=addMatrix(fa1,fa2) #aS+(1-a)/n*U#计算B节点的G 矩阵fb1=multiGeneMatrix(alpha,bS)fb

14、2=multiGeneMatrix(1-alpha)/n,U)bG=addMatrix(fb1,fb2)#AB节点特征向量qa_cur=1,1qb_cur=1,1count=1while(True): count = count +1 #得到A节点qG #print aG #print qa_cur qa_next=multiMatrixVector(aG,qa_cur); #得到B节点qG qb_next=multiMatrixVector(bG,qb_cur); #合并两个矩阵 qab_next=addColumnMatrix(qa_next,qb_next); #小数位缩小到5位 qa_

15、cur0=round(qa_cur0,5) qa_cur1=round(qa_cur1,5) qb_cur0=round(qb_cur0,5) qb_cur1=round(qb_cur1,5) qab_next0=round(qab_next0,5) qab_next1=round(qab_next1,5) qab_next2=round(qab_next2,5) qab_next3=round(qab_next3,5) #判断是否收敛到十分接近 if qa_cur0=qab_next0 and qa_cur1=qab_next1 and qb_cur0=qab_next2 and qb_cu

16、r1=qab_next3: break qa_cur0=qab_next0 qa_cur1=qab_next1 qb_cur0=qab_next2 qb_cur1=qab_next3 sum=qa_cur0+qa_cur1+qb_cur0+qb_cur1 print "P1=" + str(qa_cur0/sum) print "P2=" + str(qa_cur1/sum) print "P3=" + str(qb_cur0/sum) print "P4=" + str(qb_cur1/sum) print &q

17、uot;第 %s 轮迭代。" % count运行结果：P1=0.0523267982976P2=0.249982557734P3=0.0523267982976P4=0.645363845671第 2 轮迭代。P1=0.0177595628415P2=0.0409836065574P3=0.0409836065574P4=0.900273224044第 3 轮迭代。P1=0.00261177626645P2=0.0085593855861P3=0.0417625610923P4=0.947066277055第 4 轮迭代。P1=0.000469766144541P2=0.001321

18、21728152P3=0.0421027907045P4=0.956106225869第 5 轮迭代。P1=8.26733246251e-05P2=0.00023148530895P3=0.0421633955588P4=0.957522445808第 6 轮迭代。P1=1.86008444783e-05P2=3.72016889567e-05P3=0.0421681144324P4=0.957776083034第 7 轮迭代。P1=0.0P2=0.0P3=0.0421766145735P4=0.957823385426第 8 轮迭代。P1=0.0P2=0.0P3=0.042164705882

19、4P4=0.957835294118第 9 轮迭代。P1=0.0P2=0.0P3=0.0421804710241P4=0.957819528976第 10 轮迭代。P1=0.0P2=0.0P3=0.0421713639475P4=0.957828636052第 11 轮迭代。P1=0.0P2=0.0P3=0.0421743205248P4=0.957825679475第 12 轮迭代。P1=0.0P2=0.0P3=0.0421623249511P4=0.957837675049第 13 轮迭代。P1=0.0P2=0.0P3=0.0421676545301P4=0.95783234547第 14

20、 轮迭代。P1=0.0P2=0.0P3=0.0421864584325P4=0.957813541567第 15 轮迭代。P1=0.0P2=0.0P3=0.0421977080433P4=0.957802291957第 16 轮迭代。P1=0.0P2=0.0P3=0.042161055231P4=0.957838944769第 17 轮迭代。P1=0.0P2=0.0P3=0.0422000948317P4=0.957799905168第 18 轮迭代。P1=0.0P2=0.0P3=0.042203092862P4=0.957796907138第 19 轮迭代。P1=0.0P2=0.0P3=0.

21、0421557707137P4=0.957844229286第 20 轮迭代。P1=0.0P2=0.0P3=0.0422046637117P4=0.957795336288第 21 轮迭代。P1=0.0P2=0.0P3=0.0421588815433P4=0.957841118457第 22 轮迭代。P1=0.0P2=0.0P3=0.0421745490005P4=0.957825451第 23 轮迭代。P1=0.0P2=0.0P3=0.042220699109P4=0.957779300891第 24 轮迭代。P1=0.0P2=0.0P3=0.0422383227994P4=0.957761

22、677201第 25 轮迭代。P1=0.0P2=0.0P3=0.0421362926998P4=0.9578637073第 26 轮迭代。P1=0.0P2=0.0P3=0.0421216848674P4=0.957878315133第 27 轮迭代。P1=0.0P2=0.0P3=0.0421144987936P4=0.957885501206第 28 轮迭代。P1=0.0P2=0.0P3=0.0421805624075P4=0.957819437593第 29 轮迭代。P1=0.0P2=0.0P3=0.0421636615811P4=0.957836338419第 30 轮迭代。P1=0.0P

23、2=0.0P3=0.0421216848674P4=0.957878315133第 31 轮迭代。P1=0.0P2=0.0P3=0.0421052631579P4=0.957894736842第 32 轮迭代。P1=0.0P2=0.0P3=0.042225730071P4=0.957774269929第 33 轮迭代。P1=0.0P2=0.0P3=0.0421660008877P4=0.957833999112第 34 轮迭代。P1=0.0P2=0.0P3=0.0419370943585P4=0.958062905642第 35 轮迭代。P1=0.0P2=0.0P3=0.04211117349

24、8P4=0.957888826502第 36 轮迭代。P1=0.0P2=0.0P3=0.042297979798P4=0.957702020202第 37 轮迭代。P1=0.0P2=0.0P3=0.0419034090909P4=0.958096590909第 38 轮迭代。P1=0.0P2=0.0P3=0.0423322683706P4=0.957667731629第 39 轮迭代。P1=0.0P2=0.0P3=0.0422282120395P4=0.95777178796第 40 轮迭代。P1=0.0P2=0.0P3=0.0424242424242P4=0.957575757576第 41

25、 轮迭代。P1=0.0P2=0.0P3=0.0420454545455P4=0.957954545455第 42 轮迭代。P1=0.0P2=0.0P3=0.0421455938697P4=0.95785440613第 43 轮迭代。P1=0.0P2=0.0P3=0.0416666666667P4=0.958333333333第 44 轮迭代。P1=0.0P2=0.0P3=0.0420032310178P4=0.957996768982第 45 轮迭代。P1=0.0P2=0.0P3=0.0418181818182P4=0.958181818182第 46 轮迭代。P1=0.0P2=0.0P3=0

26、.0428571428571P4=0.957142857143第 47 轮迭代。P1=0.0P2=0.0P3=0.0413793103448P4=0.958620689655第 48 轮迭代。P1=0.0P2=0.0P3=0.0413436692506P4=0.958656330749第 49 轮迭代。P1=0.0P2=0.0P3=0.0434782608696P4=0.95652173913第 50 轮迭代。P1=0.0P2=0.0P3=0.0424836601307P4=0.957516339869第 51 轮迭代。P1=0.0P2=0.0P3=0.0404411764706P4=0.95

27、9558823529第 52 轮迭代。P1=0.0P2=0.0P3=0.0413223140496P4=0.95867768595第 53 轮迭代。P1=0.0P2=0.0P3=0.0418604651163P4=0.958139534884第 54 轮迭代。P1=0.0P2=0.0P3=0.0418848167539P4=0.958115183246第 55 轮迭代。P1=0.0P2=0.0P3=0.0411764705882P4=0.958823529412第 56 轮迭代。P1=0.0P2=0.0P3=0.0397350993377P4=0.960264900662第 57 轮迭代。P1

28、=0.0P2=0.0P3=0.0444444444444P4=0.955555555556第 58 轮迭代。P1=0.0P2=0.0P3=0.0416666666667P4=0.958333333333第 59 轮迭代。P1=0.0P2=0.0P3=0.0467289719626P4=0.953271028037第 60 轮迭代。P1=0.0P2=0.0P3=0.0421052631579P4=0.957894736842第 61 轮迭代。P1=0.0P2=0.0P3=0.0470588235294P4=0.952941176471第 62 轮迭代。P1=0.0P2=0.0P3=0.04P4=0.96第 63 轮迭代。P1=0.0P2=0.0P3=0.044776119403P4=0.955223880597第 64 轮迭代。P1=0.0P2=0.0P3=0.05P4=0.95第 65 轮迭代。P1=0.0P2=0.0P3=0.0377358490566P4=0.9622