论文笔记之The PageRank Citation Ranki

The PageRank Citation Ranking: Bringing Order to the Web

目标：

在相互引用的web page网络中，反应各个web page的重要性程度。

主要想法：

在上图中，A和B是C的backlinks，C是A和B的forwardlinks。
通常一个web page有更多的backlinks，也就是被更多的其他web pages引用，那么就会更加重要。但是又不能简单的通过backlines的数量来衡量网页的重要性。比如说，有一个web page在Yahoo首页上，可能它只有这一个backline，但是显然这个web page是比较重要的。也就是说，A引用B，如果A很重要，那么B也会相对重要。

至此，可以对pageRank有一个直观的描述。一个page的backlines的rank之和很大，那么这个page就有更高的rank。这种描述同时包括了以下两种情况：
•这个page有很多的backlines。
•这个page的backlines不多，但是它们的rank很高。

pageRank问题的定义：

u表示一个web page，Fu表示u的forwardlink page集合，Bu表示u的backline page集合。Nu=|Fu|表示从u指出去的links数量，c表示正则化因子。（c的作用是让所有web page的rank值和是常数）
至此可以定义一个pageRank的简单版本：

每个page的rank值向前传递会被均匀分配到各个边上。
式中的c<1，因为一部分pages没有指出边，因此它们的rank值没有向前传递，而是损失了。
上式是循环的（page之间可能形成环），可以对所有的rank做一个任意初始化（一般初始化成相等的值），并从任意一个page开始迭代计算，直到收敛。
下图是一个已经收敛的状态。

从矩阵的角度说明这个问题。
这里有一处需要说明，在原文中有这样一段话，经过我的反复思考与推算，认为作者出现了错误。

应该改为Let Au,v = 1/Nv if there is an edge from v to u and Au,v = 0 if not.
在下面的描述中，我会把作者的错误更正过来。
A是一个方阵，如果u到v有一条边，那么令Au,v=1/Nu，否则令Au,v=0.
以下图为例，

对应的A矩阵为：

每一列和为1，也就是该列对应的节点把它的初始权重1均匀的分给各个所指向的节点。我们可以把矩阵A看作是一个转移矩阵。
有向量R，包括了所有的page，如下：

有R=cAR.本质上其实是，前述pageRank计算公式的向量表示。

R是矩阵A的特征向量（对应的特征值是1/c，作者文中写的是c，我认为作者又写错了=.=）.
A的特征向量有多个，我们要求的是主特征向量(dominant eigenvector)，也就是绝对值最大的特征值对应的特征向量。可以计算出A绝对值最大的特征值为1，对应的特征向量为[2,1,2]，normalize后得到[0.4,0.2,0.4]，分别对应A,B,C的pageRank值，和最前面收敛图上的值是一致的。
在计算机中，我们可以使用矩阵迭代法求主特征向量。也就是，

对于上述简单版的pageRank，存在一个问题。

如上图所示，进行迭代的过程中，A,B这个loop的rank值会不断增大，这种现象称之为rank sink.
为了解决这一问题，引入rank source.

最大化c，||R'||1=1.（R'表示所有的pageRank值，令其L1范式为1，也就是绝对值之和为1）
E(u)是一个和R形状一样的向量。如果E里的值都为正，c就必须减小来平衡整个等式（E是用户自定义的参数，一般情况下令向量E中的所有值都为相同值α）。
带入到矩阵表达式中，有R'=c(AR'+E). => R'=c(A+EI)R',I是全1向量。所以，R'是(A+EI)的特征向量。

计算pageRank：

S是任意的初始化向量。

d增加了收敛率，同时也维持了||R||1=1.

Dangling Links问题

dangling links是那些指向没有forwardlink的page的边，对于这些边，它们的权重不知道该分配到哪里去。dangling links并不会影响其他page的rank值的计算，我们可以先移除这些dangling links，当所有的pageRank值被计算完后，再把它们加回来。