Realize the PageRank Algorithm i

Introduction

Background

PageRank是Google创始人Larry Page和Sergey Brin在1996年创造的算法，起源于他们在斯坦福的一个关于开发有效搜索引擎的项目。
他们把万维网(World Wide Web)看作是一个巨大的文件集，在这个集中，文件与文件间有着复杂的超链接结构。因此万维网也可以抽象成一个巨大的有向图，节点代表各网页，而有向边则代表网页之间的超链接。如何通过节点在图中的位置来计算逼近它对应的重要性，是PageRank算法的主要目的。
在详细讨论pageRank算法以前，需要先阐述一些有关的基础概念与定义。首先，如何把万维网抽象成一个有向图对PageRank算法至关重要。因为，万维网的link structure可以确定每个节点在整个网络中的相对位置，而这个相对位置则为后续计算它的重要性提供了信息。
我们用节点(vertex)来代表网页，有向边(edge)来代表网页间的链接关系。由于网页之间的链接边(或 link)有两个方向，因此分别命名为forward link(outedge) 和 backlink(inedge)。下图示意了一个，由5个网页组成的网络的link structure：

图1：W.W.W as a directed graph

Principle

基于万维网link structure的这个结构特性，PageRank算法的核心思想应运而生。
既然网页之间相互链接，那么对于一个网页而言，每一个指向它的链接(inedge)都可以类似成一个学术引用，代表了它的重要性。但是与学术引用不同，网页并没有质量控制和发表成本等门槛。因此，如果只单用inedge的数量来表示重要性的话，所得出的重要性指标会很容易被操控篡改。仅仅是靠低成本地制造大量垃圾网页，使它们指向某一特定网页，便可以增加此网页的引用数量。
基于这个考虑，除了使用引用数目(inedge的数目)这个局部指标以外，还应该使用万维网的全局信息。因为涉及万维网巨大的整体结构，这部分信息难以被简单篡改，使得计算出的重要性更为robust。
由观察得知，一个网页的重要与否，取决于以下两个因素：

• 与学术引用类似，此网页是否有许多入链接，即是否很多网页都指向它
• 指向它的网页中，是否存在非常重要的网页。例如：某网页也许只有一个入链接，但此入链接是源自Wiki这样的权威网页
  PageRank正是综合地考虑了网页的入链接数目这个局部指标，以及入链接网页重要性这个全局指标，来逼近一个网页的真实重要性。为了达到这一综合，此算法使用了重要性传递(rank propagation through links)这一思想，让rank依照万维网的结构动态流动直到稳定，所得的最终结果便是网页最后的重要性(或 Rank)。

PageRank Algorithm

basics

PageRank的定义

某一个网页
此网页对应的PageRank值(此公式算出的PageRank为naive版本)
归一化系数
指向网页u的网页集合

网页u指向的网页集合

图2

如上图中:

Matrix Representation

为了能够高效地计算网络里各个网页的PageRank，需要把上一节中公式表达成矩阵运算形式。
首先，假设网络中一共包含了N 个网页。设 R 为一个向量，一共包含 N 个entries，它的每个entry均存储了对应网页的PageRank值。
一个数组，负责存储每个网页的PageRank。
设一矩阵，它存储了网络任意两个网页间的链接关系。

例如下图三中的网络所对应的矩阵 A 为：

图3
https://goo.gl/images/4hnXVL
当随机浏览的用户进入这个子网络时，他将被困住，一直在这个网络的网页里循环。因此，这些网页的PageRank会趋近于无限大，而这个子网络之外的网页的PageRank会下降，造成失真。

Optimalization

一个有效的解决办法是额外加入一个Escape Term E(u)。它和R(u)一样，也是一个跳转概率分布，通过融合R(u) 和 Escape Term E(u)，死循环可以被打破。相当于，当用户陷入一个死循环时，Escape Term E(u) 提供了随机跳出此循环的可能性。融合方法如下：

Implementation in OpenMP

Motivation

此处，我使用OpenMP实现了PageRank的并行计算。
OpenMP是一个共享内存的并行计算模型，适用于多核的单节点并行。它支持多平台，计算中数据的分布与合成可以由 directives 自动处理，因此使用十分便捷，非常适合用来初步并行串行代码。

General Process

根据公式，计算PageRank的伪代码如下：

pseudo code
其中：
串行 vs. 并行
下图是 scaling factor，由于我的电脑只有四核，因此曲线的走势是合理的。
scaling factor

Analysis

由上面的分析可知，算法的 Speedup 非常不理想的。而这个性能的限制主要有两个因素 ：

• Load imbalance overheads(负载不均衡)

• Synchronization overheads(线程同步开销)

Load imbalance overheads

scheduling methods
上图展示了OpenMP的三种 scheduling methods：

• Static
• Dynamic

• Guided
  具体实现时，需要根据数据的具体分布来选择合适的scheduling methods，否则可能会降低算法的性能。
  首先，在原始的数据上检验不同的scheduling methods对性能的影响。结果如下：

  
  scheduling methods and performance
  

  可以看出，由于负载较为均衡，此时用chunk较小的Dynamic方法反而会增大调度开销，降低性能。
  然后，随机在原始网络上选出三个网页(节点)，每个网页手动添加一百万个随机入链接，增加网络的不均衡分布。当计算这个新的strewed数据时，每个iteration的计算量会严重不均衡。各个scheduling methods的运行时间如下：

  
  imbalance data
  可以看出，在计算量不均衡时，使用Dynamic更有优势，避免线程空闲。

Synchronization overheads

另一个影响性能的因素是代码的并行度。由于在实现这个算法时，为了避免data races ，在每个iteration中均用了atomic operation，造成了代码同步度的底下，降低了性能。
为了解决这个问题，可以先使每个iteration仅更新改变本地值，避免data races problem，在循环结束后做一个总的final synchronized reduction，以更新最终的全局共享变量。这个操作可以避免使用 atomic operation ，提高了代码的并行度。缺点是需要大量的内存来存放本地数据 ()。
改进的算法与旧算法的性能对比如下：

Summary

PageRank:

• numbers & importance of backlinks
• importance propagation:
  based on location in the graph structure

Implementation in OpenMP:

• Data race
• Load imbalance