第一周的后半部分讲的是Link Analysis，主要讲的是PageRank的计算。

互联网在某种意义上是一个有向图，每个页面是图上的节点，而页面间的链接就是图的边。在经历了早期的目录式页面分类后，web现在进入了以Search为主的的组织方式。下面问题来了：

• 怎么确定找到的信息是可以信赖的（或者相对可以信赖的）。
• 当我们查找某个词时，哪个才是最好的结果。
• 搜索技术哪家强？

所以这里引入了给页面排序的做法，以确定页面的重要性。

PageRank

PageRank，Google家的看家算法。核心思路是，如果一个页面是重要的，那么它指向的那个页面应该也是重要的。也就是用其它页面来证明这个页面的重要性。

Flow Formulation

在一张图中，假设有节点$i$，它的PR值是$r_{i}$，它有$d_{i}$条出链，其中一条指向节点$j$。那么$j$上由$i$带来的PR值即为$\frac{r_{i}}{d_{i}}$。

根据这个需求，可以列出来一个方程组。显然，图中有几个节点，这个方程组就会有几个方程，为了给这个方程求得一个固定解，我们会人为的加上一个条件 $\sum{r_{i}} = 1$，这样就可以求解出每个节点的PR值了。

这个方法比较易于理解，但是对于大规模的页面集不适用，所以引入了Matrix Formulation。

Matrix Formulation

首先，把所有页面之间的跳转都用一个列随机矩阵(column stochastic matrix)来表示，记为$M$。对于每条链路$i\rightarrow j$，都有相应的$M_{ji} = 1/d_{i}$，其中$d$是$i$的出链路条数。下一步是Rank向量，记为$r$它是一个1维的列向量，每一个元素的值就是表示此节点的Rank值，记为$r_{i}$，此向量满足$\sum_{i}r_{i} = 1$。

有此定义后，上面介绍的Flow方程可以转换成这样： $r = M \cdot r$。

由矩阵的定义，这个$r$是矩阵$M$的单位向量(eigenvector)。即，页面的PageRank值，就是这些页面之间转移矩阵的单位向量，解出了这个向量，也就确定了这些页面的PageRank值。

求解特征向量使用的是被称为Power Iteration的方法：

• 初始化： $r^{(0)} = [1/N, \ldots , 1/N]^{T}$ ，其中$N$是图中的节点数，也即所有页面个数。
• 迭代： $r^{(t+1)} = M \cdot r^{(t)}$
• 停止条件： $|r^{(t+1) = r^{(t)}}|_{1} < \epsilon$。其中$|x_{i}|_{1} ＝ \sum_{i}|x_{i}|$是向量$i$的 L1范数 （其实就是绝对值相加，范数的定义就是 $|x_{i}|_{p} = (\sum_{i}|x_{i}|^{p})^{\frac{1}{p}}$）。此处可以使用其它的范数，如L2范数，即欧氏距离。

Teleports

如果图中有 dead end 节点，即只有进链没有出链；或者是在多个节点之间存在环，那么上面的迭代就会收敛到一个错误的结果上。解决方案就是，对于每次跳转，有$\beta$的概率跟随链路去跳，而有$1-\beta$的概率是一次随机传送 (Teleports)，这样就解决上面提到的两个问题了。在实际使用中，一般$\beta$取值为0.8或0.9。

在计算上，就是引入一个Teleports矩阵，其中的每个值都是$1/N$，$N$为节点数目。而之前的转移矩阵$M$则变为$\beta M + (1-\beta)\frac{1}{N}e \cdot e^{T}$，记为$A$。同样，状态跳转的迭代公式也变为$r = A \cdot r$。

实际使用的样子

以上说的都是理论，在那个神奇的世界里，计算机的内存都是无限大的，计算速度都是无限NB的，一句话，TA们都是超限界的。在回到了位于爬行界的真实世界后，还有其它需要考虑的东西。假设节点数目是 1 billion ，那么计算前和后的向量各需要1 billion，但是对于那个矩阵，它可是1 billion * 1 billion，也就是10^18。这个内存，有点贵哈～

一般来说，转移矩阵都是稀疏的，这样在存储的时候可以不用存多少东西，但是加了那个Teleports后，它变成每个位置都有值了，这内存使用就duang的一下上来了。还好经过计算，发现公式$r = A \cdot r$ 可以改写成：$r = \beta M \cdot r + [ \frac{1-\beta}{N} ]_{N}$。这就是说，矩阵还是那个稀疏的矩阵，但是在每次算完后，需要在向量上加上Teleports的结果。这样一来，占用的内存又回去了吧。

基本上就是这样了~