PageRank算法如何給網(wǎng)頁(yè)排名

PageRank算法如何給網(wǎng)頁(yè)排名，相信很多沒(méi)有經(jīng)驗(yàn)的人對(duì)此束手無(wú)策，為此本文總結(jié)了問(wèn)題出現(xiàn)的原因和解決方法，通過(guò)這篇文章希望你能解決這個(gè)問(wèn)題。

1，PageRank 算法原理

PageRank 算法的核心原理是：在互聯(lián)網(wǎng)中，如果一個(gè)網(wǎng)頁(yè)被很多其它網(wǎng)頁(yè)所鏈接，說(shuō)明該網(wǎng)頁(yè)非常的重要，那么它的排名就高。

拉里·佩奇將整個(gè)互聯(lián)網(wǎng)看成一張大的圖，每個(gè)網(wǎng)站就像一個(gè)節(jié)點(diǎn)，而每個(gè)網(wǎng)頁(yè)的鏈接就像一個(gè)弧。那么，互聯(lián)網(wǎng)就可以用一個(gè)圖或者矩陣來(lái)描述。

拉里·佩奇也因該算法在30 歲時(shí)當(dāng)選為美國(guó)工程院院士。

假設(shè)目前有4 個(gè)網(wǎng)頁(yè)，分別是 A，B，C，D，它們的鏈接關(guān)系如下：

我們規(guī)定有兩種鏈：

• 出鏈：從自身引出去的鏈。

• 入鏈：從外部引入自身的鏈。

比如圖中的C 網(wǎng)頁(yè)，有兩個(gè)入鏈，一個(gè)出鏈。

PageRank 的思想就是，一個(gè)網(wǎng)頁(yè)的影響力就等于它的所有入鏈的影響力之和。

用數(shù)學(xué)公式表示為：

其中（分值代表頁(yè)面影響力）：

• PR(u) 是網(wǎng)頁(yè)u 的分值。

• Bu 是網(wǎng)頁(yè)u 的入鏈集合。

• 網(wǎng)頁(yè)v 是網(wǎng)頁(yè)u 的任意一個(gè)入鏈。

• PR(v) 是網(wǎng)面v 的分值。

• L(v) 是網(wǎng)頁(yè)v 的出鏈數(shù)量。

• 網(wǎng)頁(yè)v 帶給網(wǎng)頁(yè)u 的分值就是 PR(v) / L(v)。

• 那么PR(u) 就等于所有的入鏈分值之和。

在上面的公式中，我們假設(shè)從一個(gè)頁(yè)面v 到達(dá)它的所有的出鏈頁(yè)面的概率是相等的。

比如上圖來(lái)說(shuō)，頁(yè)面A 有三個(gè)出鏈分別鏈接到了 B、C、D 上。那么當(dāng)用戶訪問(wèn) A 的時(shí)候，就有跳轉(zhuǎn)到 B、C 或者 D 的可能性，跳轉(zhuǎn)概率均為 1/3。

2，計(jì)算網(wǎng)頁(yè)的分值

下面來(lái)看下如何計(jì)算網(wǎng)頁(yè)的分值。

我們可以用一個(gè)表格，來(lái)表示上圖中的網(wǎng)頁(yè)的鏈接關(guān)系，及每個(gè)頁(yè)面到其它頁(yè)面的概率：

根據(jù)這個(gè)表格中的數(shù)字，可以將其轉(zhuǎn)換成一個(gè)矩陣M：

假設(shè) A、B、C、D 四個(gè)頁(yè)面的初始影響力都是相同的，都為 1/4，即：

經(jīng)過(guò)第一次分值轉(zhuǎn)移之后，可以得到 W₁，如下：

同理可以得到W₂，W₃ 一直到 W_n：

• W₂ = M * W₁

• W₃ = M * W₂

• W_n = M * W_n-1

那么什么時(shí)候計(jì)算終止呢？

佩奇和布林已經(jīng)證明，不管網(wǎng)頁(yè)的初識(shí)值選擇多少（我們這假設(shè)都是1/4），最終都能保證網(wǎng)頁(yè)的分值能夠收斂到一個(gè)真實(shí)確定值。

也就是直到 W_n 不再變化為止。

這就是網(wǎng)頁(yè)分值的計(jì)算過(guò)程，還是比較好理解的。

3，PageRank 的兩個(gè)問(wèn)題

我們上文中介紹到的是PageRank 的基本原理，是簡(jiǎn)化版本。在實(shí)際應(yīng)用中會(huì)出現(xiàn)等級(jí)泄露（RankLeak）和等級(jí)沉沒(méi)（Rank Sink）的問(wèn)題。

