浅谈PageRank算法以及实现

背景

网络就像是一张图,网页作为节点,链接作为边。当我们想要对网页进行排名,如此多的网页如何实现呢?于是google公司基于链接投票法开发了PageRank算法用于搜索引擎对网页进行排名。

原理

  • 每个链接的投票作用于他的源页面
  • 如果页面$j$有$n$个出链,那么每个出链会获得$r_j/n$张票
  • 页面$j$的个人重要度是所有他的入链的票数之和
    根据以上的理论基础我们可以推出:
  • 一张来自重要度很高的页面的票也同样很重要
  • 如果一个页面被其他重要度很高的页面所链接,那么这个页面的重要度也很高

定义

因此我们定义一个排名分数$r_j$作为页面$j$的排名分数:
$$r_j=\Sigma_{i->j}r_i/d_i$$
($d_i$指的是节点i的度)

例子

(此处加入例子的图片page21)
在以上的图中,三个节点的分数$r_j$分别为
$$r_y = r_y/2+r_a/2$$

$$r_a=r_y/2+r_m$$

$$r_m=r_a/2$$

基础公式

知道了如何计算,我们应该抽象出适用于大型图计算的公式!

推导

随机矩阵$M$
假设网页$i$有$d_i$个出链
如果$i->j$ ,那么就设$M_{ji}=1/d_i$ 否则$M_{ji}=0$
M是一个随机矩阵,每一列的和为1
$r_i$是一列存储网页$i$重要性分数的向量
$$\Sigma_{i}r_i = 1$$
实际上$r$是$M$的特征向量
那么排名运算可以写成$r = M * r$
(此处加入例子图片page25)

算法流程

  • 输入: 一个包含N个网页节点网络图的随机矩阵M
  • 初始化分数矩阵: $r^{0} = [1/N,…,1/N]^T$
  • 循环计算: $r^(t+1)=M*r^(t)$
  • 直到收敛: $|r^(t+1)-r^(t)|_1<\epsilon$
  • 输出r(排名结果)

问题

(此处加入p37图片)
以上就是PageRank算法的全部流程,但是实际上还存在一些问题

死胡同(dead end)

死胡同现象指的是一些网页不存在出链,这会导致:

  1. 随机矩阵的步骤无处可去
  2. 导致一些重要的网页分数$r_j$降低

蜘蛛陷阱

蜘蛛陷阱是指所有的出链都在一个社区内,这会导致:

  1. 随机矩阵运算时在社区内会大幅下降
  2. 最终这个社区内的所有节点都有特别高的排名分数
    实际上蜘蛛陷阱并不是一个问题,但他会对排名分数产生影响导致最终的排名不是我们所期望得到的..

解决蜘蛛陷阱问题

(此处加入p40的图)
就像人们平时浏览网页一样,虽然一个网页有许多出链,但实际上并不会每个网页都浏览。虽然一个网页没有被链接,但是有可能会通过地址访问。
google解决蜘蛛陷阱的方法来源于此,在运算时加入随机参数$\beta$,对每个节点计算时:

  • 有$\beta$的概率浏览出链的网页
  • 有$1-\beta$的概率浏览非出链的网页
  • $\beta$介于0.8到0.9之间
    通过调整后,一个社区内的节点也有可能在某次循环中访问到社区外的节点。

解决死胡同问题

(此处加入p41的图)
对该矩阵$M$中该节点所在的行,给所有节点赋予$1/n$的值

公式的优化

那么基于以上两个问题的解决方法,我们可以推导出新的公式:
旧的计算公式:
$$r_j=\Sigma_{i->j}r_i/d_i$$
新的计算公式:
$$r_j=\Sigma_{i->j}\beta*r_i/d_i+(1-\beta)*1/N$$

于是我们得出一个新的矩阵

$$A=\betaM+(1- \beta )$$
M+(1-\beta)(1/N)_{N
N}

因此我们计算时只需要循环计算

$$r=A*r$$

最终收敛即可得到结果

实际运算该如何优化算法

那么google是如何进行实际的运算呢?整个算法最核心的步骤就是**矩阵乘法**
如果我们有足够大的内存空间可以存取矩阵 $A,r^{old},r^{new}$.
假设我们有一个包含10亿个节点的矩阵

  • 我们需要四位用来存储每个记录
  • 对于矩阵来说有20亿个记录,需要8GB
  • 矩阵$A$需要存储$N^2$个记录,$10^18$如此庞大的数据内存根本装不下。

从算法公式对算法进行优化

$$r = Ar, A_{ji}=\BetaM_{ji}+{1-\Beta}/N$$

$$r_j=\Sigma^{N}{i=1}A{ji}*r_i$$

$$r_j=\Sigma^{N}{i=1}[\Beta*M{ji}+{1-\Beta}/N]*r_i$$

$$r_j=\Sigma^{N}{i=1}\Beta*M{ji}r_i+{1-\Beta}/N\Sigma^{N}_{i=1}r_i$$

$$r_j=\Sigma^{N}{i=1}\Beta*M{ji}r_i+{1-\Beta}/N$$

通过推导我们将公式化简为

$$r=\BetaMr+[{1-\Beta}/N]_N$$

在新的公式中,我们只需

  • 计算 $r^{new}=\BetaMr^{old}$
  • 把 $r^{new}$加上$(1-\beta)/N$
    但即使是优化到如此地步,我们仍然需要足够的内存能够存储$M$矩阵。那么我们能不能对$M$矩阵的存储进行优化?

$M$矩阵的优化

原始的$M$矩阵类似于邻接矩阵,我们只需要$o(1)$的时间复杂度就可以判断某个边是否存在,但是我们算法的核心并不在于此,因此我们需要对数据结构进行修改。
(插入优化图p52)
实际上我们只需要存储节点的源、度、目标三个数据即可,因此我们用一个$N*3$的矩阵存储这些数据,第一维度存储source,第二维度存储degree,第三维度存储destination.
在这样的数据结构下,算法的流程可以写成:

  1. 初始化所有节点的$r^{new}=(1-\beta)/N$
  2. 对每个节点:
  • 将source,degree,destination读入内存
  • 对每个destination:
  • 计算$r^{new}(dest_j) += \beta*r^{old}(i)/d_j$

但是由于数据量过大,即便是这样的矩阵存储,我们也没有足够的RAM可以用来存放。

如何解决存放的问题?

由于内存空间不足,我们可以将数据存放在磁盘,并且在算法需要读取时使用读取函数进行访问和修改。
但是随之而来的问题是,如此庞大的数据文件如果进行频繁的读写实际上效率非常低,主要是因为每次访问都需要重新打开文件,并且访问到其他不需要的节点。

解决读写效率低的问题

我们可以对硬盘上的数据文件按照编号分块存储,以此提高读写速度和减少不必要的浪费。

实现

数据集

随机生成使用1 000/ 10 000/ 100 000个节点的图,每个节点随机地赋予6-16的出度

仓库地址

我的github仓库
在pagerank.py中没有对数据结构进行优化,仅存放在RAM上。
在new_pagerank1.py中我将表写入本地的json文件,每2000/100个节点的信息存为一个json文件(根据节点的多少修改)。
在算法执行的loop阶段使用函数对json文件进行读写。
原算法执行10000个节点运算需要大概几个小时,优化后10000个节点只需要26s.


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!