任务：论文（格式参考“中国科学报”）->“基于MapReduce方法的PageRank算法实现”
本文内容：探讨研究学习PageRank相关知识并编码实现，拓展至MapReduce方法概念以及实现原理，但是并不进行实现，因为博主的hadoop环境没有配，如果想要模拟较为真实的搜索引擎，不用hadoop跑跑足够大的数据，没啥意思，所以在下篇博文里进行实现。

一、什么是PageRank

直白的翻译来讲就是：页面排名。当然也有说法是Page指代Larry Page（google的产品经理及CEO），因为他是这个算法的创造者之一。那么我们为什么需要页面排名？这得从搜索引擎的发展讲起。早的搜索引擎采用的是 分类目录的方法，即通过人工进行网页分类并整理出高质量的网站。那时 Yahoo 和国内的 hao123 就是使用的这种方法。
后来网页越来越多，人工分类已经不现实了。搜索引擎进入了文本检索的时代，即计算用户查询关键词与网页内容的相关程度来返回搜索结果。这种方法突破了数量的限制，但是搜索结果不是很好。因为总有某些网页来回地倒腾某些关键词使自己的搜索排名靠前（想要实现这样的目的，其实很容易，我们会在下面的内容里学习到）。
需求总是在不停的催动发展。于是谷歌的两位创始人，当时还是美国斯坦福大学 (Stanford University) 研究生的佩奇 (Larry Page) 和布林 (Sergey Brin) 开始了对网页排序问题的研究。他们的借鉴了学术界评判学术论文重要性的通用方法， 那就是看论文的引用次数，由此想到网页的重要性也可以根据这种方法来评价，于是PageRank的核心思想就诞生了。不要觉得PageRank这个作为google的核心算法多么的高大上，其实道理很好理解：

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

下面这张抽象的节点图就可以说明问题了：

image.png

（这块在论文里体现时图要更换！所以的图都要更换）

这张节点关系图可以看作是网页链接抽象图（其实大同小异），从图中可以看到，C网站可以被A、C、D三个网站所链接到，当然我们可以大胆的推测，C的重要性一定是最高的，同样PageRank值（及PR值）也是最高的。我图中给的这个例子有点特殊，因为他在下面的内容里还会被引用，所以就直接用这张图说明问题了（特殊在哪里应该可以看出来）。在这里我们还引出了PageRank中一个很重要的测量指标：PR值。我们想象这样一个情景，一个悠闲的上网者在随意的浏览着一些网站，当打开某一网站并在该网站上停留了几分钟后，跳转到该网页所指向的链接，这样漫无目的的在一些网页上跳来跳去，而PR值就是估计这个悠闲的上网者分布在各个网页的概率。所以我们需要明确的一点是，PR值是在“不断”变化着的，但是神奇的是，这个本该“不断”变化的值会在一定回合时期后收敛稳定。

二、算法原理

下面我们所有的原理都是围绕上网者浏览网页这个易于理解的例子来说明的。

1、初始化PR值向量

首先PageRank算法会给每个网页设置一个初始值，初始值为：

PR = 1/L #L为网页的总数量

一般来说所有网页的PR值总和应该为1，这个很好理解，如果我们要以概率进行讨论的话，理应如此。但是有的时候不为1也不是不行，最后所得到的网页之间的PR值的大小关系仍然正确，只是不可以直观地反映概率。

2、转移矩阵以及迭代

从上文我们可以知道， 当上网者随意地进入网站时，PR值矩阵会随之改变。而改变后的PR值矩阵便是上一状态的PR值矩阵*转移矩阵：

PR_now  = PR_pre * M  # M为转移矩阵

M转移矩阵的定义：当一个网站有N个链接时，这个网站对其他各个网站的PR贡献值为1/N，而各个网站的PR值为各个指向自己的PR贡献值之和。即：

PR_i_commit = PR_i / l_i # l_i为第i个网站的出链数
PR_i = PR_1_commit + PR_2_commit + PR_3_commit + ... + PR_n_commit # n=网站入链数

