这篇文章总结 PageRank 相关内容

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

intuition

pagerank的直观非常简单:

  1. 整个 web 是一个是一个有向图,一个页面包含的链接,表示这个页面指向另外一个页面
  2. 重要的页面被访问的频率越高
  3. 被访问的频率(次数) 代表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’ 也就是任意两点可达,且非周期。因此我们需要解决两个问题

  1. dead end
  2. spider trap

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

  1. 每个节点以 $\beta \le 1$ 的概率分配转移链接到的节点集合,
  2. 每个节点以 $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

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

高效计算

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

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

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

  1. 矩阵是稀疏的,所以仅仅存下这个稀疏矩阵就行了,这样内存仅有 $O(|E|)$, $E$ 为网络的边的集合
  2. 分布式,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

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

版权声明

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

作者: taotao

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