CS224w图机器学习（九）：Link Analysis- PageRank

前十课内容总结

本文主要介绍CS224W的第十一课，RageRank（很有名，就不赘述了）。

开始本章节内容之前，先对前十课的内容进行总结。前三节课主要讲在图的概念与性质，我们简单总结下这三讲内容所提到的与图相关的概念。

第四课到第十课主要在介绍图的各个方向，图社区、图分割、消息传播、表征学习与图神经网络。

CS224w Lecture 11: Link Analysis- PageRank

上图为CS224W第十一讲的内容框架，如下链接为第十一讲的课程讲义

1 Web as a Graph

我们都知道PageRank是谷歌的网页排名算法。诸多网页构成的网络（Web）可以看作是一张有向图，节点是网页，边是网页之间的超链接。

先深入了解有向图都有哪些重要的知识点。

先引入两个问题： 1）给定节点

[公式]

，哪些节点可以通过有向路径到达节点

[公式]

，

[公式]

， 2）给定节点

[公式]

，它可以通过有向路径到达哪些节点，

[公式]

。 基于有向图的节点能否通过有向路径到达其他节点，任意有向图可由下面两种子图来表示： 1）强连通图（Strong Connected Component, SCC）：任意节点之间都可以通过有向路径到达； 2）有向无环图（Directed Acyclic Graph, DAG）：图中没有环路，若节点

[公式]

能通过有向路径到达节点

[公式]

，那么节点

[公式]

无法到达节点

[公式]

。 如何寻找节点

[公式]

的强连通分量呢？取能到达节点

[公式]

和节点

[公式]

能到达的节点集合即可，即

[公式]

。 通过深度优先搜索/广度优先搜索都可得到

[公式]

和

[公式]

。把

[公式]

内的边全都反转，可得到

[公式]

。 接下来，我们使用谷歌之前的搜索巨头Altavista在1999年的网页数据（共2.03亿个网页，15亿个超链接），来看下网页有向图是什么样子的。 如下图1，网页

[公式]

能通过超链接访问到的网页数量分布，不难发现两极分化严重，要么极多、要么极少。 如下图2，可将2.03亿网页划分为SCC、IN、OUT、TenDrils、Tubes、Disconnected Components等部分。

图1 网页能通过超链接访问到的网页数分布

图2 Altavista网页数据的SCC和DAG

总的来看，上面讲述的内容核心是在传达：网络中的节点不是同等重要的，比如SCC、DAG内的节点重要性存在差异。我们需要通过链接分析（Link Analysis）的相关方法来计算网络节点的重要性。

2 How to organize the web: PageRank

上述已提到不同网页的重要性是不一样的，我们需要的是能够计算网页重要性的手段。

先引入这么一个观点：网页的重要性由它的超链接决定。 如果有个超链接从一个重要的网页指向当前网页，那么当前网页的重要性也很高。即重要性高的网页，它的超链接权重也应该更高。 如下图所示，网页

[公式]

的重要性为

[公式]

，且一共指向三个网页，所以网页

[公式]

的一跳网页接收的重要性为

[公式]

，共有两个网页指向网页

[公式]

，所以网页

[公式]

的重要性

[公式]

。 即任意网页

[公式]

的重要性为：

[公式]

其中网页

[公式]

为指向网页

[公式]

的网页集合，

[公式]

为网页

[公式]

指向的网页数量（出度）。

我们用有向图的随机邻接矩阵

[公式]

来表示上述公式，网页

[公式]

的出度为

[公式]

，对于所有被网页

[公式]

所指向的网页

[公式]

，我们有

[公式]

。（ 不难发现矩阵

[公式]

的列和为1） 那么节点重要性计算可用如下矩阵，可参见下图案例辅助理解。

[公式]

再仔细看上述公式，网页重要性组成的向量

[公式]

其实是随机邻接矩阵

[公式]

特征值为1时的特征向量。

除了用特征向量求解，我们还可以用更快速有效的方法：Power iteration 1）初始化节点重要性：

[公式]

2）迭代：

[公式]

3）满足条件则停止迭代：

[公式]

我们现在有了一套计算网页节点重要性的方法，但它存在一些缺陷，接下来我们会更进一步的完善这个方法。

缺陷主要有两点： 1）Dead End：有一些网页没有指向任何网页 2）Spider traps：某些网页的所有指向的网页都是它们内部，计算重要性时这些网页会吸收所有的重要性（他们不指向其他网页，重要性不会流出去，随着迭代次数的增加，这部分网页的重要性会越来越强，直至吸收所有网页的重要性） 解决方法： 每次迭代时，网页

[公式]

有

[公式]

的概率随机选择一个它指向的网页传递重要性，有

[公式]

的概率随机传给全部网页中。 最终网页

[公式]

的重要性为：

[公式]

矩阵

[公式]

（也可称为Google Matrix）也就表示为：

[公式]

在实践中，

[公式]

通常取0.8或0.9。

3 Compute PageRank

上一部分已经讲了PageRank的算法详情，这部分主要将实际落地以及落地时需要做的优化。

实际计算过程中的问题： PageRank的实际计算过程：

[公式]

，当网络中的节点数量很大时，存储

[公式]

非常耗费内存。 解决方法： 随机邻接矩阵

[公式]

通常是稀疏矩阵，Google Matrix

[公式]

是一个稠密矩阵，稀疏矩阵的存储消耗会好很多，假设每个节点平均有10条链接，矩阵

[公式]

的存储为

[公式]

，矩阵

[公式]

近似于

[公式]

。 所以在实际计算中，通过如下方式进行计算（稠密部分转化为一维向量）：

[公式]

PageRank计算流程： 1）初始化重要性：

[公式]

2）计算

[公式]

[公式]

3）计算

[公式]

[公式]

4）重复2和3，直至收敛

[公式]

4 Random Walk with Restarts and Personalized PageRank

我们已经足够了解PageRank的详情和落地实现，可按照重要性得分给节点排序。再换一个角度来思考这个问题，我们怎么用PageRank来给用户推荐合适的网页呢？

再给用户做推荐时，网络已经变成了由用户和网页组成的二分图。 以下图为例，左边是会议，右边是作者，怎么利用二分图和PageRank算法找到与ICDM最为相关的会议？怎么给作者推荐合适的会议？

解决方案是 Personalized PageRank。 在介绍算法之前，先思考下这个问题，如下图所示，在二分图中，节点

[公式]

和节点

[公式]

怎么才算有关系？

再思考第二个问题，下面三组节点

[公式]

，哪组节点的关系最强？

结合上述两个问题，我们不难发现共同的邻居越多，两个节点之间的关系也就越强，这也是Personalized PageRank算法的出发点。 我们的问题是找到某节点

[公式]

的相似节点，Personalized PageRank算法刻画节点相似性的算法逻辑如下：

pin_node = Q
for i in range(n_steps):

    # 随机选择pin_node的邻居节点
    board_node = pin_node.get_random_neighbor()  

    # 再随机选择board_node的邻居节点
    pin_node = board_node.get_random_neighbor()  
    
    # 有一定概率（alpha）从头开始随机游走
    if random() < alpha:
        pin_node = Q

alpha设置为0.5时，最终所有节点的访问频次如下图所示，这也就是所有节点与节点

[公式]

的相似度。按照从大到小排序，即可给节点

[公式]

推荐相似的节点。