所以M概率矩阵为Pr_i_coomit的矩阵表示形式。看下面这个例子（又是它。）

image.png

我们可以按照上面的方法写出M矩阵的值：

image.png

刚才我们所作的初始化PR值的目的为假设上网者等概率的浏览已有的网站，下面的我们的上网者开始他第一次的上网体验，我们可以由概率矩阵和初始值向量得到该上网者第一步之后的概率分布：

image.png

这里我们需要注意的是，概率矩阵M是不变的，M只与网站的链接情况相关，而与过程无关。我们尝试迭代30次、50次、100次，可以发现PR值稳定不变了：

image.png

3、算法存在的问题以及相应的解决方法

Q1：终止点问题

该问题的产生是由于某个网站节点并没有指向别的网站的链接了，也就是死胡同。如下图：

image.png

由图中可以看到，网页C没有任何链接到其他网页的出链，故该网页节点是个死胡同。
同样，我们按照上面的方法可以写出他的概率矩阵：

image.png

但是有趣的是，当我们进行了30次或以上迭代后(其实不用这么多次)，所有的PR值都为0了。有点线性代数基础的同学很快就可以反应过来这个矩阵乘法的问题。映射到我们的实际场景下：当我们的上网者进入该网站时，发现该网站没有其他网站连接选项或者被该网站的一些小把戏糊弄住了，他会怎么做呢？会傻乎乎的一直呆在该网站吗？当然不会。按照绝大数人的正常行为习惯，会在地址栏中随机输入一个其他的URL进行访问，而不是就跟这个"死胡同"网站去较劲。那么我们的解决方法也就应运而生了：

A1：给死胡同网站加出链

既然该网站没有出链会影响算法最后的输出结果，那么我们就模拟人的正常思维方式，给这个网站节点等概率的设置出链，出链的目标为所有网站包括其本身。如下图

image.png

那么在修改后的节点图中，此时B节点的PR值为：

PR_B = PR_A/3  + PR_D/2 + PR_C/4 

Q2：陷阱问题

这个问题，正好对应文章开头所埋下的伏笔问题，不得不佩服这个漏洞的创造者们，通过审计PageRank算法的缺陷，来达到自己排名上升的目的。这个问题的原因是如何产生的呢？如下图：

image.png

这张图是我们的老朋友了。他的特殊之处相信大家也能够一眼看出来，网页C只有对自己的出链，或者另外一种情况：几个网页的出链形成一个循环圈。那么
设想这样一个网站，它并没有任何指向其他网站的链接，但是它却有指向自己本网站的链接，当我们的上网者进入该网站，停留片刻后想要离开，于是点击了指向该网站的链接，又回到了该网站。如果是一个爱较真一根筋的上网者，他会一直驻留在该网站，久久不能释怀。然而算法一定是面向广大正常的使用者的，所以为了避免这样的问题的产生，又一个十分牛逼的想法诞生了（听老师介绍，是个本科生想出来的？）

A2：增加随即跳转

我们假定上网者不会与陷阱网站较真，并给定一个确定的概率值来表示该上网者会按照一定的概率随机跳转到另外的一个网页，并且跳转到每个网页的概率相同。即：

image.png

（图需要修改）

该确定的概率值一般为0.85，至于为什么，肯定是基于大量的实验数据证明，在概率值为0.85时，可以达到最佳的效果。
当然，迭代30次或更多次数之后，PR值也会收敛稳定。
最终结合以上对两个问题的解决方方法，得出最终的迭代公式：

image.png

拓展来看：

image.png

以上这两种针对不同问题的解决办法的共同思路相信大家都很明白——充分考虑并模拟上网者的思维方式， 关于这个话题我想在文末进行阐述，因为这也是我近期很感兴趣的一个话题。

三、PageRank算法合理性证明

证明该算法的合理性，其实可以拆分为两个子证明问题：

