PageRank算法

taotao_2016 2020-04-04

展开全文

1. 算法来源

这个要从搜索引擎的发展讲起。最早的搜索引擎采用的是 分类目录¹的方法，即通过人工进行网页分类并整理出高质量的网站。那时 Yahoo 和国内的 hao123 就是使用的这种方法。

后来网页越来越多，人工分类已经不现实了。搜索引擎进入了 文本检索 的时代，即计算用户查询关键词与网页内容的相关程度来返回搜索结果。这种方法突破了数量的限制，但是搜索结果不是很好。因为总有某些网页来回地倒腾某些关键词使自己的搜索排名靠前。

谷歌的两位创始人，当时还是美国斯坦福大学 (Stanford University) 研究生的佩奇 (Larry Page) 和布林 (Sergey Brin) 开始了对网页排序问题的研究。他们的借鉴了学术界评判学术论文重要性的通用方法，那就是看论文的引用次数。由此想到网页的重要性也可以根据这种方法来评价。于是PageRank的核心思想就诞生了²，非常简单：

如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是PageRank值会相对较高
如果一个PageRank值很高的网页链接到一个其他的网页，那么被链接到的网页的PageRank值会相应地因此而提高

就如下图所示（一个概念图）:

在这里插入图片描述

2. 算法原理

PageRank算法³简单来说分为两步：

给每个网页一个PR值（下面用PR值指代PageRank值）
通过（投票）算法不断迭代，直至达到平稳分布为止。

互联网中的众多网页可以看作一个有向图。下图是一个简单的例子

图1-1

由于PR值物理意义上为一个网页被访问概率，所以初始值可以假设为1N{1\over N}N1，其中N为网页总数。一般情况下，所有网页的PR值的总和为1。（如果不为1的话也不是不行，最后算出来的不同网页之间PR值的大小关系仍然是正确的，只是不能直接地反映概率了。而且公式也不再是本文提供的公式了。详情见此博文。）

B、C、D三个页面都链入到A，则A的PR值将是B、C、D三个页面PR值的总和：

PR(A)=PR(B)+PR(C)+PR(D)

继续上面的假设，B除了链接到A，还链接到C和D，C除了链接到A，还链接到B，而D只链接到A，所以在计算A的PR值时，B的PR值只能投出131\over 331的票，C的PR值只能投出121\over 221的票，而D只链接到A，所以能投出全票，所以A的PR值总和应为：

PR(A)=PR(B)/3+PR(C)/2+PR(D)

所以可以得出一个网页的PR值计算公式应为：

PR(u)=∑v∈BuPR(v)L(v)PR(u)=\sum_{v\in B_u}{PR(v)\over L(v)}PR(u)=v∈Bu∑L(v)PR(v)

其中，BuB_uBu是所有链接到网页u的网页集合，网页v是属于集合BuB_uBu的一个网页，L(v)则是网页v的对外链接数(即出度)

表2-2 根据图2-1计算的PR值
在这里插入图片描述

表2-2，经过几次迭代后，PR值逐渐收敛稳定。

2.1 排名泄露

如图2-3所示，如果存在网页没有出度链接，如A节点所示，则会产生排名泄露问题，经过多次迭代后，所有网页的PR只都趋向于0。

在这里片描述
在这里插入图片描述

图中的A网页没有出链，对其他网页没有PR值的贡献，为了满足 Markov 链的收敛性，于是我们设定其对所有的网页（包括它自己）都有出链，则此图中B的PR值可表示为：

PR(B)=P(A)4+PR(D)2PR(B)={P(A)\over 4} + {PR(D)\over 2}PR(B)=4P(A)+2PR(D)

2.2 排名下沉

如图1-5所示，若网页没有入度链接，如节点A所示，经过多次迭代后，A的PR值会趋向于0。

在这里插入图片描述

2.3 排名上升

互联网中一个网页只有对自己的出链，或者几个网页的出链形成一个循环圈。那么在不断地迭代过程中，这一个或几个网页的PR值将只增不减。如下图中的A网页：
在这里插入图片描述
为了解决这个问题。我们想象一个随机浏览网页的人，当他到达A网页后，显然不会傻傻地一直被A网页的小把戏困住。我们假定他有一个确定的概率会输入网址直接跳转到一个随机的网页，并且跳转到每个网页的概率是一样的。

于是则此图中A的PR值可表示为：

PR(A)=α(PR(B)2)+(1−α)4PR(A) = \alpha(\frac{PR(B)}{2}) + \frac{(1 - \alpha)}{4}PR(A)=α(2PR(B))+4(1−α)

在一般情况下，一个网页的PR值计算如下：

PR(pi)=α∑pj∈MpiPR(pj)L(pj)+(1−α)NPR(p_{i}) = \alpha \sum_{p_{j} \in M_{p_{i}}} \frac{PR(p_{j})}{L(p_{j})} + \frac{(1 - \alpha)}{N}PR(pi)=αpj∈Mpi∑L(pj)PR(pj)+N(1−α)

