以下文章來自博客：/* https://www.cnblogs.com/jpcflyer/p/11180263.html * /

?

一、 PageRank 的簡化模型

我們先來看下 PageRank 是如何計算的。

我假設一共有 4 個網(wǎng)頁 A、B、C、D。它們之間的鏈接信息如圖所示：

這里有兩個概念你需要了解一下。

出鏈指的是鏈接出去的鏈接。入鏈指的是鏈接進來的鏈接。比如圖中 A 有 2 個入鏈，3 個出鏈。

簡單來說，一個網(wǎng)頁的影響力 = 所有入鏈集合的頁面的加權影響力之和，用公式表示為：

u 為待評估的頁面， B_{u} 為頁面 u 的入鏈集合。針對入鏈集合中的任意頁面 v，它能給 u 帶來的影響力是其自身的影響力 PR(v) 除以 v 頁面的出鏈數(shù)量，即頁面 v 把影響力 PR(v) 平均分配給了它的出鏈，這樣統(tǒng)計所有能給 u 帶來鏈接的頁面 v，得到的總和就是網(wǎng)頁 u 的影響力，即為 PR(u)。

所以你能看到，出鏈會給被鏈接的頁面賦予影響力，當我們統(tǒng)計了一個網(wǎng)頁鏈出去的數(shù)量，也就是統(tǒng)計了這個網(wǎng)頁的跳轉(zhuǎn)概率。

在這個例子中，你能看到 A 有三個出鏈分別鏈接到了 B、C、D 上。那么當用戶訪問 A 的時候，就有跳轉(zhuǎn)到 B、C 或者 D 的可能性，跳轉(zhuǎn)概率均為 1/3。

B 有兩個出鏈，鏈接到了 A 和 D 上，跳轉(zhuǎn)概率為 1/2。

這樣，我們可以得到 A、B、C、D 這四個網(wǎng)頁的轉(zhuǎn)移矩陣 M：

我們假設 A、B、C、D 四個頁面的初始影響力都是相同的，即：

當進行第一次轉(zhuǎn)移之后，各頁面的影響力 w_{1} 變?yōu)?#xff1a;

然后我們再用轉(zhuǎn)移矩陣乘以 w_{1} 得到 w_{2} 結(jié)果，直到第 n 次迭代后 w_{n} 影響力不再發(fā)生變化，可以收斂到 (0.3333，0.2222，0.2222，0.2222），也就是對應著 A、B、C、D 四個頁面最終平衡狀態(tài)下的影響力。

你能看出 A 頁面相比于其他頁面來說權重更大，也就是 PR 值更高。而 B、C、D 頁面的 PR 值相等。

?

至此，我們模擬了一個簡化的 PageRank 的計算過程，實際情況會比這個復雜，可能會面臨兩個問題：

1. 等級泄露（Rank Leak）：如果一個網(wǎng)頁沒有出鏈，就像是一個黑洞一樣，吸收了其他網(wǎng)頁的影響力而不釋放，最終會導致其他網(wǎng)頁的 PR 值為 0。

?

?

2. 等級沉沒（Rank Sink）：如果一個網(wǎng)頁只有出鏈，沒有入鏈（如下圖所示），計算的過程迭代下來，會導致這個網(wǎng)頁的 PR 值為 0（也就是不存在公式中的 V）。

針對等級泄露和等級沉沒的情況，我們需要靈活處理。

比如針對等級泄露的情況，我們可以把沒有出鏈的節(jié)點，先從圖中去掉，等計算完所有節(jié)點的 PR 值之后，再加上該節(jié)點進行計算。不過這種方法會導致新的等級泄露的節(jié)點的產(chǎn)生，所以工作量還是很大的。

有沒有一種方法，可以同時解決等級泄露和等級沉沒這兩個問題呢？

?

二、 PageRank 的隨機瀏覽模型

為了解決簡化模型中存在的等級泄露和等級沉沒的問題，拉里·佩奇提出了 PageRank 的隨機瀏覽模型。他假設了這樣一個場景：用戶并不都是按照跳轉(zhuǎn)鏈接的方式來上網(wǎng)，還有一種可能是不論當前處于哪個頁面，都有概率訪問到其他任意的頁面，比如說用戶就是要直接輸入網(wǎng)址訪問其他頁面，雖然這個概率比較小。

所以他定義了阻尼因子 d，這個因子代表了用戶按照跳轉(zhuǎn)鏈接來上網(wǎng)的概率，通常可以取一個固定值 0.85，而 1-d=0.15 則代表了用戶不是通過跳轉(zhuǎn)鏈接的方式來訪問網(wǎng)頁的，比如直接輸入網(wǎng)址。

其中 N 為網(wǎng)頁總數(shù)，這樣我們又可以重新迭代網(wǎng)頁的權重計算了，因為加入了阻尼因子 d，一定程度上解決了等級泄露和等級沉沒的問題。

通過數(shù)學定理（這里不進行講解）也可以證明，最終 PageRank 隨機瀏覽模型是可以收斂的，也就是可以得到一個穩(wěn)定正常的 PR 值。

?

三、?PageRank 在社交影響力評估中的應用

網(wǎng)頁之間會形成一個網(wǎng)絡，是我們的互聯(lián)網(wǎng)，論文之間也存在著相互引用的關系，可以說我們所處的環(huán)境就是各種網(wǎng)絡的集合。

只要是有網(wǎng)絡的地方，就存在出鏈和入鏈，就會有 PR 權重的計算，也就可以運用我們今天講的 PageRank 算法。

我們可以把 PageRank 算法延展到社交網(wǎng)絡領域中。比如在微博上，如果我們想要計算某個人的影響力，該怎么做呢？

一個人的微博粉絲數(shù)并不一定等于他的實際影響力。如果按照 PageRank 算法，還需要看這些粉絲的質(zhì)量如何。如果有很多明星或者大 V 關注，那么這個人的影響力一定很高。如果粉絲是通過購買僵尸粉得來的，那么即使粉絲數(shù)再多，影響力也不高。

同樣，在工作場景中，比如說脈脈這個社交軟件，它計算的就是個人在職場的影響力。如果你的工作關系是李開復、江南春這樣的名人，那么你的職場影響力一定會很高。反之，如果你是個學生，在職場上被鏈入的關系比較少的話，職場影響力就會比較低。

同樣，如果你想要看一個公司的經(jīng)營能力，也可以看這家公司都和哪些公司有合作。如果它合作的都是世界 500 強企業(yè)，那么這個公司在行業(yè)內(nèi)一定是領導者，如果這個公司的客戶都是小客戶，即使數(shù)量比較多，業(yè)內(nèi)影響力也不一定大。

除非像淘寶一樣，有海量的中小客戶，最后大客戶也會找上門來尋求合作。所以權重高的節(jié)點，往往會有一些權重同樣很高的節(jié)點在進行合作。

?

四、 如何使用工具實現(xiàn) PageRank 算法

PageRank 算法工具在 sklearn 中并不存在，我們需要找到新的工具包。實際上有一個關于圖論和網(wǎng)絡建模的工具叫 NetworkX，它是用 Python 語言開發(fā)的工具，內(nèi)置了常用的圖與網(wǎng)絡分析算法，可以方便我們進行網(wǎng)絡數(shù)據(jù)分析。

上節(jié)課，我舉了一個網(wǎng)頁權重的例子，假設一共有 4 個網(wǎng)頁 A、B、C、D，它們之間的鏈接信息如圖所示：

針對這個例子，我們看下用 NetworkX 如何計算 A、B、C、D 四個網(wǎng)頁的 PR 值，具體代碼如下：

1 import networkx as nx2 3 # 創(chuàng)建有向圖4 5 G = nx.DiGraph()6 7 # 有向圖之間邊的關系8 9 edges = [("A", "B"), ("A", "C"), ("A", "D"), ("B", "A"), ("B", "D"), ("C", "A"), ("D", "B"), ("D", "C")] 10 11 for edge in edges: 12 13 G.add_edge(edge[0], edge[1]) 14 15 pagerank_list = nx.pagerank(G, alpha=1) 16 17 print("pagerank 值是：", pagerank_list)

NetworkX 工具把中間的計算細節(jié)都已經(jīng)封裝起來了，我們直接調(diào)用 PageRank 函數(shù)就可以得到結(jié)果：

1 pagerank 值是： {'A': 0.33333396911621094, 'B': 0.22222201029459634, 'C': 0.22222201029459634, 'D': 0.22222201029459634}

?

好了，運行完這個例子之后，我們來看下 NetworkX 工具都有哪些常用的操作。

1. 關于圖的創(chuàng)建

圖可以分為無向圖和有向圖，在 NetworkX 中分別采用不同的函數(shù)進行創(chuàng)建。無向圖指的是不用節(jié)點之間的邊的方向，使用 nx.Graph() 進行創(chuàng)建；有向圖指的是節(jié)點之間的邊是有方向的，使用 nx.DiGraph() 來創(chuàng)建。在上面這個例子中，存在 A→D 的邊，但不存在 D→A 的邊。

?

2.關于節(jié)點的增加、刪除和查詢

如果想在網(wǎng)絡中增加節(jié)點，可以使用 G.add_node(‘A’) 添加一個節(jié)點，也可以使用 G.add_nodes_from([‘B’,‘C’,‘D’,‘E’]) 添加節(jié)點集合。如果想要刪除節(jié)點，可以使用 G.remove_node(node) 刪除一個指定的節(jié)點，也可以使用 G.remove_nodes_from([‘B’,‘C’,‘D’,‘E’]) 刪除集合中的節(jié)點。

那么該如何查詢節(jié)點呢？

如果你想要得到圖中所有的節(jié)點，就可以使用 G.nodes()，也可以用 G.number_of_nodes() 得到圖中節(jié)點的個數(shù)。

?

3. 關于邊的增加、刪除、查詢

增加邊與添加節(jié)點的方式相同，使用 G.add_edge(“A”, “B”) 添加指定的“從 A 到 B”的邊，也可以使用 add_edges_from 函數(shù)從邊集合中添加。我們也可以做一個加權圖，也就是說邊是帶有權重的，使用 add_weighted_edges_from 函數(shù)從帶有權重的邊的集合中添加。在這個函數(shù)的參數(shù)中接收的是 1 個或多個三元組 [u,v,w] 作為參數(shù)，u、v、w 分別代表起點、終點和權重。

另外，我們可以使用 remove_edge 函數(shù)和 remove_edges_from 函數(shù)刪除指定邊和從邊集合中刪除。

另外可以使用 edges() 函數(shù)訪問圖中所有的邊，使用 number_of_edges() 函數(shù)得到圖中邊的個數(shù)。

以上是關于圖的基本操作，如果我們創(chuàng)建了一個圖，并且對節(jié)點和邊進行了設置，就可以找到其中有影響力的節(jié)點，原理就是通過 PageRank 算法，使用 nx.pagerank(G) 這個函數(shù)，函數(shù)中的參數(shù) G 代表創(chuàng)建好的圖。

?

五、 如何用 PageRank 揭秘希拉里郵件中的人物關系

了解了 NetworkX 工具的基礎使用之后，我們來看一個實際的案例：希拉里郵件人物關系分析。

希拉里郵件事件相信你也有耳聞，對這個數(shù)據(jù)的背景我們就不做介紹了。你可以從 GitHub 上下載這個數(shù)據(jù)集：https://github.com/cystanford/PageRank

整個數(shù)據(jù)集由三個文件組成：Aliases.csv，Emails.csv 和 Persons.csv，其中 Emails 文件記錄了所有公開郵件的內(nèi)容，發(fā)送者和接收者的信息。Persons 這個文件統(tǒng)計了郵件中所有人物的姓名及對應的 ID。因為姓名存在別名的情況，為了將郵件中的人物進行統(tǒng)一，我們還需要用 Aliases 文件來查詢別名和人物的對應關系。

整個數(shù)據(jù)集包括了 9306 封郵件和 513 個人名，數(shù)據(jù)集還是比較大的。不過這一次我們不需要對郵件的內(nèi)容進行分析，只需要通過郵件中的發(fā)送者和接收者（對應 Emails.csv 文件中的 MetadataFrom 和 MetadataTo 字段）來繪制整個關系網(wǎng)絡。因為涉及到的人物很多，因此我們需要通過 PageRank 算法計算每個人物在郵件關系網(wǎng)絡中的權重，最后篩選出來最有價值的人物來進行關系網(wǎng)絡圖的繪制。

?

了解了數(shù)據(jù)集和項目背景之后，我們來設計到執(zhí)行的流程步驟：

首先我們需要加載數(shù)據(jù)源；

在準備階段：我們需要對數(shù)據(jù)進行探索，在數(shù)據(jù)清洗過程中，因為郵件中存在別名的情況，因此我們需要統(tǒng)一人物名稱。另外郵件的正文并不在我們考慮的范圍內(nèi)，只統(tǒng)計郵件中的發(fā)送者和接收者，因此我們篩選 MetadataFrom 和 MetadataTo 這兩個字段作為特征。同時，發(fā)送者和接收者可能存在多次郵件往來，需要設置權重來統(tǒng)計兩人郵件往來的次數(shù)。次數(shù)越多代表這個邊（從發(fā)送者到接收者的邊）的權重越高；

在挖掘階段：我們主要是對已經(jīng)設置好的網(wǎng)絡圖進行 PR 值的計算，但郵件中的人物有 500 多人，有些人的權重可能不高，我們需要篩選 PR 值高的人物，繪制出他們之間的往來關系。在可視化的過程中，我們可以通過節(jié)點的 PR 值來繪制節(jié)點的大小，PR 值越大，節(jié)點的繪制尺寸越大。

?

設置好流程之后，實現(xiàn)的代碼如下：

1 # -*- coding: utf-8 -*-2 3 # 用 PageRank 挖掘希拉里郵件中的重要任務關系4 5 import pandas as pd6 7 import networkx as nx8 9 import numpy as np10 11 from collections import defaultdict12 13 import matplotlib.pyplot as plt14 15 # 數(shù)據(jù)加載16 17 emails = pd.read_csv("./input/Emails.csv")18 19 # 讀取別名文件20 21 file = pd.read_csv("./input/Aliases.csv")22 23 aliases = {}24 25 for index, row in file.iterrows():26 27 aliases[row['Alias']] = row['PersonId']28 29 # 讀取人名文件30 31 file = pd.read_csv("./input/Persons.csv")32 33 persons = {}34 35 for index, row in file.iterrows():36 37 persons[row['Id']] = row['Name']38 39 # 針對別名進行轉(zhuǎn)換 40 41 def unify_name(name):42 43 # 姓名統(tǒng)一小寫44 45 name = str(name).lower()46 47 # 去掉, 和 @后面的內(nèi)容48 49 name = name.replace(",","").split("@")[0]50 51 # 別名轉(zhuǎn)換52 53 if name in aliases.keys():54 55 return persons[aliases[name]]56 57 return name58 59 # 畫網(wǎng)絡圖60 61 def show_graph(graph, layout='spring_layout'):62 63 # 使用 Spring Layout 布局，類似中心放射狀64 65 if layout == 'circular_layout':66 67 positions=nx.circular_layout(graph)68 69 else:70 71 positions=nx.spring_layout(graph)72 73 # 設置網(wǎng)絡圖中的節(jié)點大小，大小與 pagerank 值相關，因為 pagerank 值很小所以需要 *2000074 75 nodesize = [x['pagerank']*20000 for v,x in graph.nodes(data=True)]76 77 # 設置網(wǎng)絡圖中的邊長度78 79 edgesize = [np.sqrt(e[2]['weight']) for e in graph.edges(data=True)]80 81 # 繪制節(jié)點82 83 nx.draw_networkx_nodes(graph, positions, node_size=nodesize, alpha=0.4)84 85 # 繪制邊86 87 nx.draw_networkx_edges(graph, positions, edge_size=edgesize, alpha=0.2)88 89 # 繪制節(jié)點的 label90 91 nx.draw_networkx_labels(graph, positions, font_size=10)92 93 # 輸出希拉里郵件中的所有人物關系圖94 95 plt.show()96 97 # 將寄件人和收件人的姓名進行規(guī)范化98 99 emails.MetadataFrom = emails.MetadataFrom.apply(unify_name) 100 101 emails.MetadataTo = emails.MetadataTo.apply(unify_name) 102 103 # 設置遍的權重等于發(fā)郵件的次數(shù) 104 105 edges_weights_temp = defaultdict(list) 106 107 for row in zip(emails.MetadataFrom, emails.MetadataTo, emails.RawText): 108 109 temp = (row[0], row[1]) 110 111 if temp not in edges_weights_temp: 112 113 edges_weights_temp[temp] = 1 114 115 else: 116 117 edges_weights_temp[temp] = edges_weights_temp[temp] + 1 118 119 # 轉(zhuǎn)化格式 (from, to), weight => from, to, weight 120 121 edges_weights = [(key[0], key[1], val) for key, val in edges_weights_temp.items()] 122 123 # 創(chuàng)建一個有向圖 124 125 graph = nx.DiGraph() 126 127 # 設置有向圖中的路徑及權重 (from, to, weight) 128 129 graph.add_weighted_edges_from(edges_weights) 130 131 # 計算每個節(jié)點（人）的 PR 值，并作為節(jié)點的 pagerank 屬性 132 133 pagerank = nx.pagerank(graph) 134 135 # 將 pagerank 數(shù)值作為節(jié)點的屬性 136 137 nx.set_node_attributes(graph, name = 'pagerank', values=pagerank) 138 139 # 畫網(wǎng)絡圖 140 141 show_graph(graph) 142 143 144 145 # 將完整的圖譜進行精簡 146 147 # 設置 PR 值的閾值，篩選大于閾值的重要核心節(jié)點 148 149 pagerank_threshold = 0.005 150 151 # 復制一份計算好的網(wǎng)絡圖 152 153 small_graph = graph.copy() 154 155 # 剪掉 PR 值小于 pagerank_threshold 的節(jié)點 156 157 for n, p_rank in graph.nodes(data=True): 158 159 if p_rank['pagerank'] < pagerank_threshold: 160 161 small_graph.remove_node(n) 162 163 # 畫網(wǎng)絡圖, 采用 circular_layout 布局讓篩選出來的點組成一個圓 164 165 show_graph(small_graph, 'circular_layout')

?

運行結(jié)果如下：

針對代碼中的幾個模塊我做個簡單的說明：

1. 函數(shù)定義

人物的名稱需要統(tǒng)一，因此我設置了 unify_name 函數(shù)，同時設置了 show_graph 函數(shù)將網(wǎng)絡圖可視化。NetworkX 提供了多種可視化布局，這里我使用 spring_layout 布局，也就是呈中心放射狀。

除了 spring_layout 外，NetworkX 還有另外三種可視化布局，circular_layout（在一個圓環(huán)上均勻分布節(jié)點），random_layout（隨機分布節(jié)點 ），shell_layout（節(jié)點都在同心圓上）。

2. 計算邊權重

郵件的發(fā)送者和接收者的郵件往來可能不止一次，我們需要用兩者之間郵件往來的次數(shù)計算這兩者之間邊的權重，所以我用 edges_weights_temp 數(shù)組存儲權重。而上面介紹過在 NetworkX 中添加權重邊（即使用 add_weighted_edges_from 函數(shù)）的時候，接受的是 u、v、w 的三元數(shù)組，因此我們還需要對格式進行轉(zhuǎn)換，具體轉(zhuǎn)換方式見代碼。

3.PR 值計算及篩選

我使用 nx.pagerank(graph) 計算了節(jié)點的 PR 值。由于節(jié)點數(shù)量很多，我們設置了 PR 值閾值，即 pagerank_threshold=0.005，然后遍歷節(jié)點，刪除小于 PR 值閾值的節(jié)點，形成新的圖 small_graph，最后對 small_graph 進行可視化（對應運行結(jié)果的第二張圖）。

?

?

總結(jié)

以上是生活随笔為你收集整理的pagerank 的介绍的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。