1、当n->∞时，Pn是否存在
2、如果Pn存在，是否与P0无关

在理解这两个子证明问题的时候，还是需要结合上网者的实际例子来分析。
首先证明第一个子问题：
还是以矩阵的形式表示各个网站节点的出入链关系：（这里随便定义一个S矩阵）

image.png
取e为所有分量都为 1 的列向量,接着定义矩阵：
image.png
则PR值的计算如下，其中Pn为第n次迭代时各网页PR值组成的列向量：
image.png
于是计算PR值的过程就变成了一个 Markov 过程，那么PageRank算法的证明也就转为证明 Markov 过程的收敛性证明：如果这个 Markov 过程收敛，那么Pn存在且与P0无关。
若一个Markov过程收敛，那么它的状态转移矩阵A需要满足：

1、A为随机矩阵
2、A是不可约的
3、A是非周期的

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

image.png

显然我们的A矩阵所有元素都大于等于0，并且每一列的元素和都为1。
第二点，不可约矩阵：方针A是不可约的当且仅当与A对应的有向图是强联通的。有向图G=(V,E)是强联通的当且仅当对每一对节点对u,v∈V，存在从u到v的路径。因为我们在之前设定上网者在浏览页面的时候有确定概率通过输入网址的方式访问一个随机网页，也就是说上网者在任一时刻都有机会访问任一网站，所以A矩阵同样满足不可约的要求。
第三点，要求A是非周期的。所谓周期性，体现在Markov链的周期性上。即若A是周期性的，那么这个Markov链的状态就是周期性变化的。因为A是素矩阵（素矩阵指自身的某个次幂为正矩阵的矩阵），所以A是非周期的。
至此，我们证明了PageRank算法的合理性与正确性。

四、PR值的计算方式

1、幂迭代法

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

|Pn+1−Pn|<ϵ

2、特征值法

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

3、代数法

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

image.png

又因为e为所有分量都为1的列向量，P的所有分量之和为1，所以：

image.png

五、利用MapReduce方法计算PageRank

在上面我们所讨论的问题，都是给出了十分简单的矩阵相乘情况，然而对于一个十分庞大的web结构来说，这样简单粗暴的迭代方式显然不行，原因很简单，计算机根本放不下这么大的矩阵。目前的网页数量没有几万亿也有几千亿，那么转移矩阵就是几万亿*几万亿的矩阵，显然是不切实际的。这时候我们就需要借助MapReduce的计算方法来解决这么庞大的数据处理问题。
MapReduce其实分为两个阶段：Map阶段和Reduce阶段。其实也就是两种操作：
Mapping和Reducing。

映射（Mapping）：对集合里的每个目标应用同一个操作。
化简（Reducing ）：遍历Mapping返回的集合中的元素来返回一个综合的结果

就拿一个最经典的例子来说：现在有3个文本文件，需要统计出所有出现过的词的词频。传统的想法是让一个人顺序阅读这3个文件，每遇到一个单词，就看之前有没有遇到过。遇到过的话词频加一：（单词，N + 1），否则就记录新词，词频为一：（单词，1）。
MapReduce方式为：把这3个文件分给3个人，每个人阅读一份文件。每当遇到一个单词，就记录这个单词：（单词，1）（不管之前有没有遇到过这个单词，也就是说可能出现多个相同单词的记录）。之后将再派一个人把相同单词的记录相加，即可得到最终结果。

映射到我们所考虑的情景下，利用一个很简单的例子来说明MapReduce算法的实现：
考虑转移矩阵是一个很多的稀疏矩阵，我们可以用稀疏矩阵的形式表示，我们把web图中的每一个网页及其链出的网页作为一行，这样第四节中的web图结构用如下方式表示：

1 A    B    C    D
2 B    A    D
3 C    C
4 D    B    C

A有三条出链，分别指向B、C、D，实际上，我们爬取的网页结构数据就是这样的。

