超链接分析–PageRank

我们知道，在评价一篇论文它是否是这个领域当中比较优秀或者是代表作的方法常常是看有多少人引用它，但是这种判断方法可以使用自己引用自己或者作者之间互相引用而达到作弊，现在对于论文的影响因子的作弊方法计算相对复杂。pagerank的算法思想借助于文献计量学(Bibliometrics)。

在浩瀚的网络环境中，我们可以将互联网可以看成是文档之间超链接组成的有向图，其中节点是互联网中的文档，而边则是互联网之间的超链接。我们访问网页的时 候总是习惯于首先输入一个网址，然后在根据网站上的链接，进入其他的网站。对于这种情况我们认为他是一个random suffer，他首先进入一个网页，然后又以一个随机的方式进入另一个网页。在pagerank算法中实际中分两种，一种是主题相关的，另一种是与主题无 关的。例如：当random suffer进入网页A，而A又有三个指向其他三个网页的超链接B,C,D那么他有A到B，C或者D的概率就是1/3。对于从互联网中的一个网站进入到另 一个网站，我们可以与一维马尔可夫链的性质联系起来，对于马尔可夫链来说是从一个状态转换到另一个状态。当马尔科夫链达到稳定状态时，所求出来的转移矩阵 的值，就称为pagerank的值。

记录网站之间的链接关系的有向图，我们称为网络图的链接矩阵，一般用A来表示，对于从一个状态转换到另一个状态的概率，我们称之为状态转移概率，而有这些 概率所组成的矩阵，称为状态转移矩阵，在这里我们用用P来表示。一个random suffer直接进入一个网站的概率是α。
根据pagerank的计算公式，我们现在只需要知道状态转移的概率就能够计算出每个节点的pagerank的值。状态转移概率矩阵P方法如下：

1. 首先构建网络图的邻接矩阵A （N*N矩阵，其中N为马尔可夫链中状态个数）对于邻接矩阵中其中有一行全部为0的元素，将其用1/N代替。对于一行不全为0的元素，构建由下面几个步骤完成；
2. 对于不是1的元素由1/n(n为这行中所有不为0的元素的个数)；图1中的分别为1/3。
3. 将结果矩阵乘以(1-α)；
4. 对于结果矩阵中的每一项加上α/N。

这个可能和我们在平常所看到的pagerank的算法的书写公式可能会有所不一样，因为我们常常见到的pagerank的算法公式常常如下所示：

其中PR(B)为B的pagerank的值，L(B)为网页B中的超链接数(outlink)。其实这个公式的算法和上面所描述的算法是一样的，只是表现 上不同而已，如果将上述的状态转移概率在计算的时候将两个α/N和后面的部分分开来计算的话，每一项的结果和上述所得的结果一致（这里的1-d对应于状态 转移矩阵计算用的α）。