资源下载地址：https://download.csdn.net/download/sheziqiong/85601120
资源下载地址：https://download.csdn.net/download/sheziqiong/85601120
互联网时代带给人们生活最大的改变是，通过搜索引擎进行高效准确的 Web 搜索。尽管 Google 并不是最早的搜索引擎，但它却史无前例地成功解决了 Web 作弊问题。Google 搜索引擎的核心正是 PageRank 算法。
PageRank 算法，是 Google 的创始人拉里·佩奇和谢尔盖·布林于 1998 年在斯坦福大学发明了一种高效的链接分析方法。该算法基于一种假设：更重要的页面往往更多地被其他页面引用（或称其他页面中会更多地加入通向该页面的超链接）。PageRank 算法用于求解对搜索结果的网页排名，由于其高效性，它至今还在被各大搜索引擎使用。
本文主要进行 PageRank 算法的核心原理探讨以及实现优化。在实现算法基础功能的工作之上，引入随机游走因子，对于算法进行优化，从而解决 Web 数据中存在的 dead ends 和 spider traps 问题。此外，本文进一步实现了 PageRank 算法的 Block-Stripe Update 分块优化，以达到空间复杂度的优化。
关键词：PageRank 算法；链接分析；随机游走；Block-Stripe Update 分块优化
互联网时代，人们越来越依靠网络来获取知识。搜索引擎对于用户给出的查询，在海量 Web 网页寻找与查询匹配的内容，并在尽可能短的时间内给出用户反馈。用户通常关心搜索引擎搜索结果中的排名考前的结果，因此，在此需求下，搜索引擎需要对于海量 Web 数据进行质量分析。Google 公司的拉里·佩奇和谢尔盖·布林于 1998 年在斯坦福大学提出 PageRank 算法，通过对于 Web 网页间的链接分析，检索出其中与搜索相符的高质量网页，成功地解决了 Web 中广泛存在的垃圾页面和链接作弊的问题，极大地提高了搜索引擎的性能。
本次实验实现了 PageRank 算法基础功能，并在此之上通过随机游走算法解决了 dead ends 和 spider traps 问题，并通过 Block-Stripe Update 分块优化，保证了算法在大规模数据的情况下仍能有较高的性能。
本节将针对 PageRank 算法面对的核心问题以及解决方案给出算法分析。
搜索引擎根据用户的查询关键词，给出内容相关的 Web 页面。PageRank 算法通过 Web 页面之间的链接关系，建立相互投票的评分机制，通过计算页面最终的得分来衡量页面的质量。
具体来说，PageRank 让链接来” 投票”。一个页面的“得票数”由所有链向它的页面的权重（重要性）来决定，到一个页面的超链接相当于对该页投一票。一个页面的 PageRank 是由所有链向它的页面（“链入页面”）的权重经过递归算法得到的。一个有较多入链的页面会有较高的权重，反之则页面的权重较低。
朴素的 PageRank 算法在 Web 网页结构良好的环境下可以正常运行，通过迭代可以对不同的网页给出合理的打分。然而，研究表明，现实中的 Web 网页结构常常出现网页个体或网页群体没有出向链接，即网络中的 dead ends 和 spider trap。PageRank 算法经过迭代之后，全体系统的权重会被以上两种 Web 网页结构吸收，其余页面的权重会趋于 0，这使得计算得出的结果失去意义。
基于以上的问题，Google 对于朴素的 PageRank 算法提出改进策略。新的算法增加了随机游走因子，对于 Web 网页间的行为进行了更加细致的建模。朴素的 PageRank 认为网页之间的跳转只能通过彼此间的链接来实现；而加入随机游走因子后，算法认为用户会以一定概率随机打开任意一个网页，例如，用户直接在地址栏中输入某 Web 网页的网址。随机游走因子使得流入 dead ends 或 spider trap 中的权重能够以一定概率跳出该结构，保证系统的权重不会困于局部网页结构中，提高了算法的鲁棒性。
互联网的发展带来的是网络中页面的爆炸式增长，这导致在现实情景下，PageRank 算法的性能受到存储介质空间的限制。内存空间，甚至单台机器的硬盘存储空间，难以支持庞大的数据以及 PageRank 的复杂运算，因此，分块化的 PageRank 算法优化显得格外重要。
为了解决存储空间有限的问题，可以采用分块的思想。即把进行解耦合并分块处理。每个块内部先进行一次处理，之后把处理之后的结果，通过整合、处理，得到最终的结果。对于每一块，通常认为是单台计算机可以存储并且处理的，而最终的整合信息，也认为是单台计算机可以综合处理的。这样，就能使大规模数据集被多台计算机配合处理，从而得到最终结果。
工程领域中，常采用 MapReduce 分布式集群的模型架构。本文的实验方案中，对于输入数据进行了划分，使每部分数据适应运行环境的内存大小，已达到 PageRank 算法的分块化处理。
本节针对 PageRank 朴素算法、随机游走算法以及分块化算法给出公式定义。
朴素 PageRank 算法分析
本小节针对朴素 PageRank 算法给出分析。在理想的 Web 网页结构中，即不存在 dead ends 以及 spider trap 结构的前提下，PageRank 算法可以
可以概括为
如果一个网页被大量网页链接到，则该网页质量较高，拥有较高的
如果一个高 PageRank 权重的网页中包含一条链出至其他页面的链接，则被链接的网页会拥有较高的 PageRank 值。
基于以上的假设，利用“权重投票“的方式描述网页间的链接关系，并以此计算网页相应的 PageRank 权重。例如图 1 中的网络结构示意图，其中 i,j,k 表示 Web 中的三个网页，ri,rj,rk 分别表示网页的 PageRank 权重, 有向箭头表示网页间的链接。
每个网页的 PageRank 权重值由指向它的网页的 PageRank 权重值及这些网页的出度共同决定；同时这个网页的 PageRank 权重值及其出度又会影响它所指向的网页的 PageRank 权重值。由此，可以得出网页 j 的
PageRank 权重值 rj，其公式化定义为：
构建保存网页结点 PageRank 值的向量并初始化，r_new 代表当前时刻网页的 PageRank 值，r_old 代表上一时刻的 PageRank 值。
代码分析
本小节分析矩阵分块算法的实现。本次实验中，对于原始的数据文件按照参数 bloc_size 进行分块，并将划分后的数据分别成新的文件，以实现数据的分块。
本小节分析随机游走算法部分的实现代码。据公式 3 引入随机游走因子 β，利用矩阵乘法（公式 2）, 迭代计算 PageRank 值向量。
当迭代更新的误差小于阈值时，则认为算法收敛。
本节将从开发环境、实验设置、实验数据统计以及实验结果展示三个方面进行实验介绍与分析。
本小节将介绍本次实验所采用的环境。受限于实验条件条件，本次实验仅在本地运行，未使用云服务器及分布式架构。本地使用处理器为 Intel® Core™ i7-6700, 主频 3.40GHz；硬盘参数为 Samsung SSD 850 EVO 250GB 固态硬盘，理论读取速度 540MB/S，理论写入速度 520MB/S；RAM 空间为 16GB；未使用 GPU。
为保证实验的可复现性，本小节将介绍实验中部分参数的设置情况。参数 threshold 为控制算法收敛的阈值，当算法每轮迭代的更新量小于阈值时，
则算法以收敛；参数 β 为随机游走因子，控制算法随机游走的概率；参数 block_size 为分块优化算法中块的尺寸。具体参数取值见表 1。
表 1: 实验参数设置详情
针对本次实验使用的 Wiki 数据，进行了数据部分参数的统计，统计信息与实验结果可形成验证关系。统计详细信息见表 3
6.3.1 表 2: Wiki 数据集统计量详情
Wiki 数据集大小为 1070KB，约为 1MB，远小于运行环境下的内存容量。因此，对于矩阵分块算法，本实验假设数据规模过大，无法一次性装载入内存中。网页总数是 7115，假设使用邻接矩阵的形式来存储网页间的链接关系，共需要保存 71152 个矩阵项，占用内存大小为 71152 ×4 Byte = 193.11MB。统计网页间的链接数，共 103689 条，计算矩阵的非 0 项比例约为：0.020。由此可见，邻接矩阵相当稀疏。尽管使用邻接矩阵所占用的存储空间远小于运行环境中的内存空间，本实验还是优化稀疏矩阵的存储方式，以达到进一步节省空间开销的目的。
本小节展示算法运行的输出结果。在 PageRank 算法收敛后，选取权重值最大的前 100 个网页写入输出文件。如表所示的为排名在 1-5 以及排名在 96-100 位的部分网页编号以及 PageRank 数值。PageRank 值均保留 6 位小数。
6.4.1 表 3: Wiki 数据集统计参数详情
值得注意的是，根据 PageRank 权重排名最高的节点编号为 4037，对比 6.3 小节中 Wiki 数据集统计量信息，编号为 4037 的网页拥有最多的入向链接。换言之，被链接次数最多的网页拥有最高的权重，实验结果与
PageRank 算法的定义相符。
根据算法计算得到的 PageRank 值，可视化计算的结果。如图 4 右图所示，将网页映射至二维平面空间，散点的面积与 PageRank 值成正比。如图 4 左图所示，统计网页的 PageRank 值的取值范围，以及在权重范围内网页的数量。对比表 3 的统计信息，绝大多数的网页 PageRank 值较小，只有极个别的网页拥有较大的权重。绘制得到的统计柱状图符合“长尾”模型。
图 4: PageRank 统计信息可视化结果
本次实验聚焦于 PageRank 算法分析实现及其优化。在学习并分析了有关 PageRank 算法基础理论后，通过编程对于现实中的案例给出了一个相对原始的解。在此基础上，加入了对于网络结构恶劣情况下算法的改进，掌握了经典的随机游走算法。对于大规模数据，通过分块算法，对于数据进行处理，对于海量数据存储于预算给出了一个相对初级的解决方案。
在这次实验中，加深了对于链接分析与 PageRank 算法的认识，提升了对大规模数据集的处理能力。
互联网大规模数据挖掘与分布式处理（第二版） Jure Leskovec, Anand Rajaraman, Jeff Ullman
PageRank 算法：https://en.wikipedia.org/wiki/PageRank
通过分块算法，对于数据进行处理，对于海量数据存储于预算给出了一个相对初级的解决方案。
在这次实验中，加深了对于链接分析与 PageRank 算法的认识，提升了对大规模数据集的处理能力。