PageRank算法学习与研究

什么是PageRank

PageRank，简称PR，是Google排名运算法则（排名公式）的一部分，是Google用于用来标识网页的等级/重要性的一种方法，是Google用来衡量一个网站的好坏的重要标准之一。PageRank计算页面的重要性，对每个链入(inbound)赋以不同的权值，链接提供页面的越重要则此链接入越高。当前页的重要性，是由其它页面的重要性决定的。在揉合了诸如Title标识和Keywords标识等所有其它因素之后，Google通过PageRank来调整结果，使那些更具“等级/重要性”的网页在搜索结果中令网站排名获得提升，从而提高搜索结果的相关性和质量。

PageRank，2001年9月被授予美国专利，专利人是Google创始人之一拉里•佩奇（Larry Page）。因此，PageRank里的Page不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的。该算法由Larry Page和Sergey Brin在斯坦福大学读研时发明的，相关论文： The PageRank Citation Ranking: Bringing Order to the Web 。按照《数学之美》（吴军）的说法，PageRank 的算法思想主要来自于 Larry Page，而 Sergey Brin 则将其转化为矩阵的迭代运算并证明其收敛性。

在PageRank提出之前，已经有研究者提出利用网页的入链数量来进行链接分析计算，这种入链方法假设一个网页的入链越多，则该网页越重要。早期的很多搜索引擎也采纳了入链数量作为链接分析方法，对于搜索引擎效果提升也有较明显的效果。PageRank除了考虑到入链数量的影响，还参考了网页质量因素，两者相结合获得了更好的网页重要性评价标准。

对于某个互联网网页A来说，该网页PageRank的计算基于以下两个基本假设：

• 数量假设：在Web图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。
• 质量假设：指向页面A的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A，则页面A越重要。

利用以上两个假设，PageRank算法刚开始赋予每个网页相同的重要性得分，通过迭代递归计算来更新每个页面节点的PageRank得分，直到得分稳定为止。PageRank计算得出的结果是网页的重要性评价，这和用户输入的查询是没有任何关系的，即算法是主题无关的。假设有一个搜索引擎，其相似度计算函数不考虑内容相似因素，完全采用PageRank来进行排序，那么这个搜索引擎的表现是什么样子的呢？这个搜索引擎对于任意不同的查询请求，返回的结果都是相同的，即返回PageRank值最高的页面。

PageRank的结果从0到10，10级为满分。PR值越高说明网页越重要/受欢迎。例如PR值为1的网站不太重要，而PR值为7~10的网站可以说是非常重要了。一般到4，就能说是一个不错的网站。

PageRank的原理

PageRank 算法的表述很简单，大体上只需要几句话就能表述清楚（不包含一些细微的修正）：

• 将整个互联网，看做一张有向图
  • 网页是图上的点
  • 链接是图上的有向边
• 每个网页都有一个权威性得分，称作 PageRank，可以把它当做是一种「投票权」
• 将每一个超链接作为一次「投票」
  • 每个网页的 PageRank 等于所有具有指向该网页超链接的网页的 PageRank 的加权和
  • 这些权值等于这些网页各自向外链接数目的倒数

PageRank的计算过程：

• 为每个网站设置一个初始的PageRank值。
• 第一次迭代：每个网站得到一个新的PageRank。
• 第二次迭代：用这组新的PageRank再按上述公式形成另一组新的PageRank。
• 重复迭代直至PageRank值收敛

什么时候迭代结束？

• 每个页面的PR值和上一次计算的PR相等
• 设定一个差值指标（0001）。当所有页面和上一次计算的PR差值平均小于该标准时，则收敛。
• 设定一个百分比（99%），当99%的页面和上一次计算的PR相等
• 设置最大循环次数

基本思想

如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/L(T)，其中PR（T）为T的PageRank值，L(T)为T的出链数，则A的PageRank值为一系列类似于T的页面重要性得分值的累加。即一个页面的得票数由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面（链入页面）的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。

简化版本

