1. 首頁 > 生活百科 > >

pagerank算法實現 PageRank算法與實踐

生活百科節點

如果讓我們自己去做搜索的話，我們能夠想到的是文章和搜索詞的相關性，以此來判斷這個文章是否是我們想要的，最開始的搜索有的是這樣做的，還有的是按照網站的種類做個大的索引表，但是可以索引的關鍵字有限 。
互聯網上的網頁估計有千百億規模了（猜測），那么顯然不是所有包含搜索關鍵字的網頁都同等重要 。有的在標題中包含關鍵字，有的在文檔中包含關鍵字；有的是權威機構網站，有的是個人博客，顯然在給用戶返回網頁的時候，比較重要的網頁的應該排在前面，不重要的網頁信息排在后面 。那又來一個問題，如何確定一個網頁的重要性那 。
網頁是通過鏈接來組織的，那么我們可以把整個互聯網看成一張大的圖，每個節點為一個個網頁，網頁之間的鏈接看成邊 。網頁是否重要，要看是否有多個網頁鏈接到它 。被越多網頁鏈接的網頁越重要，當然鏈接這個網頁的多個鏈接的重要性又是不相同的 。
假設我們搜索得到很多網頁，其中一個網頁Y的排名應該來自所有指向這個網頁X1，X2，X3的權重之和：
Y網頁的權重 = X1+X2+X3...+Xn而X1，X2，...Xn的權重分別是多少，如何度量，這又需要通過鏈接到它的網頁的權重來計算，這樣循環往復，就無解了 。據說是Google的布林破解了這個怪圈，就是開始的時候給每個網頁設置相同的初始值，那么經過多輪計算后，這個算法可以保證網頁排名多次之后回收斂到排名的真實值 。
我理解下，大概是這樣子的：
第一輪的時候，我們假設所有網頁的權重都是1，那么A這個網頁的權重為1+1+1為3， 第二輪計算的時候，與A相連的網頁權重變成了2，那么最終A這個網頁的權重就變成了2+2+2=6，這樣多次計算后，被更多權重高的網頁鏈接的網頁，排名靠前，其他的靠后 。
這整個過程有點類似于民主選舉，選舉過程中每個人的票的權重又是不一樣的，這和現實也很類似 。那么PageRank算法除了計算網頁排名還有什么用那，數據實戰45講里面，有個例子比較有意思，計算泄露出來希拉里郵件列表中的人物影響力的情況，通過python的networkx庫可以方便地計算PageRank的值 。
下面的網絡圖的：
【pagerank算法實現 PageRank算法與實踐】
簡單的計算PageRank的代碼：
import networkx as nx# 創建有向圖G = nx.DiGraph() # 有向圖之間邊的關系edges = [("B1", "B"), ("B2", "B"), ("C1", "C"), ("C2", "C"), ("D1", "D"), ("D2", "D"), ("D", "A"), ("C", "A"), ("B", "A")]for edge in edges: G.add_edge(edge[0], edge[1])pagerank_list = nx.pagerank(G, alpha=1)print("pagerank值是：", pagerank_list)結果：
整個數據集合分為三個文件：Aliases.csv,Emails.csv和Persons.csv,其中Emails文件為郵件內容，包括重要的發送者和接收者信息 。Persons文件統計郵件中所有人的姓名和對應ID 。下面代碼是數據實戰中的代碼直接拿過來了，其實過程也是比較簡單，只是這個思路比較重要 。
# -*- coding: utf-8 -*-# 用 PageRank 挖掘希拉里郵件中的重要任務關系import pandas as pdimport networkx as nximport numpy as npfrom collections import defaultdictimport matplotlib.pyplot as plt# 數據加載emails = pd.read_csv("./input/Emails.csv")# 讀取別名文件file = pd.read_csv("./input/Aliases.csv")aliases = {}for index, row in file.iterrows(): aliases[row['Alias']] = row['PersonId']# 讀取人名文件file = pd.read_csv("./input/Persons.csv")persons = {}for index, row in file.iterrows(): persons[row['Id']] = row['Name']# 針對別名進行轉換 def unify_name(name): # 姓名統一小寫 name = str(name).lower() # 去掉, 和 @后面的內容 name = name.replace(",","").split("@")[0] # 別名轉換 if name in aliases.keys(): return persons[aliases[name]] return name# 畫網絡圖def show_graph(graph, layout='spring_layout'): # 使用 Spring Layout 布局，類似中心放射狀 if layout == 'circular_layout': positions=nx.circular_layout(graph) else: positions=nx.spring_layout(graph) # 設置網絡圖中的節點大小，大小與 pagerank 值相關，因為 pagerank 值很小所以需要 *20000 nodesize = [x['pagerank']*20000 for v,x in graph.nodes(data=http://www.zrodata.com/True)] # 設置網絡圖中的邊長度 edgesize = [np.sqrt(e[2]['weight']) for e in graph.edges(data=http://www.zrodata.com/True)] # 繪制節點 nx.draw_networkx_nodes(graph, positions, node_size=nodesize, alpha=0.4) # 繪制邊 nx.draw_networkx_edges(graph, positions, edge_size=edgesize, alpha=0.2) # 繪制節點的 label nx.draw_networkx_labels(graph, positions, font_size=10) # 輸出希拉里郵件中的所有人物關系圖 plt.show()# 將寄件人和收件人的姓名進行規范化emails.MetadataFrom = emails.MetadataFrom.apply(unify_name)emails.MetadataTo = emails.MetadataTo.apply(unify_name)# 設置遍的權重等于發郵件的次數edges_weights_temp = defaultdict(list)for row in zip(emails.MetadataFrom, emails.MetadataTo, emails.RawText): temp = (row[0], row[1]) if temp not in edges_weights_temp: edges_weights_temp[temp] = 1 else: edges_weights_temp[temp] = edges_weights_temp[temp] + 1# 轉化格式 (from, to), weight => from, to, weightedges_weights = [(key[0], key[1], val) for key, val in edges_weights_temp.items()]# 創建一個有向圖graph = nx.DiGraph()# 設置有向圖中的路徑及權重 (from, to, weight)graph.add_weighted_edges_from(edges_weights)# 計算每個節點（人）的 PR 值，并作為節點的 pagerank 屬性pagerank = nx.pagerank(graph)# 將 pagerank 數值作為節點的屬性nx.set_node_attributes(graph, name ='pagerank', values=pagerank)# 畫網絡圖show_graph(graph)# 將完整的圖譜進行精簡# 設置 PR 值的閾值，篩選大于閾值的重要核心節點pagerank_threshold = 0.005# 復制一份計算好的網絡圖small_graph = graph.copy()# 剪掉 PR 值小于 pagerank_threshold 的節點for n, p_rank in graph.nodes(data=http://www.zrodata.com/True): if p_rank['pagerank'] < pagerank_threshold: small_graph.remove_node(n)# 畫網絡圖,采用circular_layout布局讓篩選出來的點組成一個圓show_graph(small_graph, 'circular_layout')

推薦閱讀