python 实现PageRank计算

#coding=utf-8 # Filename:pr.py

S=[[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(Matrix) for row in range(len(Matrix))] #定义新的矩阵大小，初始化为0

for i in range(0,len(Matrix)): for j in range(0,len(Matrix)):

mullist[i][j] += Matrix[i][j]*gene return mullist '''

两个矩阵相加'''def addMatrix(Matrix1,Matrix2): if len(Matrix1[0])!=len(Matrix2): print \这两个矩阵无法相加...\ return

addlist=[[0]*len(Matrix1) for row in range(len(Matrix1))] #定义新的矩阵大小

for i in range(0,len(Matrix1)): for j in range(0,len(Matrix2)):

addlist[i][j]=Matrix1[i][j]+Matrix2[i][j] 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(m[1])): temp+=m[row][col]*v[col] rv[row]=temp return rv #公式

f1=multiGeneMatrix(alpha,S)

f2=multiGeneMatrix((1-alpha)/len(S[0]),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_next[0],5)) +\ + str(round(pr_next[1],5)) + \ + str(round(pr_next[2],5)) + \ + str(round(pr_next[3],5))

if round(f[0],5)==round(pr_next[0],5) and round(f[1],5)==round(pr_next[1],5) and round(f[2],5)==round(pr_next[2],5) and round(f[3],5)==round(pr_next[3],5): #当前向量与上次向量值偏差不大后，停止迭 break f=pr_next

print \值已计算完成\

运行结果：

第 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.14999 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 轮迭代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 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.52982 Page Rank值已计算完成

#coding=utf-8

# FileName:MapReducePageRank.py '''

模拟map-reduce的思想，实现AB物理节点的分布计算。''' #矩阵与乘因子def multiGeneMatrix(gene,Matrix):

result=[[0]*len(Matrix[0]) for row in range(len(Matrix[0]))] #定义大小一样新的矩阵，初始化为0

for i in range(0,len(Matrix[0])): for j in range(0,len(Matrix[0])): result[i][j]=Matrix[i][j]*gene return result

#两个矩阵相加def addMatrix(Matrix1,Matrix2): if len(Matrix1[0])!=len(Matrix2[1]): print \这两个矩阵无法相加...\ return

addList=[[0]*len(Matrix1[0]) for row in range(len(Matrix1[0]))] for i in range(0,len(Matrix1[0])): for j in range(0,len(Matrix2[0])):

addList[i][j]=Matrix1[i][j]+Matrix2[i][j] return addList

#两个矩阵合并def addColumnMatrix(Matrix1,Matrix2): result=Matrix1+Matrix2 return result

#矩阵与向量相乘def multiMatrixVector(m,v): rv = range(len(m))

for row in range(0,len(m)): temp=0

for col in range(0,len(m[1])): temp +=m[row][col]*v[col] rv[row]=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,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*U aG=addMatrix(fa1,fa2) #aS+(1-a)/n*U #计算B节点的G 矩阵

fb1=multiGeneMatrix(alpha,bS) fb2=multiGeneMatrix((1-alpha)/n,U) bG=addMatrix(fb1,fb2) #AB节点特征向量 qa_cur=[1,1] qb_cur=[1,1]

count=1 while(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_cur[0]=round(qa_cur[0],5) qa_cur[1]=round(qa_cur[1],5) qb_cur[0]=round(qb_cur[0],5) qb_cur[1]=round(qb_cur[1],5)

qab_next[0]=round(qab_next[0],5) qab_next[1]=round(qab_next[1],5) qab_next[2]=round(qab_next[2],5)