假设一个由4个网页组成的集合：A，B，C和D。如果所有页面都只链接至A，那么A的PR值将是B，C及D的PR值之和，即：

重新假设B链接到A和C，C链接到A，并且D链接到A,B,C。最初一个页面总共只有一票。所以B给A,C每个页面半票。以此类推，D投出的票只有三分之一加到了A的PR值上：

换句话说，算法将根据每个页面连出总数 平分该页面的PR值，并将其加到其所指向的页面：

最后，所有这些PR值被换算成百分比形式再乘上一个修正系数d。由于“没有向外链接的网页”传递出去的PR值会是0，而这会递归地导致指向它的页面的PR值的计算结果同样为零，所以赋给每个页面一个最小值(1-d)/N：

需要注意的是，在Sergey Brin和Lawrence Page的1998年原版论文中给每一个页面设定的最小值是1-d，而不是这里的(1-d)/N，这将导致集合中所有网页的PR值之和为N（N为集合中网页的数目）而非所期待的1。

因此，一个页面的PR值直接取决于指向它的的页面。如果在最初给每个网页一个随机且非零的PR值，经过重复计算，这些页面的PR值会趋向于某个定值，也就是处于收敛的状态，即最终结果。这就是搜索引擎使用该算法的原因。

完整版本

这个方程式引入了随机浏览者（random surfer）的概念，即假设某人在浏览器中随机打开某些页面并点击了某些链接。为了便于理解，这里假设上网者不断点击网页上的链接直到进入一个没有外部链接的网页，此时他会随机浏览其他的网页（可以与之前的网页无关）。

为了处理那些“没有外部链接的页面”（这些页面就像“黑洞”一样吞噬掉用户继续向下浏览的概率）所带来的问题，我们假设：这类页面链接到集合中所有的网页（不管它们是否相关），使得这类网页的PR值将被所有网页均分。对于这种残差概率（residual probability），我们引入阻尼系数d（damping factor），并声明d=0.85，其意义是：任意时刻，用户访问到某页面后继续访问下一个页面的概率，相对应的1-d=0.15则是用户停止点击，随机浏览新网页的概率。d的大小由一般上网者使用浏览器书签功能的频率的平均值估算得到。

所以，对于某个页面i，其对应PR值大小的计算公式如下：

这里，是目标页面， 是链入页面的集合， 是页面链出页面的数量，而是集合中所有页面的数量。

集合中所有页面的PR值可以由一个特殊的邻接矩阵的特征向量表示。这个特征向量R为：

同时，R也是下面的方程组的解：

这里的邻接函数（adjacency function） 代表“从页面j指向页面i的链接数”与“页面j中含有的外部链接总数”的比值

如果不链向，则前面提到的“从页面j指向页面i的链接数”为零。将情况一般化：对于特定的j，应有：

由于上述修改后的邻接矩阵的巨大的eigengap值，几次迭代后即可在极高的精确度下估计PageRank特征向量R的值。

算法中的几个问题

1、迭代初始值的确定

初始条件下，每个网页的级别可以一视同仁，由于每个页面的入度和出度不同，经过若干次迭代后得到的PR可以很好的 反应页面链入和链出的情况。根据Lawrence Page 和 Sergey Brin公开发表的文章，他们实际需要进行100次迭代才能得到 整个互联网的满意的网页级别值，他们还从理论上证明了不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛 到他们的真实值。在迭代的过程中，每个网页的网页级别的和是收敛于整个网络的页面数的，所以，每个页面的平均网页级别 是1。于是，可以将每个网页的初始PR定为1。阻尼系数一般设为0.85。

2、算法的时间复杂性

在互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数目平方之多个元素。如果我们假定有十亿个网页， 那么这个矩阵 就有一百亿亿个元素。这样大的矩阵相乘，计算量是非常大的。拉里和谢尔盖两人利用稀疏矩阵计算的技巧， 大大的简化了计算量，并实现了这个网页排名算法。今天 Google 的工程师把这个算法移植到并行的计算机中，进一步缩短了 计算时间，使网页更新的周期比以前短了许多。因此该算法的时间性能不是问题。