其中MpiM_{p_i}Mpi是所有对pip_ipi网页有出链的网页集合，L(pj)L(p_j)L(pj)是网页pjp_jpj的出链数目，N是网页总数，ααα一般取0.850.850.85（很多论文都取0.85）。

根据上面的公式，我们可以计算每个网页的PR值，在不断迭代趋于平稳的时候，即为最终结果。具体怎样算是趋于平稳，我们在下面的PR值计算方法部分再做解释。

3. 算法证明

limn→∞Pnlim_{n→∞}P_nlimn→∞Pn是否存在？
如果极限存在，那么它是否与P0P_0P0的值无关？

PageRank算法的正确性证明包括上面两点⁴。为了方便证明，我们先将PR值的计算方法转换一下。

在这里插入图片描述
我们可以用一个矩阵来表示这张图的出链入链关系，Sij=0S_{ij}=0Sij=0表示j网页没有对i网页的出链：

S=⎛⎝⎜⎜⎜⎜01/31/31/31/2001/2001001/21/20⎞⎠⎟⎟⎟⎟S = \left(\begin{array}{cccc}0 & 1/2 & 0 & 0 \\ 1/3 & 0 & 0 & 1/2 \\ 1/3 & 0 & 1 & 1/2 \\ 1/3 & 1/2 & 0 & 0 \\ \end{array}\right)S=⎝⎜⎜⎛01/31/31/31/2001/2001001/21/20⎠⎟⎟⎞

取E为所有分量都为 1 的列向量，接着定义矩阵：

A=αS+(1−α)NEETA = \alpha S + \frac{(1 - \alpha)}{N}EE^TA=αS+N(1−α)EET

则PR值的计算如下，其中PnP_nPn为第n次迭代时各网页PR值组成的列向量：

Pn+1=APnP_{n+1} = A P_{n}Pn+1=APn

于是计算PR值的过程就变成了一个 Markov 过程，那么PageRank算法的证明也就转为证明 Markov 过程的收敛性证明：如果这个 Markov 过程收敛，那么limn→∞Pn存在，且与lim_{n→∞}P_n存在，且与limn→∞Pn存在，且与P_0$的选取无关。

若一个 Markov 过程收敛，那么它的状态转移矩阵A需要满足⁵：

A为随机矩阵。
A是不可约的。
A是非周期的。

第一点，随机矩阵又叫概率矩阵或 Markov 矩阵⁶，满足以下条件：

令aij为矩阵A中第i行第j列的元素，则∀i=1…n,j=1…n,aij≥0,且∀i=1…n,∑nj=1aij=1令a_{ij}为矩阵A中第i行第j列的元素，则\forall i = 1 \dots n, j = 1 \dots n, a_{ij} \geq 0, 且\forall i = 1 \dots n, \sum_{j = 1}^n a_{ij} = 1令aij为矩阵A中第i行第j列的元素，则∀i=1…n,j=1…n,aij≥0,且∀i=1…n,j=1∑naij=1

显然我们的A矩阵所有元素都大于等于0，并且每一列的元素和都为1。所以A矩阵为左随机矩阵。

第二点，不可约矩阵：方阵A是不可约的当且仅当与A对应的有向图是强联通的。有向图G=(V,E)是强联通的当且仅当对每一对节点对u,v∈V，存在从u到v的路径。

因为我们在之前设定用户在浏览页面的时候有确定概率通过输入网址的方式访问一个随机网页，所以A矩阵同样满足不可约的要求。

第三点，要求A是非周期的。

所谓周期性，体现在Markov链的周期性上，即，在经历一段转移之后必然会回到链中的某个位置并开始循环。若A的幂具有周期性，那么这个Markov链的状态就是周期性变化的。

因为A是素矩阵（素矩阵指自身的某个次幂为正矩阵的矩阵），所以A是非周期的。

至此，我们证明了PageRank算法的正确性。

4. PR值计算方法

4.1 幂迭代法

首先给每个页面赋予随机的PR值，然后通过Pn+1=APnP_{n+1}=AP_nPn+1=APn不断地迭代PR值。当满足下面的不等式后迭代结束，获得所有页面的PR值：

∣Pn+1−Pn∣<ϵ|P_{n+1} - P_{n}| < \epsilon∣Pn+1−Pn∣<ϵ

4.2 特征值法

当上面提到的Markov链收敛时，必有：

P=AP⇒P为矩阵A特征值1对应的特征向量（随机矩阵必有特征值1，且其特征向量所有分量全为正或全为负）P = A P \Rightarrow P为矩阵A特征值1对应的特征向量 \\（随机矩阵必有特征值1，且其特征向量所有分量全为正或全为负）P=AP⇒P为矩阵A特征值1对应的特征向量（随机矩阵必有特征值1，且其特征向量所有分量全为正或全为负）

