參考
.PageRank算法--從原理到實作
零. PageRank算法簡介
PageRank算法，即網頁排名算法，由Google創始人Larry Page在斯坦福上學的時候提出來的。該算法用于對網頁進行排名，排名高的網頁表示該網頁被通路的機率高。
該算法的主要思想有兩點：
a. 如果多個網頁指向某個網頁A，則網頁A的排名較高。
b. 如果排名高A的網頁指向某個網頁B，則網頁B的排名也較高，即網頁B的排名受指向其的網頁的排名的影響。
一、PageRank算法原理
1. 簡單的PageRank算法
如圖是一個4個網頁之間的連結情況：
假設網頁X的排名用PR(X)表示，則A的排名為PR(A)，由圖可知，網頁B和C指向了網頁A，那麼網頁A的排名可以表示為：
網頁C隻指向了A，不指向其他網頁，然而網頁B不僅指向了A，還指向了D，是以上面的公式更合理地修改為：
意思是，B的PageRank值被分給了A和D，而C的PageRank值全都給了A。
2. 考慮沒有出邊（outlink）的網頁
有的網頁，沒有指向其他網頁，如下圖中的C網頁。
那麼，假設網頁C的PageRank值被均分為到圖中的所有網頁（4個網頁），那麼A網頁的PageRank值可以表示為：
3. 網頁連結中存在環
圖中網頁C指向網頁C，不指向其他網頁。現實中，網頁自己指向自己的情況可能不太常見，但是有可能的情況是：若幹個頁面形成一個環，那麼使用者在進入其中某個網頁的時候，就陷入這個循環中。
假設當一個使用者，遇上這種情況時，以某個機率α随機指向其他任意一個網頁，每個網頁的機率相等。是以上圖中的網頁A的PageRank值可以表示為：
上面這個公式可以解釋為：α表示使用者從網頁B以機率α連結到網頁A，後面的（1-α）表示使用者從網頁C以機率（1-α）連結到網頁A。
即：
網頁B的PageRank值配置設定情況為：α*1/2給A, α*1/2給D,(1-α)/4分别給4個網頁。
網頁C的PageRank值配置設定情況為：α*1給自己C（1-α）*1/4分别給其他網頁。
4. 更一般的PageRank公式
綜合上面的論述，一般的PageRank計算公式為：
其中S(X)表示，指向網頁X的所有網頁的集合，n_i表示網頁Y_i的出邊數量，N表示所有網頁總數，α一般取0.85。
二、PageRank值的計算方法
1. 疊代法
利用前面得到的公式，進行疊代，直到疊代前後兩次的內插補點在允許的門檻值範圍内，疊代結束。
當然，可以将疊代過程寫成矩陣形式。推導過程如下：
針對前面的最後一個網絡圖，可以分别得到各個網頁的PageRank值得計算公式，如下：
寫成矩陣的形式為：
可以将上面的列向量和矩陣分别記為一些符号，上式表示為：
還有更簡潔的記法，記
A是一個常數矩陣，那麼，就有疊代公式：
也可以根據這個公式，進行疊代。
2. 代數法
因為，PageRank算法最終收斂（這個結論可以證明，此文不證明），是以，收斂時刻的PageRank值組成的列向量P應當滿足：
是以有：
這個方法不用疊代，求出矩陣的逆，就可以求出PageRank值組成的列向量P（然而，計算大規模的矩陣的逆，也是個難題。是以，這個方法代碼簡單，但效率可能不如疊代方法高）
三、Python實作
下面僅僅實作疊代法，代碼如下，需要用到Python的numpy庫用于矩陣乘法：
# 輸入為一個*.txt檔案，例如
# A B
# B C
# B A
# ...表示前者指向後者
import numpy as np
if __name__ == '__main__':
# 讀入有向圖，存儲邊
f = open('input_1.txt', 'r')
edges = [line.strip('\n').split(' ') for line in f]
print(edges)
# 根據邊擷取節點的集合
nodes = []
for edge in edges:
if edge[0] not in nodes:
nodes.append(edge[0])
if edge[1] not in nodes:
nodes.append(edge[1])
print(nodes)
N = len(nodes)
# 将節點符号（字母），映射成阿拉伯數字，便于後面生成A矩陣/S矩陣
i = 0
node_to_num = {}
for node in nodes:
node_to_num[node] = i
i += 1
for edge in edges:
edge[0] = node_to_num[edge[0]]
edge[1] = node_to_num[edge[1]]
print(edges)
# 生成初步的S矩陣
S = np.zeros([N, N])
for edge in edges:
S[edge[1], edge[0]] = 1
print(S)
# 計算比例：即一個網頁對其他網頁的PageRank值的貢獻，即進行列的歸一化處理
for j in range(N):
sum_of_col = sum(S[:,j])
for i in range(N):
S[i, j] /= sum_of_col
print(S)
# 計算矩陣A
alpha = 0.85
A = alpha*S + (1-alpha) / N * np.ones([N, N])
print(A)
# 生成初始的PageRank值，記錄在P_n中，P_n和P_n1均用于疊代
P_n = np.ones(N) / N
P_n1 = np.zeros(N)
e = 100000 # 誤差初始化
k = 0 # 記錄疊代次數
print('loop...')
while e > 0.00000001: # 開始疊代
P_n1 = np.dot(A, P_n) # 疊代公式
e = P_n1-P_n
e = max(map(abs, e)) # 計算誤差
P_n = P_n1
k += 1
print('iteration %s:'%str(k), P_n1)
print('final result:', P_n)
輸入的input_1.txt文本内容為：
A B
A C
A D
B D
C E
D E
B E
E A
結果為：
最後的一個數組，分别為A, B, C, D, E的PageRank值，其中E最高， A第二高， B和C相同均最低。
我們再來看一下這個可視化的有向圖：
可以看出，有3條邊指向E。再看，指向A的這個點是E點，是以A的PageRank值也很高，可以說“A沾了E的光”。
上面的可視化代碼如下：
import networkx as nx
import matplotlib.pyplot as plt
if __name__ == '__main__':
# 讀入有向圖，存儲邊
f = open('input_1.txt', 'r')
edges = [line.strip('\n').split(' ') for line in f]
G = nx.DiGraph()
for edge in edges:
G.add_edge(edge[0], edge[1])
nx.draw(G, with_labels=True)
plt.show()