算法的特性：

• 页面的网页级别由链向它的页面的网页级别决定，但每个链入页面的贡献的值是不同的。如果页面中链出越多，它对当前页面的贡献就越小；而页面的链入页面越多，其网页级别就越高。
• 入链总是能增加当前页面的级别，尤其当前页与其下级页面构成回路时，这种贡献更大。
• 增加出链不会影响整个web的总级别，但一个站点失去的级别值等于链到的站点的增加值之和。
• 阻尼系数越大，页面级别的收益越大，且整个回路上都能收到更大的收益。
• 增加页面后，所有页面级别增加了1，但每个页面的级别值减少了，这是由于新加页面分享了入链代来的值。从这个结果看，增加页面减少了已有页面的级别值。当然，大站点也会因内容丰富而吸引其它站点的出链而得以级别值增加。

PageRank算法优缺点

优点：

• 是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间。

缺点：

• 人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低
• 旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接，除非它是某个站点的子站点。

算法的改进方法

1、主题敏感的PageRank（Topic-Sedsitive PageRank）

在这个算法中，我们需要预先计算离线时页面的重要性的分数；然后，我们为每一个页面计算多种重要性分数，即关于不同的主题来计算这个页面的重要性分数。在查询的时候，把这些重要性分数与根据被查询的主题的重要性分数综合在一起，就形成一个复合的PageRank分数。采用这种方法能形成更加精确的 排序 值，而不是原始普通的排序值。

2、二次方程推断法（Quadratic Extra polation）

这是一个可以加快PageRank的运算速度的方法。它能通过周期性的削减当前的矩阵乘幂迭代的非主要特征向量的方法，大大加快其收敛速度。使用这种方法计算PageRank值时，当计算一个包含8000万个节点的网络图时，与采用原来的PageRank 方法相比，计算速度可以提高20%-300%。

3、分块矩阵排序算法（BlockRank Algorithm）

该算法是PageRank算法的另一个加速算法，它首先把网络根据领域划分成不同的区域（块），为每个区域计算它们的 局部PageRank值；估计它们的相对的重要性（每个区域的BlockRank值）；用这个区域的Block-Rank.值来给每个区域 的Block-Rank赋予一定的权重。然后再把这些加权的局部的PageRank值近似地看作全局的PageRank向量，把这个向量 作为标准的PageRank算法的开始向量。这种方法可以减少计算的迭代次数，可以把更多的时间用于收敛速度慢的区域 的计算，提高了局部PageRank计算的有效性。BlockRank算法可以采取并行或分布的形式来进行计算，节约运算的时间。 此外，局部的PageRank计算结果在以后的计算中可以被再利用。

其它算法

Google PageRank并不是唯一的链接相关的排名算法，而是最为广泛使用的一种。其他算法还有：

• Hilltop 算法
• ExpertRank
• HITS
• TrustRank

PageRank 的代码实现

"""
Created on Sun Jan  8 23:41:29 2017
 
@author: whenif
"""
 
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
 
 
def getGm(A):
    '''
    功能：求状态转移概率矩阵Gm
    @A：网页链接图的邻接矩阵
    '''
    Gm = []
    for i in range(len(A)):
        cnt = 0
        for j in range(len(A[i])):
            if A[i][j] != 0:
                cnt += 1
        tran_prob = 1 / cnt  # 转移概率
        Gm_tmp = []
        for j in range(len(A[i])):
            Gm_tmp.append(tran_prob * A[i][j])
        Gm.append(Gm_tmp)
    Gm = np.transpose(Gm)
    return Gm
 
 
def getBaseLev(N):
    '''
    功能：计算网页所获得的基本级别(1-P)*e/n
    @N：网页总个数
    '''
    P = 0.85
    e = np.ones(N)
    R = [[(1 - P) * i * 1 / N] for i in e]
    return R
 
 
