这篇文章总结 PageRank 相关内容

PageRank 在搜索引擎中用来对网页做特征评估(为网页重要性打分)，Google当年就是靠它，拿到互联网时代的门票，进而成就今天的霸主地位。同时，这也是 技术+商业 变现的例子。这边博文就在这里简要总结PageRank算法，揭开它的神秘面纱。

intuition

pagerank的直观非常简单:

整个 web 是一个是一个有向图，一个页面包含的链接，表示这个页面指向另外一个页面
重要的页面被访问的频率越高
被访问的频率(次数) 代表page的重要性

那么剩下的就是一个问题，如何评估页面被访问的次数？当然，直接统计是一种方式，不过这种方式有一个问题，最开始的时候(无人访问的时候)怎么评估？因此我们要想出一个替代的办法

这里采用的模型就是随机游走(random walk)。假设一个人在这个web上随机游走，每个链接指向的边($A\rightarrow B$) 表示从页面 $A$ 到达 $B$ 的权重，其权重为 $\frac{1}{deg-out_{A}}$。即将它自己的pagerank等概率的分给所有出边指向的链接.

最终每个页面的极限概率就是每个页面的pagerank。

表达成数学模型就是一个markov chain模型。

markov chain

转移矩阵为$M$,其中 $M_{ij}$ 表示页面$j\rightarrow i$ 的转移概率，$\mathbf{r}$ 表示rank向量长度为 $n$,表示每个页面的pagerank，也就是每个页面的极限概率,其和为1.则

$$ \begin{aligned} \mathbf{r}&=M\mathbf{r}\\\
\sum_{i=1}^n & r_i=1
\end{aligned} $$

即

$$ r_i=\sum_j M_{ij}r_j\tag{1} $$

求解

求解这个很简单，可以将上式看做固定点迭代，从任意一个随机的r(和为1)开始不停迭代，当 $||r'-r||\le \epsilon$,类似于power iteration。不过这种方法是非常naive的，在数据很大，首先matrix纯不下来，后面我们再讨论pagerank的高效计算。

现在先来看这样一个问题。一个非常核心的问题，一定有解吗？解唯一吗？

解的唯一性

基于markov chain的相关知识我们知道，markov chain要能够收敛必须要保证 ‘irreducible’ 和 ‘recurrent’ 也就是任意两点可达，且非周期。因此我们需要解决两个问题

dead end
spider trap

解决这两个问题 Google 设计pagerank的时候引入了一个策略

每个节点以 $\beta \le 1$ 的概率分配转移链接到的节点集合，

每个节点以 $1 - \beta$ 的概率转移到任意一个节点

即

$$ r_i =\beta \sum_j M_{ij}r_j + \sum \frac{(1-\beta)r_j}{N}\tag{2} $$

trick

(2) 式有一个小缺陷，即对于dead end，也就是没有出边的节点，它的出边概率之和为 $1 - \beta$,不满足出边概率和为1，也就是会造成 rank 泄露。为解决这个问题，我们可以加入下面一个trick

$r'_i = \beta \sum_j M_{ij}r_j$
$r'_i += (1-S)/N,S=\sum r'_i$

高效计算

最朴素的算法就是直接按照上面的trick进行计算，但是，这通常会有两个问题:

矩阵太大$O(N^2)$，内存不够
矩阵乘法 $O(N^2)$运行时间也不够

解决这两个问题，有两个手段

矩阵是稀疏的，所以仅仅存下这个稀疏矩阵就行了，这样内存仅有 $O(|E|)$, $E$ 为网络的边的集合
分布式，mapreduce

将矩阵存为，如

顶点	IN边集合
1	3，5

再存下每个节点的出度 $deg_i$

注意存取入边集合，有一个好处，这使得每次乘法行与行独立，可以做并行加速

这样每次迭代需要扫描内存为 $O(|M|)$,每次计算时间为 $O(|E|)$

spark简单实现

cur = 1
r_dict= [dict([(i,1/N_NODES) for i in range(N_NODES)]),dict()]

for i in range(MAX_ITERS):
    r_dict[cur]=sc.pickleFile(DEG_IN).mapValues(
        lambda in_nodes: sum(list(map(lambda e : r_dict[cur^1][e]/no_degs[e],in_nodes)))
    ).collectAsMap()
    cur ^=1

完整代码 github

以上代码没有考虑 dead end

扩展

固定teleport 集合

teleport 是说，每次$1-\beta$ 的概率不等概率转移到所有节点，而是等概率转移到一个固定节点集合 $S$。这样有一个好处，与 $S$ 连接的点的pagerank会得到提升

例如，如果 $S$ 所包含的是一个固定的topic集合，那么整个就是 topic specific PageRank

这种方法还能拿来做推荐，pinterest就是用了这种方法，将 $S$ 固定为一个 user，那与他silimar的节点会得到更大的pagerank，也就会更容易被推荐

beyond Link Analysis

PageRank 已经有了许多不同的改进，被用在许多地方，比如图中的社群检测，这个我们后面再讲

reference

Jure Leskovec,Anand Rajaraman,Jeffrey D. Ullman. Mining massive data set. ch5. link analysis.P175-212.
http://web.stanford.edu/class/cs246/ . lec 9.pagerank

版权声明

本作品为作者原创文章，采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

作者: taotao

仅允许非商业转载，转载请保留此版权声明，并注明出处

PageRank 算法简介