PageRank 算法-Google 如何给网页排名

灰太狼 2022-11-16 05:50 195阅读 0赞

# [PageRank 算法-Google 如何给网页排名][PageRank _-Google] #

在互联网早期，随着网络上的网页逐渐增多，如何从海量网页中检索出我们想要的页面，变得非常的重要。

当时著名的雅虎和其它互联网公司都试图解决这个问题，但都没能有一个很好的解决方案。

直到1998 年前后，两位斯坦福大学的博士生，拉里·佩奇和谢尔盖·布林一起发明了著名的 **PageRank** 算法，才完美的解决了网页排名的问题。也正是因为这个算法，诞生了伟大的 **Google** 公司。

![在这里插入图片描述][20201128164559962.png]

（上图中：**左为布林**，**右为佩奇**。）

## ##

### 1，PageRank 算法原理 ###

**PageRank** 算法的核心原理是：**在互联网中，如果一个网页被很多其它网页所链接，说明该网页非常的重要，那么它的排名就高**。

拉里·佩奇将整个互联网看成一张大的图，每个网站就像一个节点，而每个网页的链接就像一个弧。那么，互联网就可以用一个图或者矩阵来描述。

> 拉里·佩奇也因该算法在30 岁时当选为美国工程院院士。

假设目前有4 个网页，分别是 **A，B，C，D**，它们的链接关系如下：

![在这里插入图片描述][20201128170854783.png]

我们规定有两种链：

*  出链：从自身引出去的链。
 *  入链：从外部引入自身的链。

比如图中的C 网页，有两个入链，一个出链。

PageRank 的思想就是，**一个网页的影响力就等于它的所有入链的影响力之和**。

用数学公式表示为：

![在这里插入图片描述][20201128171619707.png]

其中（分值代表页面影响力）：

*  `PR(u)` 是网页`u` 的分值。
 *  `Bu` 是网页`u` 的入链集合。
 *  网页`v` 是网页`u` 的任意一个入链。
 *  `PR(v)` 是网面`v` 的分值。
 *  `L(v)` 是网页`v` 的出链数量。
 *  网页`v` 带给网页`u` 的分值就是 `PR(v) / L(v)`。
 *  那么`PR(u)` 就等于所有的入链分值之和。

在上面的公式中，我们假设**从一个页面v 到达它的所有的出链页面的概率是相等的**。

比如上图来说，页面**A** 有三个出链分别链接到了 **B、C、D** 上。那么当用户访问 **A** 的时候，就有跳转到 **B、C** 或者 **D** 的可能性，跳转概率均为 **1/3**。

## ##

### 2，计算网页的分值 ###

下面来看下如何计算网页的分值。

我们可以用一个表格，来表示上图中的网页的链接关系，及每个页面到其它页面的概率：

根据这个表格中的数字，可以将其转换成一个矩阵**M**：

![在这里插入图片描述][20201128173843414.png]

假设 **A、B、C、D** 四个页面的初始影响力都是相同的，都为 **1/4**，即：

![在这里插入图片描述][20201128173925779.png]

经过第一次分值转移之后，可以得到 **W1**，如下：

![在这里插入图片描述][20201128175032751.png]

同理可以得到**W2**，**W3** 一直到 **Wn**：

* **W2** = M \* **W1**
 * **W3** = M \* **W2**
 * **Wn** = M \* **Wn-1**

那么什么时候计算终止呢？

佩奇和布林已经证明，不管网页的初识值选择多少（我们这假设都是1/4），最终都能保证网页的分值能够收敛到一个真实确定值。

也就是直到 **Wn** 不再变化为止。

这就是网页分值的计算过程，还是比较好理解的。

## ##

### 3，PageRank 的两个问题 ###

我们上文中介绍到的是**PageRank** 的基本原理，是简化版本。在实际应用中会出现**等级泄露**（RankLeak）和**等级沉没**（Rank Sink）的问题。

如果一个网页**没有出链**，就会吸收其它网页的分值不释放，最终会导致其它网页的分值为**0**，这种现象叫做**等级泄露**。如下图中的网页**C**：

![在这里插入图片描述][20201128222411596.png]

相反，如果一个网页**没有入链**，最终会导致该网页的分值为**0**，这种现象叫做**等级沉没**。如下图中的网页**C**：