def getPR(P, Gm, R, PR):
    '''
    功能：获取PR值
    @P：加权系数，通常取 0.85 左右,按照超链接进行浏览的概率
    @Gm：状态转移概率矩阵
    @R：网页所获得的基本级别
    @PR：每个网页节点的PageRank值
    '''
    # 状态转移概率矩阵Gm与PR值相乘矩阵相乘
    Gm_PR = np.dot(Gm, PR)
    # 矩阵乘以常数P
    P_Gm_PR = P * Gm_PR
    # 矩阵相加
    new_PR = P_Gm_PR + R  # PR=P*Gm'PR+(1-d)*e/n PageRank算法的核心
    return new_PR
 
 
def res_vis(A, PR):
    '''
    将计算出来的值进行可视化展示
    @A：网页链接图的邻接矩阵
    @PR：每个网页节点最终的PageRank值
    '''
    # G=nx.Graph()构造的是无向图， G=nx.DiGraph()构造的是有向图
    # 初始化有向图，节点数为7,edge（边）被创造的随机概率
    all_edges = []
    for i in range(7):
        for j in range(len(A)):
            if A[i][j] == 1:
                all_edges.append([i + 1, j + 1])
                # （1）初始化有向图
    G = nx.DiGraph()
    # （2）添加节点
    G.add_nodes_from(range(1, len(A)))
    # （3）添加有向边
    G.add_edges_from(all_edges)
    # （4）添加PR值
    pr = {}
    for i in range(len(PR)):
        pr[i + 1] = PR[i][0]
    # (5)画图
    layout = nx.spring_layout(G)
    plt.figure(1)
    nx.draw(G, pos=layout, node_size=[x * 6000 for x in pr.values()],
            node_color='m', with_labels=True)
    plt.show()
 
 
def main():
    # 初始化参数
    N = 7  # 网页个数
    P = 0.85  # 一个加权系数，通常取 0.85 左右,按照超链接进行浏览的概率
    # 网页链接图的邻接矩阵，每一列表示一个网页的出度
    A = np.array([[0, 1, 1, 0, 1, 1, 0],
                  [1, 0, 1, 1, 0, 0, 0],
                  [1, 0, 0, 1, 1, 0, 0],
                  [1, 0, 0, 0, 1, 0, 0],
                  [1, 0, 0, 1, 0, 1, 1],
                  [0, 0, 0, 0, 1, 0, 0],
                  [1, 0, 0, 0, 0, 0, 0]])
    A = np.transpose(A)  # 转置
    # 初始化PR值为0
    new_PR = []
    for i in range(N):
        new_PR.append([0])
    count = 0  # 迭代计数器
    while True:
        PR = new_PR
        R = getBaseLev(N)
        Gm = getGm(A)
        new_PR = getPR(P, Gm, R, PR)
        count = count + 1
        print("第 %s 轮迭代" % count)
        print(str(round(new_PR[0][0], 5))
              + "\t" + str(round(new_PR[1][0], 5))
              + "\t" + str(round(new_PR[2][0], 5))
              + "\t" + str(round(new_PR[3][0], 5))
              + "\t" + str(round(new_PR[4][0], 5))
              + "\t" + str(round(new_PR[5][0], 5))
              + "\t" + str(round(new_PR[6][0], 5)))
        # 设置迭代条件
        if (round(PR[0][0], 5) == round(new_PR[0][0], 5)
                and round(PR[1][0], 5) == round(new_PR[1][0], 5)
                and round(PR[2][0], 5) == round(new_PR[2][0], 5)
                and round(PR[3][0], 5) == round(new_PR[3][0], 5)
                and round(PR[4][0], 5) == round(new_PR[4][0], 5)
                and round(PR[5][0], 5) == round(new_PR[5][0], 5)
                and round(PR[6][0], 5) == round(new_PR[6][0], 5)):
            break
    print("-------------------")
    print("PageRank值已计算完成")
    res_vis(A, new_PR)
 
 
if __name__ == '__main__':
    main()

参考链接：

• https://zh.wikipedia.org/wiki/PageRank
• https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.html
• https://segmentfault.com/a/1190000000711128
• https://www.jianshu.com/p/5657910d7df6