1. 從Google網(wǎng)頁排序到PageRank算法
（1）谷歌網(wǎng)頁怎么排序？
- 先對搜索關鍵詞進行分詞，如“技術社區(qū)”分詞為“技術”和“社區(qū)”；
- 根據(jù)建立的倒排索引返回同時包含分詞后結果的網(wǎng)頁；
- 將返回的網(wǎng)頁相關性（類似上篇文章所講的文本相似度）網(wǎng)頁，相關性越高排名越靠前
（2）怎么處理垃圾網(wǎng)頁？
那么問題來了，假如有某個垃圾網(wǎng)頁中雖然也包含大量的查詢詞，但卻并非滿足用戶需要的文檔，因此，頁面本身的重要性在網(wǎng)頁排序中也起著很重要的作用。
（3）如何度量網(wǎng)頁本身的重要性？
實際上互聯(lián)網(wǎng)上的每一篇HTML文檔除了包含文本、圖片、視頻等信息外，還包含了大量的鏈接關系，利用這些鏈接關系，能夠發(fā)現(xiàn)某些重要的網(wǎng)頁，其中網(wǎng)頁是節(jié)點，網(wǎng)頁間的鏈接關系是邊。
如上圖，某網(wǎng)頁1鏈向網(wǎng)頁2，則可以認為網(wǎng)頁1覺得網(wǎng)頁2有鏈接價值，是比較重要的網(wǎng)頁。某網(wǎng)頁被指向的次數(shù)越多，則它的重要性越高；越是重要的網(wǎng)頁，所鏈接的網(wǎng)頁的重要性也越高。
通過下圖我們可以更形象地看出鏈向網(wǎng)頁E的鏈接遠遠大于鏈向網(wǎng)頁C的鏈接，但是網(wǎng)頁C的重要性卻大于網(wǎng)頁E。這是因為網(wǎng)頁C被網(wǎng)頁B所鏈接，而網(wǎng)頁B有很高的重要性。
（4）PageRank核心思想
PageRank對網(wǎng)頁的排序可以獨立于用戶搜索進行。如果一個網(wǎng)頁被很多其它網(wǎng)頁所鏈接，說明它受到普遍的承認和信賴，那么它的排名就高。這就是 Page Rank 的核心思想。當然 Google 的 Page Rank 算法實際上要復雜得多。比如說，對來自不同網(wǎng)頁的鏈接對待不同，本身網(wǎng)頁排名高的鏈接更可靠，于是給這些鏈接予較大的權重。
通俗理解，我們可以將互聯(lián)網(wǎng)中的網(wǎng)頁理解成我們現(xiàn)實中的每個人，人與人之間的聯(lián)系就類似于網(wǎng)頁與網(wǎng)頁之間聯(lián)系，一般人的社交影響力是跟其人脈的廣度與人脈的質量有關，網(wǎng)頁也同理，其重要性也跟網(wǎng)頁的被鏈的數(shù)量與質量有關。
具體參考：PageRank算法講解
2 PageRank的python實現(xiàn)
2.1 需求
利用PageRank隨機瀏覽模型求如下圖個網(wǎng)頁的PageRank值。
即網(wǎng)頁之間的關系如下表格：
| 鏈接源ID | 鏈接目標 ID |
|---|---|
| 1 | 2,3,4,5, 7 |
| 2 | 1 |
| 3 | 1,2 |
| 4 | 2,3,5 |
| 5 | 1,3,4,6 |
| 6 | 1,5 |
| 7 | 5 |
2.2 Python實現(xiàn)
"""
Created on Sun Jan 8 23:41:29 2017
@author: whenif
"""
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
def getGm(A):
'''
功能：求狀態(tài)轉移概率矩陣Gm
@A：網(wǎng)頁鏈接圖的鄰接矩陣
'''
Gm = []
for i in range(len(A)):
cnt = 0
for j in range(len(A[i])):
if A[i][j] != 0:
cnt += 1
tran_prob = 1/cnt#轉移概率
Gm_tmp = []
for j in range(len(A[i])):
Gm_tmp.append(tran_prob*A[i][j])
Gm.append(Gm_tmp)
Gm = np.transpose(Gm)
return Gm
def getBaseLev(N):
'''
功能：計算網(wǎng)頁所獲得的基本級別(1-P)*e/n
@N：網(wǎng)頁總個數(shù)
'''
P = 0.85
e = np.ones(N)
R = [ [(1-P)*i*1/N] for i in e ]
return R
def getPR(P,Gm,R,PR):
'''
功能：獲取PR值
@P：加權系數(shù)，通常取 0.85 左右,按照超鏈接進行瀏覽的概率
@Gm：狀態(tài)轉移概率矩陣
@R：網(wǎng)頁所獲得的基本級別
@PR：每個網(wǎng)頁節(jié)點的PageRank值
'''
#狀態(tài)轉移概率矩陣Gm與PR值相乘矩陣相乘
Gm_PR = np.dot(Gm,PR)
#矩陣乘以常數(shù)P
P_Gm_PR = P*Gm_PR
#矩陣相加
new_PR = P_Gm_PR+R #PR=P*Gm'PR+(1-d)*e/n PageRank算法的核心
return new_PR
def res_vis(A,PR):
'''
將計算出來的值進行可視化展示
@A：網(wǎng)頁鏈接圖的鄰接矩陣
@PR：每個網(wǎng)頁節(jié)點最終的PageRank值
'''
#G=nx.Graph()構造的是無向圖， G=nx.DiGraph()構造的是有向圖
#初始化有向圖，節(jié)點數(shù)為7,edge（邊）被創(chuàng)造的隨機概率
all_edges = []
for i in range(7):
for j in range(len(A)):
if A[i][j]==1:
all_edges.append([i+1,j+1])
#（1）初始化有向圖
G = nx.DiGraph()
#（2）添加節(jié)點
G.add_nodes_from(range(1,len(A)))
#（3）添加有向邊
G.add_edges_from(all_edges)
#（4）添加PR值
pr = {}
for i in range(len(PR)):
pr[i+1] = PR[i][0]
# (5)畫圖
layout = nx.spring_layout(G)
plt.figure(1)
nx.draw(G, pos=layout, node_size=[x * 6000 for x in pr.values()],
node_color='m',with_labels=True)
plt.show()
def main():
#初始化參數(shù)
N = 7 #網(wǎng)頁個數(shù)
P = 0.85 #一個加權系數(shù)，通常取 0.85 左右,按照超鏈接進行瀏覽的概率
#網(wǎng)頁鏈接圖的鄰接矩陣，每一列表示一個網(wǎng)頁的出度
A = np.array([[0,1,1,0,1,1,0],
[1,0,1,1,0,0,0],
[1,0,0,1,1,0,0],
[1,0,0,0,1,0,0],
[1,0,0,1,0,1,1],
[0,0,0,0,1,0,0],
[1,0,0,0,0,0,0]])
A = np.transpose(A) #轉置
#初始化PR值為0
new_PR = []
for i in range(N):
new_PR.append([0])
count = 0#迭代計數(shù)器
while True:
PR = new_PR
R = getBaseLev(N)
Gm = getGm(A)
new_PR = getPR(P,Gm,R,PR)
count = count +1
print("第 %s 輪迭代" % count)
print(str(round(new_PR[0][0],5))
+"\t" + str(round(new_PR[1][0],5))
+ "\t" + str(round(new_PR[2][0],5))
+ "\t" + str(round(new_PR[3][0],5))
+ "\t" + str(round(new_PR[4][0],5))
+ "\t" + str(round(new_PR[5][0],5))
+ "\t" + str(round(new_PR[6][0],5)))
#設置迭代條件
if ( round(PR[0][0],5)==round(new_PR[0][0],5)
and round(PR[1][0],5)==round(new_PR[1][0],5)
and round(PR[2][0],5)==round(new_PR[2][0],5)
and round(PR[3][0],5)==round(new_PR[3][0],5)
and round(PR[4][0],5)==round(new_PR[4][0],5)
and round(PR[5][0],5)==round(new_PR[5][0],5)
and round(PR[6][0],5)==round(new_PR[6][0],5)):
break
print("-------------------")
print("PageRank值已計算完成")
res_vis(A,new_PR)
if __name__ == '__main__':
main()
2.3 結果與分析
（1）迭代結果
第 1 輪迭代
0.02143 0.02143 0.02143 0.02143 0.02143 0.02143 0.02143
第 2 輪迭代
0.06241 0.04025 0.0357 0.02963 0.05846 0.02598 0.02507
......
第 57 輪迭代
0.28026 0.15875 0.13887 0.10821 0.18418 0.06057 0.06907
第 58 輪迭代
0.28026 0.15875 0.13887 0.10821 0.18418 0.06057 0.06907
-------------------
PageRank值已計算完成
（2）可視化結果
其中圓圈編號表示網(wǎng)頁ID，圓圈大小表示PR值大小，連線表示網(wǎng)頁之間的關系，有帶黑色箭頭表示出度方向。
（3）結果匯總
| 名次 | PageRank值 | 網(wǎng)頁ID | 發(fā)出鏈接ID | 被鏈接ID |
|---|---|---|---|---|
| 1 | 0.28026 | 1 | 2,3,4,5,7 | 2,3,5,6 |
| 2 | 0.18418 | 5 | 1,3,4,6 | 1,4,6,7 |
| 3 | 0.15875 | 2 | 1 | 1,3,4 |
| 4 | 0.13887 | 3 | 1,2 | 1,4,5 |
| 5 | 0.10821 | 4 | 2,3,5 | 1,5 |
| 6 | 0.06907 | 7 | 5 | 1 |
| 7 | 0.06057 | 6 | 1,5 | 5 |
（4）結果分析
- 被鏈接個數(shù)越多其PageRank值越大，當被鏈接個數(shù)相同則發(fā)出鏈接個數(shù)越多其PageRank值越大；
- ID=1的頁面的PageRank值是0.28026，占據(jù)全體接近三分之一，成為了第1位。從可視化圖與結果匯總表格可以看出，因為ID=1頁面是鏈出鏈接和鏈入鏈接最多的頁面，也可以理解它是最受歡迎的頁面。
同時需要注意的是在PageRank值排在第3位的ID=2頁面，被3個鏈接所鏈接，而只有面向ID=1頁面發(fā)出一個鏈接，因此(面向ID=1頁面的)鏈接就得到ID=2的所有的PageRank值。
3 應用場景
在數(shù)據(jù)分析我們經(jīng)常需要從用戶的角度思考問題，如用戶購買路徑，用戶之所以沒產(chǎn)生購買，那么到底是在哪個環(huán)節(jié)出現(xiàn)了問題？基于用戶還有許許多多的分析問題，如流失用戶分析、流失用戶預警、用戶信用度分析等。
從基于用戶的分析我們可以延伸到用戶與信息、用戶與商品、用戶與用戶之間的分析，當然這三點對號入座的便分別是BAT的基因所在，其中人與人之間的分析即是社交關系分析，這也是PageRank適合的領域之一。在不同行業(yè)的應用場景不用，如以下應用場景：
- 微信、微博等應用的社交網(wǎng)絡分析，可以實現(xiàn)基于用戶的相似度的內容推薦、可以挖掘用戶的價值、用戶的社交影響力等；電商如京東等可利用用戶關系，在一定程度上協(xié)助風險控制（抓刷單等）。
- 在電信行業(yè)中利用交往圈數(shù)據(jù)可以得到用戶的社交影響力，從而在一定程度上可以協(xié)助垃圾短信等的治理；
- 文獻重要性研究（引用與被引用）
- ......
后記
數(shù)據(jù)分析與挖掘很多都是從人出發(fā)，逐漸延伸到人與人，甚至是人、人與人在時間與空間上的表現(xiàn)，其中人與人之間的關系可以說是很重要的一環(huán)，所以個人覺得PageRank還是有挺大的應用性，在工作中也是深有體會。當然文中只是舉了簡單的例子并實現(xiàn)，代碼可優(yōu)化的地方應該不少，望各路小伙伴一起交流一起進步。
參考：
[1] PageRank算法講解
本文所有代碼只用于技術交流，拒絕任何商用活動
個人Github
后續(xù)的學習細節(jié)將會記錄在個人博客DebugNLP中，歡迎各路同學互相交流
