PageRank算法原理与实现

1.PageRank

1.1 简介

PageRank，又称网页排名、谷歌左侧排名，是一种由搜索引擎根据网页之间的相互的超链接计算的技术，而作为网页排名的要素之一，以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。
Google用他来体现网页的相关性和重要性，在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。

假设一个由4个网页组成的群体：A，B，C和D。如果所有页面都只链接至A，那么A的PR(PageRank)值将是B，C及D的PageRank总和。

重新假设B链接到A和C，C只链接到A，并且D链接到全部其他的3个页面。一个页面总共只有一票。所以B给A和C每个页面半票。以同样的逻辑，D投出的票只有三分之一算到了A的PageRank上。

1.2 公式

对于一个页面A，那么它的PR值为：

其中

• 是页面的PR值
• 是页面的PR值
• 是页面的出度，也就是指向其它页面的边的个数
• 为阻尼系数，其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率，该数值根据上网者使用浏览器书签的平均频率估算而得，通常。

还有一个版本的公式:

其中N为页面的总数。由于“没有向外链接的网页”传递出去的PR值会是0，而这会递归地导致指向它的页面的PR值的计算结果同样为零，所以赋给每个页面一个最小值。

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

用矩阵形式表示，则：

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

1.3 具体实例

三个页面A、B、C
为了便于计算，我们假设每个页面的PR初始值为1，d为0.5

• 页面A的PR值计算如下：
  
• 页面B的PR值计算如下：
  
• 页面C的PR值计算如下：
  

下面是迭代12轮之后，各个页面的PR值：

那么什么时候，迭代结束哪？一般要设置收敛条件：比如上次迭代结果与本次迭代结果小于某个误差，我们结束程序运行；比如还可以设置最大循环次数。

2. 算法中的几个问题

2.1 迭代初始值的确定

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

2.2 算法的时间复杂性

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

2.3 算法的特性：

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

2.4 PageRank算法优缺点

优点：

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

缺点：

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

2.5 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

3. 代码实现

#!/usr/bin/env python
# coding: utf-8

# In[7]:


import numpy as np
import networkx as nx
import matplotlib.pyplot as plt


# In[8]:


def getGm(A):
    '''
    求状态转移概率矩阵Gm
    :param A: 网页链接图的邻接矩阵
    :return:
    '''
    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


# In[9]:


def getBaseLev(N):
    '''
    计算网页所获得的基本级别(1-P)*e/n
    :param N: 网页总个数
    :return:
    '''
    P = 0.85
    e = np.ones(N)
    R = [[(1-P) * i * 1 /N]for i in e]
    return R


# In[10]:


def getPR(P,Gm,R,PR):
    '''
    获取PR值
    :param P: 加权系数，即阻尼系数，通常取0.85左右，按照超链接进行浏览的概率
    :param Gm: 状态转移概率矩阵, [N,N]
    :param R: 网页所获得的基本级别 [N,1]
    :param PR: 每个网页的PageRank值 [N,1]
    :return:
    '''
    # 状态转移概率矩阵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


# In[11]:


def res_vis(A,PR):
    '''
    将计算结果可视化展示
    :param A: 网页链接图的邻接矩阵
    :param PR: 每个网页节点最终的PageRank值
    :return:
    '''
    # 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)
    # 节点大小由节点PR值给出，反映节点重要性
    nx.draw(G, pos = layout,node_size =[x*6000 for x in pr.values()],node_color='m',with_labels=True)
    plt.show()


# In[12]:


def main():
    # 初始化参数
    N = 7 # 网页个数
    P = 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
• PageRank算法原理与实现