![在这里插入图片描述][20201128222506105.png]

## ##

### 4，PageRank 的随机浏览模型 ###

为了解决上面的问题，拉里·佩奇提出了**随机浏览模型**，即用户并不都是依靠网页链接来访问网页，也有可能用其它方式访问网址，比如输入网址。

因此，提出了**阻尼因子**的概念，这个因子代表用户按照**跳转链接**来上网的概率，而 **1-d** 则代表用户通过其它方式访问网页的概率。

所以，将上文中的公式改进为：

![在这里插入图片描述][20201128223823862.png]

其中：

*  **d** 为阻尼因子，通常可以取**0.85**。
 *  **N** 为网页总数。

## ##

### 5，用代码计算网页分值 ###

如何用代码来计算网页的**PR** 分值呢？（为了方便查看，我把上图放在这里）

![在这里插入图片描述][20201128170854783.png]

我们可以看到，该图实际上就是数据结构中的**有向图**，因此我们可以通过构建有向图来构建 **PageRank** 算法。

[NetworkX][] 是一个**Python** 工具包，其中集成了常用的**图结构和网络分析算法**。

我们可以用 **NetworkX** 来构建上图中的网络结构。

首先引入模块：

import networkx as nx

用 **DiGraph** 类创建有向图：

G = nx.DiGraph()

将4 个网页的链接关系，用数组表示：

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

数组中的元素作为有向图的边，并添加到图中：

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

使用`pagerank` 方法计算**PR** 分值：

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

输出每个网页的**PR** 值：

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

最终，我们计算出了每个网页的**PR** 值。

## ##

### 6，画出网络图 ###

**NetworkX** 包中还提供了画出网络图的方法：

import matplotlib.pyplot as plt
    
    # 画网络图
    nx.draw_networkx(G)
    plt.show()

如下：

![在这里插入图片描述][20201129162824862.png]

我们还可以设置**图的形状，节点的大小，边的长度**等属性，具体可以点击[这里][Link 1]查看。

> 更多关于 **NetworkX** 的内容可以参考其[官方文档][Link 2]。

## ##

### 7，总结 ###

**PageRank** 算法给了我们一个很重要的启发，**权重**在很多时候是一个非常重要的指标。

*  比如在人际交往中，个人的影响力不仅取决于你的朋友的数量，而且朋友的质量非常重要，说明了**圈子**的重要性。
 *  比如在自媒体时代，粉丝数并不能真正的代表你的影响力，粉丝的质量也很重要。如果你的粉丝中有很多大V，那么将大大增加你影响力。

本篇文章主要介绍了：

*  **PageRank** 算法的原理。
 *  简化版的**PageRank** 算法遇到的问题，以及解决方案：
    
     *  等级泄露和等级沉没。
     *  引出**随机浏览模型**来解决这两个问题。
 *  如何用代码模拟PageRank 算法：
    
     *  使用了 [NetworkX][] 模块。

（本节完。）

[PageRank _-Google]: https://my.oschina.net/codeshell/blog/4968571
[20201128164559962.png]: /images/20221022/f17f0c00cde140a9a66fbec7faaadf7f.png?
[20201128170854783.png]: /images/20221022/5742d9b61fbe4eeaadd2d9bf8ae9b2f4.png?
[20201128171619707.png]: /images/20221022/6dcee3e4997b4855982962409040bbe1.png
[20201128173843414.png]: /images/20221022/40145738b58146a790062884de5ff1b6.png
[20201128173925779.png]: /images/20221022/248e2f22d7274f87824ed5106523c102.png
[20201128175032751.png]: /images/20221022/f78e7c9a332f4282a86039bd3b183a0f.png
[20201128222411596.png]: /images/20221022/3fe70b5c37f54e4eaafe9917e865af19.png
[20201128222506105.png]: /images/20221022/ff05e18542674d62933383560e0456aa.png?
[20201128223823862.png]: /images/20221022/c751b308e27f4ce5ae86e2e449b3ff00.png
[NetworkX]: https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fnetworkx.org%2F
[20201129162824862.png]: /images/20221022/40471297b79342d2b50767e1da213e75.png?
[Link 1]: https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fnetworkx.org%2Fdocumentation%2Fstable%2Freference%2Fdrawing.html
[Link 2]: https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fnetworkx.org%2Fdocumentation%2Fstable%2F