4.4　PageRank算法

我们看一个实例，也就是PageRank算法。它最初被谷歌用来对用户查询的搜索结果进行排名。它产生数字来量化搜索结果在用户所执行的查询中的重要程度。该算法诞生于20世纪90年代末，其设计者是斯坦福大学的两位博士拉里·佩吉（Larry Page）和思尔格·布里恩（Sergey Brin），正是二人创立了谷歌公司。

我们先正式地定义最初设计PageRank算法时要求解的问题。

4.4.1　问题定义

每当用户在网络搜索引擎中输入查询时，通常会得到大量的搜索结果。为了使搜索结果最终对用户有用，使用一些标准对网页进行排名是很重要的，排名的方式取决于正在使用的底层算法所定义的标准。用这种排名将所有搜索结果进行汇总，最后将汇总的搜索结果呈现给用户。

4.4.2　实现PageRank算法

PageRank算法中最重要的部分是找到最佳方法来计算所返回的查询结果中每个页面的重要性。为了得出一个介于0和1的数字来量化特定页面的重要性，该算法结合了以下两个部分的信息：

• 与用户输入的查询相关的信息：该部分根据用户输入的查询来估计网页内容的相关程度。网页的内容直接取决于网页的作者。
• 与用户输入的查询无关的信息：该部分试图量化每个网页在其链接、浏览量和邻域的重要性。这个部分很难计算，因为网页是异构的，很难提出可以适用于整个网络的标准。

为了在Python中实现PageRank算法，首先，我们导入必要的包：

出于演示目的，假设我们仅分析网络中的五个网页，让我们将这组页面称为myPages，它们一起位于一个名为myWeb的网络中：

现在，我们把这些网页随机链接起来，从而模拟一个实际的网络：

现在，我们绘制一幅图来表示这些链接关系：

它创建了网络的可视化表示，如图4-8所示。

在PageRank算法中，网页间的链接关系表示为一个矩阵，该矩阵被称为转移矩阵。转移矩阵用一些算法来不断更新，以捕获网络不断变化的链接状态。转移矩阵的大小为n×n，其中n是节点数。矩阵中的数字是概率值，用来表示访问者由于出站链接而在接下来的过程中访问该链接的可能性。

在我们的示例中，图4-8展示了我们拥有的静态网络。我们定义一个可用于创建转移矩阵的函数（见图4-9）。

请注意，此函数将返回网络图的转移矩阵G。

我们为建立的静态网络图生成转移矩阵（见图4-10）。

注意，对于我们所创建的图，转移矩阵是5×5的矩阵。矩阵中的每一列对应于图中的一个节点。例如，第2列与第2个节点有关。访问者从节点2导航到节点1或节点3的概率为0.5。请注意，转移矩阵的对角线全是0，因为在我们的网络图中，没有从节点到其自身的出站链接。在实际网络中，却可能会出现这种出站链接。

注意，转移矩阵是稀疏矩阵。随着节点数量的增加，其大多数值是0。