链接分析算法

PageRank算法

PageRank算法是一种静态的网页评级方法，每一个网页都有一个PageRank值，作为网页排序的依据。

PageRank值的影响因素

• 数量因素：如果一个页面节点接收到的入链数量越多，这个页面越重要
• 质量因素：指向页面A的入链质量不同，越是质量高的页面指向页面A，则页面A越重要

我们将网页之间的链接关系看作一个有向图G(V,E)，其中V是所有节点的集合，E是所有有向边的集合。假设|V|=n，PageRank值的定义如下：

其中，P（i）表示网页i的PageRank值，（i，j）表示存在网页j指向网页i的超链接。

我们用一个列向量P来表示n个网页的PageRank值，给定初值P0就可以通过若干次迭代得到Pn。满足公式方程组的解P*就是最终的全局PageRank值列向量。

但是，要存在这样的解，需要转移矩阵A满足三个条件：

• 随机矩阵
• 不可约矩阵
• 非周期性矩阵

随机矩阵理解为避免出现悬空节点（指没有出度的节点），否则不断迭代，网页整体的PageRank值会降低为0。

解决方式：将矩阵全为0的一行元素用1/n代替，即我们是有一定概率访问其他网页的。

不可约矩阵就是矩阵A对应的有向图是强连接图，每个节点都存在链接，即我们无论在访问哪个网页，都有概率访问别的网页。

解决方式：以α的概率选择一个链出链接继续浏览，1-α概率不点击链接，随机选择一个网页进行浏览。

最终的迭代公式为：

我们可以用幂迭代法求解，赋予任意的PageRank初始值，当PageRank值不再显著变化，趋于收敛时，迭代算法结束。