如果一個(gè)網(wǎng)頁(yè)沒(méi)有出鏈，就會(huì)吸收其它網(wǎng)頁(yè)的分值不釋放，最終會(huì)導(dǎo)致其它網(wǎng)頁(yè)的分值為0，這種現(xiàn)象叫做等級(jí)泄露。如下圖中的網(wǎng)頁(yè)C：

相反，如果一個(gè)網(wǎng)頁(yè)沒(méi)有入鏈，最終會(huì)導(dǎo)致該網(wǎng)頁(yè)的分值為0，這種現(xiàn)象叫做等級(jí)沉沒(méi)。如下圖中的網(wǎng)頁(yè)C：

4，PageRank 的隨機(jī)瀏覽模型

為了解決上面的問(wèn)題，拉里·佩奇提出了隨機(jī)瀏覽模型，即用戶并不都是依靠網(wǎng)頁(yè)鏈接來(lái)訪問(wèn)網(wǎng)頁(yè)，也有可能用其它方式訪問(wèn)網(wǎng)址，比如輸入網(wǎng)址。

因此，提出了阻尼因子的概念，這個(gè)因子代表用戶按照跳轉(zhuǎn)鏈接來(lái)上網(wǎng)的概率，而 1-d 則代表用戶通過(guò)其它方式訪問(wèn)網(wǎng)頁(yè)的概率。

所以，將上文中的公式改進(jìn)為：

其中：

• d 為阻尼因子，通?？梢匀?strong>0.85。

• N 為網(wǎng)頁(yè)總數(shù)。

5，用代碼計(jì)算網(wǎng)頁(yè)分值

如何用代碼來(lái)計(jì)算網(wǎng)頁(yè)的PR 分值呢？（為了方便查看，我把上圖放在這里）

我們可以看到，該圖實(shí)際上就是數(shù)據(jù)結(jié)構(gòu)中的有向圖，因此我們可以通過(guò)構(gòu)建有向圖來(lái)構(gòu)建 PageRank 算法。

NetworkX 是一個(gè)Python 工具包，其中集成了常用的圖結(jié)構(gòu)和網(wǎng)絡(luò)分析算法。

我們可以用 NetworkX 來(lái)構(gòu)建上圖中的網(wǎng)絡(luò)結(jié)構(gòu)。

首先引入模塊：

import networkx as nx

用 DiGraph 類(lèi)創(chuàng)建有向圖：

G = nx.DiGraph()

將4 個(gè)網(wǎng)頁(yè)的鏈接關(guān)系，用數(shù)組表示：

edges = [
  ("A", "B"), ("A", "C"), ("A", "D"), 
  ("B", "A"), ("B", "D"), 
  ("C", "A"), 
  ("D", "B"), ("D", "C")
  ]

數(shù)組中的元素作為有向圖的邊，并添加到圖中：

for edge in edges:    
    G.add_edge(edge[0], edge[1])

使用pagerank 方法計(jì)算PR 分值：

# alpha 為阻尼因子
PRs = nx.pagerank(G, alpha=1)
print PRs

輸出每個(gè)網(wǎng)頁(yè)的PR 值：

{'A': 0.33333396911621094, 
 'B': 0.22222201029459634, 
 'C': 0.22222201029459634, 
 'D': 0.22222201029459634}

最終，我們計(jì)算出了每個(gè)網(wǎng)頁(yè)的PR 值。

6，畫(huà)出網(wǎng)絡(luò)圖

NetworkX 包中還提供了畫(huà)出網(wǎng)絡(luò)圖的方法：

import matplotlib.pyplot as plt

# 畫(huà)網(wǎng)絡(luò)圖
nx.draw_networkx(G)
plt.show()

如下：

我們還可以設(shè)置圖的形狀，節(jié)點(diǎn)的大小，邊的長(zhǎng)度等屬性。

PageRank 算法給了我們一個(gè)很重要的啟發(fā)，權(quán)重在很多時(shí)候是一個(gè)非常重要的指標(biāo)。

• 比如在人際交往中，個(gè)人的影響力不僅取決于你的朋友的數(shù)量，而且朋友的質(zhì)量非常重要，說(shuō)明了圈子的重要性。

• 比如在自媒體時(shí)代，粉絲數(shù)并不能真正的代表你的影響力，粉絲的質(zhì)量也很重要。如果你的粉絲中有很多大V，那么將大大增加你影響力。

看完上述內(nèi)容，你們掌握PageRank算法如何給網(wǎng)頁(yè)排名的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！