1、Map阶段
　　Map操作的每一行，对所有出链发射当前网页概率值的1/k，k是当前网页的出链数，比如对第一行输出<B，1/31/4>,<C，1/31/4>,<D，1/3*1/4>;
2、Reduce阶段
　　Reduce操作收集网页id相同的值，累加并按权重计算:

pj=a*(p1+p2+...Pm)+(1-a)*1/n，其中m是指向网页j的网页j数，n所有网页数。

思路就是这么简单，但是实践的时候，怎样在Map阶段知道当前行网页的概率值，需要一个单独的文件专门保存上一轮的概率分布值，先进行一次排序，让出链行与概率值按网页id出现在同一Mapper里面，整个流程如下：
（这张图的第二个Map阶段的输出结果有点问题，在D节点那块少了两个值，不过还是要赞一下这张图的作者）

image.png

这样进行一次迭代相当于需要两次MapReduce，但第一次的MapReduce只是简单的排序，不需要任何操作。

六、PageRank算法代码

两种差别不大的代码实现：

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)

import numpy as np

class CPageRank(object):
    '''实现PageRank Alogrithm
    '''

    def __init__(self):
        self.PR = []  # PageRank值

    def GetPR(self, IOS, alpha, max_itrs, min_delta):
        '''幂迭代方法求PR值
        :param IOS       表示网页出链入链关系的矩阵,是一个左出链矩阵
        :param alpha     阻尼系数α，一般alpha取值0.85
        :param max_itrs  最大迭代次数
        :param min_delta 停止迭代的阈值
        '''
        # IOS左出链矩阵, a阻尼系数alpha, N网页总数
        N = np.shape(IOS)[0]
        # 所有分量都为1的列向量
        e = np.ones(shape=(N, 1))
        # 计算网页出链个数统计
        L = [np.count_nonzero(e) for e in IOS.T]
        # 计算网页PR贡献矩阵helpS，是一个左贡献矩阵
        helps_efunc = lambda ios, l: ios / l
        helps_func = np.frompyfunc(helps_efunc, 2, 1)
        helpS = helps_func(IOS, L)
        # P[n+1] = AP[n]中的矩阵A
        A = alpha * helpS + ((1 - alpha) / N) * np.dot(e, e.T)
        print('左出链矩阵:\n', IOS)
        print('左PR值贡献概率矩阵:\n', helpS)
        # 幂迭代法求PR值
        for i in range(max_itrs):
            if 0 == np.shape(self.PR)[0]:  # 使用1.0/N初始化PR值表
                self.PR = np.full(shape=(N, 1), fill_value=1.0 / N)
                print('初始化的PR值表:', self.PR)
            # 使用PR[n+1] = APR[n]递推公式，求PR[n+1]
            old_PR = self.PR
            self.PR = np.dot(A, self.PR)
            # 如果所有网页PR值的前后误差 都小于 自定义的误差阈值，则停止迭代
            D = np.array([old - new for old, new in zip(old_PR, self.PR)])
            ret = [e < min_delta for e in D]
            if ret.count(True) == N:
                print('迭代次数:%d, succeed PR:\n' % (i + 1), self.PR)
                break
        return self.PR


def CPageRank_manual():
    # 表示网页之间的出入链的关系矩阵，是一个左关系矩阵，可以理解成右入链矩阵
    # IOS[i, j]表示网页j对网页i有出链
    IOS = np.array([[0, 0, 0, 0, 1],
                    [1, 0, 0, 0, 0],
                    [1, 0, 0, 0, 0],
                    [1, 1, 0, 0, 0],
                    [0, 1, 1, 1, 0]], dtype=float)
    pg = CPageRank()
    ret = pg.GetPR(IOS, alpha=0.85, max_itrs=100, min_delta=0.0001)
    print('最终的PR值:\n', ret)


if __name__ == '__main__':
    CPageRank_manual()

六、参考文献

