本文共 4063 字,大约阅读时间需要 13 分钟。
PageRank算法是图的链接分析(link analysis)
的代表性算法,属于图数据上的无监督
学习方法。
PageRank算法最初作为互联网网页重要度
的计算方法,1996年由Page和Brin提出,并用于谷歌
搜索引擎的网页排序
。
随机游走模型
,即一阶马尔可夫链,描述随机游走者沿着有向图随机访问各个结点的行为概率收敛到平稳分布
,这时各个结点的平稳概率值就是其PageRank值,表示结点的重要度PageRank是定义在网页集合上的一个函数,对网页给出一个正实数,表示网页的重要程度,整体构成一个向量,PageRank值越高,网页就越重要,在互联网搜索的排序中可能就被排在前面
有向图
随机游走模型
,即一阶马尔可夫链,表示网页浏览者在互联网上随机浏览网页的过程平稳分布
。每个网页的PageRank 值就是平稳概率
给定一个包含 n n n 个结点 v 1 , v 2 … , v n v_1,v_2…,v_n v1,v2…,vn 的强连通且非周期性的有向图,在有向图上定义随机游走模型,即一阶马尔可夫链。
随机游走
的特点是从一个结点 到有 有向边连出的所有结点的转移概率相等,转移矩阵为M。这个马尔可夫链具有平稳分布 R, M R = R MR=R MR=R 平稳分布 R 称为这个有向图的 PageRank。R的各个分量称为各个结点的PageRank值
其中 P R ( v i ) , i = 1 , 2 , ⋯ , n , P R\left(v_{i}\right), i=1,2, \cdots, n, PR(vi),i=1,2,⋯,n, 表示结点 v i v_{i} vi 的 PageRank 值
R = [ P R ( v 1 ) P R ( v 2 ) ⋮ P R ( v n ) ] P R ( v i ) ⩾ 0 , i = 1 , 2 , ⋯ , n ∑ i = 1 n P R ( v i ) = 1 P R ( v i ) = ∑ v j ∈ M ( v i ) P R ( v j ) L ( v j ) , i = 1 , 2 , ⋯ , n \begin{array}{c}R=\left[\begin{array}{c}P R\left(v_{1}\right) \\ P R\left(v_{2}\right) \\ \vdots \\ P R\left(v_{n}\right)\end{array}\right] \\ \begin{array}{c} \\P R\left(v_{i}\right) \geqslant 0, \quad i=1,2, \cdots, n \\ \\ \sum\limits_{i=1}^{n} P R\left(v_{i}\right)=1\end{array} \\ \begin{array}{l}\\ P R\left(v_{i}\right)=\sum\limits_{v_{j} \in M\left(v_{i}\right)} \frac{P R\left(v_{j}\right)}{L\left(v_{j}\right)}, \quad i=1,2, \cdots, n\end{array}\end{array} R=⎣⎢⎢⎢⎡PR(v1)PR(v2)⋮PR(vn)⎦⎥⎥⎥⎤PR(vi)⩾0,i=1,2,⋯,ni=1∑nPR(vi)=1PR(vi)=vj∈M(vi)∑L(vj)PR(vj),i=1,2,⋯,n M ( v i ) M(v_i) M(vi) 表示指向节点 v i v_i vi 的节点集合, L ( v j ) L(v_j) L(vj) 表示节点 v j v_j vj 连出的有向边个数定理 :不可约且非周期的有限状态马尔可夫链,有唯一平稳分布存在,并且当时间趋于无穷时状态分布收敛于唯一的平稳分布。
未必满足
强连通且非周期性的条件基本定义不适用
有 n 个结点的任意有向图,定义一个一般的随机游走模型,即一阶马尔可夫链。
一般的随机游走模型的转移矩阵
由两部分的线性组合
组成: 基本转移矩阵M
,表示从一个结点到其连出的所有结点的转移概率相等
完全随机的转移矩阵
,表示从任意一个结点到任意一个结点的转移概率都是1/n
,线性组合系数为阻尼因子
d ( 0 ≤ d ≤ 1 ) d(0≤d≤1) d(0≤d≤1)这个一般随机游走的马尔可夫链存在平稳分布
,记作 R。
P R ( v i ) = d ( ∑ v j ∈ M ( v i ) P R ( v j ) L ( v j ) ) + 1 − d n , i = 1 , 2 , ⋯ , n P R\left(v_{i}\right)=d\left(\sum_{v_{j} \in M\left(v_{i}\right)} \frac{P R\left(v_{j}\right)}{L\left(v_{j}\right)}\right)+\frac{1-d}{n}, \quad i=1,2, \cdots, n PR(vi)=d⎝⎛vj∈M(vi)∑L(vj)PR(vj)⎠⎞+n1−d,i=1,2,⋯,n
一般PageRank的定义意味着互联网浏览者:
概率 d
决定按照超链接随机跳转,这时以等概率从连接出去的超链接跳转到下一个网页概率(1-d)
决定完全随机跳转,这时以等概率1/n跳转到任意一个网页没有连接出去
的超链接的网页也可以跳转出
。这样可以保证平稳分布
,即一般PageRank的存在包括迭代算法
、幂法
、代数算法
。常用的方法是 幂法
输入:含有 n 个结点的有向图,转移矩阵 M,阻尼因子 d,初始向量 R0
输出:有向图的 PageRank 向量 R2
输入:含有 n 个结点的有向图,转移矩阵 M,系数 d,初始向量 x0,计算精度 ε \varepsilon ε
输出:有向图的 PageRankR3
代数算法 通过一般转移矩阵
的逆矩阵
计算求有向图的一般 PageRank
转载地址:http://czhtf.baihongyu.com/