1、第二十一章 PageRank算法 PageRank算法 在实际应用中许多数据都以图（graph)的形式存在，比如，互联网、 社交网络都可以看作是一个图 图数据上的机器学习具有理论与应用上的重要意义 PageRank算法是图的链接分析（link analysis）的代表性算法，属于 图数据上的无监督学习方法。 PageRank可以定义在任意有向图 上，后来被应用到社会影响力分析、 文本摘要等多个问题。 PageRank算法 PageRank算法的基本想法是在有向图上定义一个随机游走模型， 即一阶马尔可夫链，描述随机游走者沿着有向图随机访问各个结 点的行为 在一定条件下，极限情况访问每个结点的概率
2、收敛到平稳分布， 这时各个结点的平稳概率值就是其PageRank值，表示结点的重要 度。 PageRank是递归定义的，PageRank的计算可以 通过迭代算法进 行。 PageRank的定义 基本想法 历史上，PageRank算法作为计算互联网网页重要度的算法被提出 PageRank是定义在网页集合上的一个函数，它对每个网页给出一 个正实数，表示网页的重要程度， 整体构成一个向量 PageRank值越高，网页就越重要，在互联网搜索的排序中可能就 被排在前面 基本想法 假设互联网是一个有向图，在其基础上定义随机游走模型，即一 阶马尔可夫链， 表示网页浏览者在互联网上随机浏览网页的过 程 假设浏
3、览者在每个网页依照连接出去的超链接以等概率跳转到下 一个网页，并在网上持续不断进行这样的随机跳转，这个过程形 成一阶马尔可夫链 PageRank表示这个马尔可夫链的平稳分布 每个网页的PageRank值就是平稳概率。 基本想法 下图表示一个有向图，假设是简化的互联网例，结点A,B,C和D表 示网页， 结点之间的有向边表示网页之间的超链接，边上的权 值表示网页之间随机跳转的概率 基本想法 假设有一个浏览者，在网上随机游走 如果浏览者在网页A， 则下一步以1/3的概率转移到网页B,C和D 如果浏览者在网页B， 则下一步以1/2的概率转移到网页A和D 如果浏览者在网页C， 则下一步以概率1转移到网页
4、A 如果浏览者在网页D， 则下一步以1/2的概率转移到网页B和C 基本想法 直观上，一个网页，如果指向该网页的超链接越多，随机跳转到 该网页的概率也就越高，该网页的PageRank值就越高，这个网页 也就越重要 一个网页，如果指向该网页的PageRank值越高，随机跳转到该网 页的概率也就越高，该网页的PageRank 值就越高，这个网页也 就越重要 PageRank值依赖于网络的拓扑结构，一旦网络的拓扑（连接关 系）确定，PageRank值就确定 基本想法 PageRank的计算可以在互联网的有向图上进行，通常是一个迭代 过程 先假设一 个初始分布，通过迭代，不断计算所有网页的 PageRa
5、nk值，直到收敛为止 有向图 从一个结点出发到达另一个结点，所经过的边的一个序列称为一 条路径（(path), 路径上边的个数称为路径的长度 如果一个有向图从其中任何一个结点出发可以到达 其他任何一 个结点，就称这个有向图是强连通图（strongly connected graph) 有向图 假设k是一个大于1的自然数 如果从有向图的一个结点出发返回到这个结点的路径的长度都是 k的倍数，那么称这个结点为周期性结点 如果一个有向图不含有周期性结点，则称这个有向图为非周期性 图（aperiodic graph)，否则为周期性图 有向图 下图是一个周期性有向图的例子 从结点A出发返回到A，必须经过路
6、径 A一B一C一A，所有可能的 路径的长度都是3的倍数，所以结点A是周期性结点。 这个有向 图是周期性图 随机游走模型 随机游走模型 注意转移矩阵具有性质 即每个元素非负，每列元素之和为1，即矩阵M为随机矩阵 （stochastic matrix)。 随机游走模型 在有向图上的随机游走形成马尔可夫链。也就是说，随机游走者 每经一个单位时间转移一个状态 如果当前时刻在第j个结点（状态），那么下一个时刻在第i个结 点（状态）的概率是mij 这一概率只依赖于当前的状态，与过去无关，具有马尔可夫性。 随机游走模型 在下图的有向图上可以定义随机游走模型 结点A到结点B,C和D存在有向边， 可以以概率1/
7、3从A分别转移到B,C和D，并以概率0转移到A，于是可以写出 转移矩阵的第1列 结点B到结点A和D存在有向边，可以以概 率1/2从B分别转移到A和D，并以概率0分别转 移到B和C，于是可以写出矩阵的第2列 随机游走模型 于是得到转移矩阵 随机游走在某个时刻t访问各个结点的概率分布就是马尔可夫链 在时刻t的状态 分布，可以用一个n维列向量 Rt 表示，那么在时 刻t+1访问各个结点的概率分布 Rt+1满足 PageRank的基本定义 给定一个包含n个结点的强连通且非周期性的有向图，在其基础 上定义随机游走模型 假设转移矩阵为M，在时刻0,1,2,. ,t,访问各个结点的概率 分布为 则极限 存在
8、 极限向量R表示马尔可夫链的平稳分布，满足 PageRank的基本定义 PageRank的基本定义 显然有 M(vi)表示指向结点vi的结点集合 L(vj)表示结点vj连出的有向边的个数 PageRank的基本定义是理想化的，在这中情况下，PageRank存在，而 且可以通过不断迭代求得PageRank值 PageRank的基本定义 例 求下图的PageRank 例 转移矩阵 取初始分布向量 R0 为 例 以转移矩阵M连乘初始向量 R0 得到向量序列 最后得到极限向量 即有向图的PageRank值 一般的有向图未必满足强连通且非周期性的条件。所以PageRank 的基 本定义不适用。 例 下图
9、的有向图的转移矩阵M是 例 这时M不是一个随机矩阵，因为随机矩阵要求每一列的元素之和 是1，这里第3列的和是0，不是1 如果仍然计算在各个时刻的各个结点的概率分布，就会得到如下 结果 可以看到，随着时间推移，访问各个结点的概率皆变为0 PageRank的一般定义 PageRank一般定义的想法是在基本定义的基础上导入平滑项 给定一个含有n个结点vi, i=1,2, ,n，的任意有向图 假设考虑一个在图上 随机游走模型，即一阶马尔可夫链，其转 移矩阵是M，从一个结点到其连出的所有结点的转移概率相等。 PageRank的一般定义 这个马尔可夫链未必具有平稳分布 假设考虑另一个完全随机游走的模型，其
10、转移矩阵的元素全部为 1/n，也就是说从任意一个结点到任意一个结点的转移概率都是 1/n 两个转移矩阵的线性组合又构成一个新的转移矩阵，在其上可以 定义一个新的马尔可夫链。 PageRank的一般定义 容易证明这个马尔可夫链一定具有平稳分布，且平稳分布满足 式中d(0d 1）是系数，称为阻尼因子（damping factor) R是n维向量 是所有分量为1的n维向量 R表示的就是有向图的一般PageRank 表示结点vi的PageRank值 PageRank的一般定义 式（21.10）中第一项表示（状态分布是平稳分布时）依照转移 矩阵M访问各个结 点的概率，第二项表示完全随机访问各个结点 的概
11、率 阻尼因子d取值由经验决定 例如d=0.85。当d接近1时，随机游走主要依照转移矩阵M进行 当d接近0时， 随机游走主要以等概率随机访问各个结点。 PageRank的一般定义 可以由式（21.10)写出每个结点的PageRank，这是一般PageRank 的定义 第二项称为平滑项，由于采用平滑项，所有结点的PageRank值都 不会为0，具有以下性质： PageRank的一般定义 PageRank的一般定义 一般PageRank的定义意味着互联网浏览者，按照以下方法在网上随机 游走： 在任意一个网页上，浏览者或者以概率d决定按照超链接随机跳转，这 时以等概率从连接出去的超链接跳转到下一个网页
12、 或者以概率（1-d)决定完全随机跳转，这时以等概率1/n跳转到任意一 个网页 第二个机制保证从没有连接出去的超链接的网页也可以跳转出。这样 可以保证平稳分布，即一般PageRank的存在，因而一般PageRank适用 于任何结构的网络。 PageRank的计算 迭代算法 给定一个含有n个结点的有向图，转移矩阵为M，有向图的一般 PageRank由迭代公式 的极限向量R确定 PageRank的迭代算法，就是按照这个一般定义进行迭代，直至收 敛 PageRank的迭代算法 例 图中所示的有向图，取d = 0.8，求图的PageRank 例 可得转移矩阵为 按照式（21.15）计算 例 迭代公式为
13、 令初始向量 例 进行迭代 例 最后得到 计算结果表明，结点C的PageRank值超过一半，其他结点也有相 应的 PageRank值。 幂法 幂法（(power method)是一个常用的PageRank计算方法，通过近 似计算矩阵的主特征值和主特征向量求得有向图的一般PageRank 幂法主要用于近似计算矩阵的主特征值（dominant eigenvalue ）和 主特征向量（dominant eigenvector) 主特征值是指绝对值最大的特征值 主特征向量是其对应的特征向量 注意特征向量不是唯一的，只是其方向是确定的，乘上任意系数 还是特征向量 幂法 假设要求n阶矩阵A的主特征值和主特
14、征向量，采用下面的步骤。 首先，任取一个初始。维向量xo，构造如下的一个n维向量序列 然后，假设矩阵A有n个特征值，按照绝对值大小排列 对应的n个线性无关的特征向量为 这n个特征向量构成n维空间的一组基。 幂法 于是，可以将初始向量 x0 表示为 的线性组合 得到 幂法 接着，假设矩阵A的主特征值 是特征方程的单根，由上式得 由于 ， 当k充分大时有 这里 是当 时的无穷小量， 。即 幂法 说明当k充分大时向量 xk 与特征向量 v1 只相差一个系数。由式 （21.18)知， 于是主特征值 可表示为 其中xk,j和xk+1,j分别是xk和xk+1的第j个分量 幂法 在实际计算时，为了避免出现绝
15、对值过大或过小的情况，通常在 每步迭代后即进 行规范化，将向量除以其范数，即 这里的范数是向量的无穷范数，即向量各分量的绝对值的最大值 幂法 现在回到计算一般PageRank。转移矩阵可以写作 其中d是阻尼因子 E是所有元素为1的n阶方阵 根据Perron-Frobenius定理， 一般PageRank的向量R是矩阵A的 主特征向量，主特征值是1 所以可以使用幂法 近似计算一般PageRank 计算一般PageRank的幂法 例 给定一个如图所示的有向图，取 d = 0.85，求有向图的一般 PageRank。 例 利用幂法，按照算法 21.2，计算有向图的一般 PageRank 由图可知转移矩阵 （1）令 t = 0 例 （2）计算有向图的一般转移矩阵 A 例 （3） 例 例 代数算法 代数算法通过一般转移矩阵的逆矩阵计算求有向图的一般PageRank 按照一般PageRank的定义式（21.14) 于是 这里I是单位矩阵。当0d1时，线性方程组（21.23）的解存在且唯一 这样，可以通过求逆矩阵（I-dM)-1得到有向图的一般PageRank
