在本节中，我们将探讨PageRank算法，其实这是一个老生常谈的概念或者算法，在这里我们重新温故下这个经典算法。这是一种使用Web Graph中的链接结构按重要性对网页进行排名的方法，这也是Google普及的网络搜索常用算法。在讨论PageRank之前，让我们先将Web概念化为图，然后尝试使用图论语言来研究其结构。

将Web看做Graph

我们可以将万维网是将网页看成节点，网页之间的超链接看做成边组成的Graph，同时我们可以一下假设：

仅考虑静态网页忽略网络上的暗网（即无法访问的网页，防火墙保护的页面）所有链接都是可导航的。不考虑交易或者行为链接（例如：喜欢，购买，关注等）。

通过上述方式将万维网概念化为Graph之后，我们看看当前流行的搜索引擎如何使用它。例如，Google使用爬虫为网页编制索引，这些爬虫通过按广度优先遍历访问链接来浏览网络。可以通过这种方式遍历的图的还有很多其他例子，比如：科学研究论文之间的引文图，我们写论文的时候参考文献引用；百科全书中的参考文献。

万维网的Graph到底长什么样子

在2000年，AltaVista的创始人进行了一项实验[Graph structure in the Web - ScienceDirect]，以探索Web的形状。论文抛出了一个问题：给定一个节点,这个节点可以到达哪些节点；有哪些其他节点可以访问到这个节点？

这样会就产出两种类型的节点：

上面两个集合可以通过运行简单的BFS来遍历得到。例如，在下图中

有向图的更多细节

有向图有两种类型：

强连通图：任何节点都可以访问到任何其他节点的图。
有向无环图（DAG）：在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG, Directed Acyclic Graph）。

任何有向图都可以表示为这两种类型的组合，可以通过以下两个步骤实现：

获取有向图中的强连通图

将SCC合并到超节点中，创建一个新图形G’

PageRank

简介

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上。

公式

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

PR(A) 是页面A的PR值
PR(Ti)是页面Ti的PR值，在这里，页面Ti是指向A的所有页面中的某个页面
C(Ti)是页面Ti的出度，也就是Ti指向其他页面的边的个数
d 为阻尼系数，其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率，该数值是根据上网者使用浏览器书签的平均频率估算而得，通常d=0.85

还有一个版本的公式：

具体实例

为了便于计算，我们假设每个页面的PR初始值为1，d为0.5。

页面A的PR值计算如下：

页面B的PR值计算如下：

页面C的PR值计算如下：

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

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

代码实现

import numpy as np
from scipy.sparse import csc_matrix

def pageRank(G, s=.85, maxerr=.0001):
    """
    Computes the pagerank for each of the n states
    Parameters
    ----------
    G: matrix representing state transitions
       Gij is a binary value representing a transition from state i to j.
    s: probability of following a transition. 1-s probability of teleporting
       to another state.
    maxerr: if the sum of pageranks between iterations is bellow this we will
            have converged.
    """
    n = G.shape[0]

    # 将 G into 马尔科夫 A
    A = csc_matrix(G, dtype=np.float)
    rsums = np.array(A.sum(1))[:, 0]
    ri, ci = A.nonzero()
    A.data /= rsums[ri]

    sink = rsums == 0

    # 计算PR值，直到满足收敛条件
    ro, r = np.zeros(n), np.ones(n)
    while np.sum(np.abs(r - ro)) > maxerr:
        ro = r.copy()
        for i in range(0, n):
            Ai = np.array(A[:, i].todense())[:, 0]
            Di = sink / float(n)
            Ei = np.ones(n) / float(n)
            r[i] = ro.dot(Ai * s + Di * s + Ei * (1 - s))

    # 归一化
    return r / float(sum(r))


if __name__ == '__main__':
    # 上面的例子
    G = np.array([[0, 0, 1],
                  [1, 0, 0],
                  [1, 1, 0]])
    print(pageRank(G, s=0.85))

# 结果：
[0.51203622 0.19313191 0.29483187]