一篇學會 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的代碼：
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 pd
import networkx as nx
import numpy as np
from collections import defaultdict
import 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=True)]
# 設置網絡圖中的邊長度
edgesize = [np.sqrt(e[2]['weight']) for e in graph.edges(data=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, weight
edges_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=True):
if p_rank['pagerank'] < pagerank_threshold:
small_graph.remove_node(n)
# 畫網絡圖,采用circular_layout布局讓篩選出來的點組成一個圓
show_graph(small_graph, 'circular_layout')
