python實(shí)現(xiàn)PageRank計(jì)算

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之間的小數(shù)n=len(S) #網(wǎng)頁數(shù)'''aS a權(quán)重值 由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 '''兩個(gè)矩陣相加'''def addMatrix(Matrix1,Matrix2): if len(Matrix10)!=len(Matrix2): print "這兩個(gè)矩陣無法相加." 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): #當(dāng)前向量與上次向量值偏差不大后，停止迭 break f=pr_nextprint "Page Rank值已計(jì)算完成"運(yùn)

6、行結(jié)果：第 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值已計(jì)算完成#coding=utf-8# FileName:MapReducePageRank.py'''模擬map-reduce的思想，實(shí)現(xiàn)AB物理節(jié)

10、點(diǎn)的分布計(jì)算。'''#矩陣與乘因子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#兩個(gè)矩陣相加def addMatrix(Matrix1,Matrix2): if len(Matrix10)!=len(Matrix21

11、): print "這兩個(gè)矩陣無法相加." 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#兩個(gè)矩陣合并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的思想，現(xiàn)在假設(shè)有物理節(jié)點(diǎn)A，B參與計(jì)算，其中網(wǎng)頁1、2保存于A，網(wǎng)頁3、4保存于B，試述完整的pagerank計(jì)算過程 '''alpha=0.85 #定義google 權(quán)重值aS=0,0,0.3333,0,0.3333,0.5,0.3333,

13、0.5 #假設(shè)A節(jié)點(diǎn)存放 page1 page2網(wǎng)頁 原始矩陣bS=0,0,0,1,0,0,1,0 #假設(shè)B節(jié)點(diǎn)存放 page3 page4 網(wǎng)頁 原始矩陣U=1,1,1,1,1,1,1,1 #全部為1的矩陣n=len(aS) #得到網(wǎng)頁個(gè)數(shù)#計(jì)算A節(jié)點(diǎn)的G 矩陣fa1=multiGeneMatrix(alpha,aS) #google權(quán)重值 與 原始矩陣fa2=multiGeneMatrix(1-alpha)/n,U) #(1-a)/n*UaG=addMatrix(fa1,fa2) #aS+(1-a)/n*U#計(jì)算B節(jié)點(diǎn)的G 矩陣fb1=multiGeneMatrix(alpha,bS)fb

14、2=multiGeneMatrix(1-alpha)/n,U)bG=addMatrix(fb1,fb2)#AB節(jié)點(diǎn)特征向量qa_cur=1,1qb_cur=1,1count=1while(True): count = count +1 #得到A節(jié)點(diǎn)qG #print aG #print qa_cur qa_next=multiMatrixVector(aG,qa_cur); #得到B節(jié)點(diǎn)qG qb_next=multiMatrixVector(bG,qb_cur); #合并兩個(gè)矩陣 qab_next=addColumnMatrix(qa_next,qb_next); #小數(shù)位縮小到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運(yùn)行結(jié)果：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