4.3 代数法

相似的，当上面提到的Markov链收敛时，必有：

P=AP⇒P=⎧⎩αS+(1−α)NEET⎫⎭P又∵E为所有分量都为1的列向量，P的所有分量之和为1⇒P=αSP+(1−α)NE⇒(EET−αS)P=(1−α)NE⇒P=(EET−αS)−1(1−α)NEP = A P \\\Rightarrow P = \lgroup \alpha S + \frac{(1 - \alpha)}{N}EE^T \rgroup P \\又\because E为所有分量都为 1 的列向量，P的所有分量之和为1 \\\Rightarrow P = \alpha SP + \frac{(1 - \alpha)}{N}E \\\Rightarrow (EE^T - \alpha S)P = \frac{(1 - \alpha)}{N}E \\\Rightarrow P = (EE^T - \alpha S)^{-1} \frac{(1 - \alpha)}{N}E \\P=AP⇒P=⟮αS+N(1−α)EET⟯P又∵E为所有分量都为1的列向量，P的所有分量之和为1⇒P=αSP+N(1−α)E⇒(EET−αS)P=N(1−α)E⇒P=(EET−αS)−1N(1−α)E

5. 算法实现

5.1 基于迭代法的简单实现⁷

用python实现，需要先安装python-graph-core。

# -*- coding: utf-8 -*-

from pygraph.classes.digraph import digraph


class PRIterator:
    __doc__ = '''计算一张图中的PR值'''

    def __init__(self, dg):
        self.damping_factor = 0.85  # 阻尼系数,即α
        self.max_iterations = 100  # 最大迭代次数
        self.min_delta = 0.00001  # 确定迭代是否结束的参数,即ϵ
        self.graph = dg

    def page_rank(self):
        #  先将图中没有出链的节点改为对所有节点都有出链
        for node in self.graph.nodes():
            if len(self.graph.neighbors(node)) == 0:
                for node2 in self.graph.nodes():
                    digraph.add_edge(self.graph, (node, node2))

        nodes = self.graph.nodes()
        graph_size = len(nodes)

        if graph_size == 0:
            return {}
        page_rank = dict.fromkeys(nodes, 1.0 / graph_size)  # 给每个节点赋予初始的PR值
        damping_value = (1.0 - self.damping_factor) / graph_size  # 公式中的(1−α)/N部分

        flag = False
        for i in range(self.max_iterations):
            change = 0
            for node in nodes:
                rank = 0
                for incident_page in self.graph.incidents(node):  # 遍历所有“入射”的页面
                    rank += self.damping_factor * (page_rank[incident_page] / len(self.graph.neighbors(incident_page)))
                rank += damping_value
                change += abs(page_rank[node] - rank)  # 绝对值
                page_rank[node] = rank

            print("This is NO.%s iteration" % (i + 1))
            print(page_rank)

            if change < self.min_delta:
                flag = True
                break
        if flag:
            print("finished in %s iterations!" % node)
        else:
            print("finished out of 100 iterations!")
        return page_rank


if __name__ == '__main__':
    dg = digraph()

    dg.add_nodes(["A", "B", "C", "D", "E"])

    dg.add_edge(("A", "B"))
    dg.add_edge(("A", "C"))
    dg.add_edge(("A", "D"))
    dg.add_edge(("B", "D"))
    dg.add_edge(("C", "E"))
    dg.add_edge(("D", "E"))
    dg.add_edge(("B", "E"))
    dg.add_edge(("E", "A"))

    pr = PRIterator(dg)
    page_ranks = pr.page_rank()

    print("The final page rank is\n", page_ranks)

6. PageRank算法的缺点

这是一个天才的算法，原理简单但效果惊人。然而，PageRank算法还是有一些弊端。所以其实google本身也在不断改进这个算法。

第一，没有区分站内导航链接。很多网站的首页都有很多对站内其他页面的链接，称为站内导航链接。这些链接与不同网站之间的链接相比，肯定是后者更能体现PageRank值的传递关系。

第二，没有过滤广告链接和功能链接（例如常见的“分享到微博”）。这些链接通常没有什么实际价值，前者链接到广告页面，后者常常链接到某个社交网站首页。

第三，对新网页不友好。一个新网页的一般入链相对较少，即使它的内容的质量很高，要成为一个高PR值的页面仍需要很长时间的推广。

针对PageRank算法的缺点，有人提出了TrustRank算法。其最初来自于2004年斯坦福大学和雅虎的一项联合研究，用来检测垃圾网站。TrustRank算法的工作原理：先人工去识别高质量的页面(即“种子”页面)，那么由“种子”页面指向的页面也可能是高质量页面，即其TR值也高，与“种子”页面的链接越远，页面的TR值越低。“种子”页面可选出链数较多的网页，也可选PR值较高的网站。

TrustRank算法给出每个网页的TR值。将PR值与TR值结合起来，可以更准确地判断网页的重要性。