PageRank算法的實現

目標一 迭代法實現

題目

迭代法實現大規模PageRank，網頁數量不低于10000

思路

首先創建一個txt文件，里面儲存各個點之間的關系，然后通過python語言讀取，將其轉化為矩陣，并通過公式將其轉化為相應矩陣，然后進行迭代，直至誤差小于 0.00000001結束。

原理

源代碼

import numpy as npif __name__ == '__main__':file = open('input2.txt', 'r')edges_in = []edges_out = []while True:lines = file.readline().strip('\n')if not lines:breakelse:this_line = lines.split(' ')edges_out.append(this_line[0])edges_in.append(this_line[1])# 根據邊獲取節點的集合nodes = []for edge in edges_out:if edge not in nodes:nodes.append(edge)for edge in edges_in:if edge not in nodes:nodes.append(edge)length = len(nodes) # 數據的個數i = 0node_to_num = {}for node in nodes:node_to_num[node] = ii += 1for i in range(len(edges_in)):edges_in[i] = node_to_num[edges_in[i]]edges_out[i] = node_to_num[edges_out[i]]# 生成初步的S矩陣S = np.zeros([length, length])for i in range(len(edges_in)):S[edges_in[i], edges_out[i]] = 1# 計算比例：即一個網頁對其他網頁的PageRank值的貢獻，即進行列的歸一化處理for j in range(length):sum_of_col = sum(S[:, j])for i in range(length):if sum_of_col != 0:S[i, j] /= sum_of_colelse:S[i, j] = 1/length # 判斷是零的情況# 計算矩陣Aa = 0.85A = a * S + (1 - a) / length * np.ones([length, length])# 準備進行迭代PageRank1 = np.ones(length) / lengthPageRank2 = np.zeros(length)judge = 1 # 誤差判斷while judge > 0.00000001: # 開始迭代PageRank2 = np.dot(A, PageRank1) # 迭代公式judge = PageRank2 - PageRank1judge = max(map(abs, judge))PageRank1 = PageRank2print('最終結果:', PageRank1)

運行截圖

注：因為10000個數據不太好展示，所以附帶運行了一下10以內的數據進行簡單展示。

10以內的簡單展示

目標二 代數法實現

題目

代數法求小規模PageRank的穩態解，網頁數量為5

思路

利用上一個迭代法部分代碼求得S與A，然后進行求逆等相應操作。

原理

源代碼

import numpy as npif __name__ == '__main__':file = open('input.txt', 'r')edges_in = []edges_out = []while True:lines = file.readline().strip('\n')if not lines:breakelse:this_line = lines.split(' ')edges_out.append(this_line[0])edges_in.append(this_line[1])# 根據邊獲取節點的集合nodes = []for edge in edges_out:if edge not in nodes:nodes.append(edge)for edge in edges_in:if edge not in nodes:nodes.append(edge)length = len(nodes) # 數據的個數i = 0node_to_num = {}for node in nodes:node_to_num[node] = ii += 1for i in range(len(edges_in)):edges_in[i] = node_to_num[edges_in[i]]edges_out[i] = node_to_num[edges_out[i]]# 生成初步的S矩陣S = np.zeros([length, length])for i in range(len(edges_in)):S[edges_in[i], edges_out[i]] = 1# 計算比例：即一個網頁對其他網頁的PageRank值的貢獻，即進行列的歸一化處理for j in range(length):sum_of_col = sum(S[:, j])for i in range(length):if sum_of_col != 0:S[i, j] /= sum_of_colelse:S[i, j] = 1 / length# 計算矩陣Aa = 0.85A = a * S + (1 - a) / length * np.ones([length, length])E = np.identity(length)B = np.ones(length)PageRank = (1 - a) / length * np.linalg.inv(E - a * S)PageRank = np.dot(PageRank, np.transpose(B))print('最終結果:', PageRank)

運行截圖

附加

題目

構造不存在穩態的情況，設計方法變為有穩態的情況

思路

pagerank的計算公式按迭代方式計算，保證矩陣A是正確的。

A=d*P+(1-d)ee^T/n

0<d<1

源代碼

注：本人上述代碼均使用了該方法避免不收斂

運行截圖

補充：

1.代數求解方法需要解方程組

矩陣：S
$$\begin{array}{cccc}0& 0& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 1& 0& 1& 0\end{array}$$
矩陣：(E-aS)^-1
$$\begin{array}{cccc}1& 0& 0& 0\\ ?0.425& 1& 0& ?0.85\\ 0& ?0.85& 1& 0\\ ?0.425& 0& ?0.85& 1\end{array}$$
方程：
$$?\begin{array}{l}1p_1+0p_2+0p_3+0p_4=0.375\\ ?0.425p_1+1p_2+0p_3+?0.85p_4=0.375\\ 0p_1+?0.85p_2+1p_3+0p_4=0.375\\ ?0.425p_1+0p_2+?0.85p_3+1p_4=0.375\end{array}$$
解之得：
$$\begin{array}{cccc}0.0375& 0.32640914& 0.31494776& 0.3211431\end{array}$$

2.變成穩態的方法

利用衰減系數進行判斷，用戶會有概率隨機跳轉到一個網頁，這樣可以保證存在穩態

總結

以上是生活随笔為你收集整理的pagerank简单实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。