PageRank算法是图的链接分析(link analysis)
的代表性算法,属于图数据上的无监督
学习方法。
PageRank算法最初作为互联网网页重要度
的计算方法,1996年由Page和Brin提出,并用于谷歌
搜索引擎的网页排序
。
事实上,PageRank可以定义在任意有向图上,后来被应用到社会影响力分析、文本摘要等多个问题。
PageRank算法基本想法:
随机游走模型
,即一阶马尔可夫链,描述随机游走者沿着有向图随机访问各个结点的行为概率收敛到平稳分布
,这时各个结点的平稳概率值就是其PageRank值,表示结点的重要度PageRank是定义在网页集合上的一个函数,对网页给出一个正实数,表示网页的重要程度,整体构成一个向量,PageRank值越高,网页就越重要,在互联网搜索的排序中可能就被排在前面
有向图
随机游走模型
,即一阶马尔可夫链,表示网页浏览者在互联网上随机浏览网页的过程平稳分布
。每个网页的PageRank 值就是平稳概率
定理 :不可约且非周期的有限状态马尔可夫链,有唯一平稳分布存在,并且当时间趋于无穷时状态分布收敛于唯一的平稳分布。
未必满足
强连通且非周期性的条件基本定义不适用
包括迭代算法
、幂法
、代数算法
。常用的方法是 幂法