https://www.cnblogs.com/rubinorth/p/5799848.html
https://blog.csdn.net/sz457763638/article/details/75360652
https://blog.csdn.net/rubinorth/article/details/52215036
https://blog.csdn.net/Sakura55/article/details/80958340
https://blog.csdn.net/u012421852/article/details/80324232?utm_medium=distribute.pc_relevant.none-task-blog-title-1&spm=1001.2101.3001.4242
https://blog.csdn.net/tiankong_/article/details/77431515
https://blog.csdn.net/qq_35078688/article/details/83240661
https://wizardforcel.gitbooks.io/dm-algo-top10/content/pagerank.html

七、个人感悟

首先需要感谢以上参考文献的作者或博主给我带来的启发，文中也有很多地方引用以上参考文献的内容，还望多多包涵一下。
下面的学习便是围绕着算法去实现、改进、分析结果，最终编辑内容再加上之前的内容一起形成论文报告。
下面所说的内容仅代表个人观点，与知识无关。
在老师布置这份作业之前，我就已经了解过google包括百度这些知名的搜索引擎的实现算法，当然，算法本身的价值是毋庸置疑的，搜索引擎的诞生无疑是给人们的生活带了巨大的变化与收益，也推动了整个互联网的发展。就大部分的上网者来说，所需求的无疑是浏览到自己喜欢的网站，获取到自己需要的信息，这也是搜索引擎的算法所在苦苦追求的目标：迎合大众的喜好。不单单是搜索引擎，包括某宝、某音等软件，他们的核心算法也是在考虑个人喜好，并且把这些当做优化的目标。例子不用我多说，仔细细心想想也不难发现。我们先从一个比较专业的角度来考虑这个问题，对于大多数软件而言，作为用户身份的同时我们也在参与软件的优化，我们靠什么参与优化？信息。我们每个人在体验的同时，会产生很多信息，例如：喜好、职业、甚至是未来的安排计划等。这些信息会辅助算法对个人的体验进行优化。我们给予的信息量、数据量越多，算法本身就越体现其优势。我们都知道，搜索引擎无疑就是巨大的数据库+强大的爬虫。两者都扮演着缺一不可的角色。那么在上面所说的内容里，是否存在信息、隐私泄露的问题？当然信息系统的漏洞另说，这里所假设的是不存在外在安全隐患的情况。这里所指的信息也不是很具象的信息，例如：手机号、身份证号这些，而是你的兴趣爱好、未来期望、个人追求等。在前面的文中，我们会发现，PageRank算法在发展的过程会出现很多问题，而这些问题的解决方案都是在模拟正常人的行为和思维习惯解决的，并且解决效果十分的出色。在肯定算法可行性的同时，我们需要去思考，这样的算法是否会使我们走向极端呢？这里的极端不是指上文中的“死胡同”网页节点。而是我们思维方式的极端以及独立思考能力的极端。现在很流行一句话，你眼中的网络世界其实是你想要看到的世界，而不是真实的世界。富人每天所推送的永远都是奢侈品、名流圈，相对而言的普通人所推送往往都是找工作上58、相亲就去百合网等等。慢慢地，你会发现，每个人的思想维度会因为网络被牢牢限制住。譬如发生在我身边很小的一件事情，篮球巨星科比的意外逝世给我们爱好篮球的人带来了极大的冲击，当天早上我醒来后，所有关于科比意外逝世的推送占满了整个手机屏幕，而当我却在我们宿舍群里看见舍友在讨论同一时间发生的另外的一件事（舍友都不打篮球），当我把新闻转发到群里时，得到的反馈竟然是：
“绝对是假新闻。”
“现在为了点热度，说谎都不打草稿”
“科比是打篮球的科比吗？”
“科比开飞机？？”
这件事情本身没有对错，我上面所提到的所有观点都没有对错可言，我想说的是，我们需要有独立思考问题的能力，而不是被网络左右我们的观点，道理其实大家也都懂，只是，我们有的时候真的太容易陷入到获取信息的快感中了。