皮盼资讯网移动版

这个简化的排名函数有个小问题。考虑存在只有链入而无链出的节点，那么，在迭代时，这个循环会不断积累权重，而从来不发出权重。对于这样没有出度的网页，设置其对所有网页都有出度。

PageRank迭代计算过程可以表示为算法一

算法1 PageRank算法

输入： Graph G

输出： PageRank Value

1.Initialize:float array PR[]

2.for i=1 up to max_interation do

3. change = 0

4. for node ∈ G.nodes() do

5. PR(node) = ∑_(v∈G.nodes)?(PR(v))/Nv

6. PR(node) += (1-c)/N

7. change += |〖PR〗_old-〖PR〗_new| /*累计该轮与上轮差值*/

8. end for

9. if change < threshold then

10. break

11. end if

12. end for

然而PageRank却忽视了主题性和相关性。例如“苹果”一次对于不同主题就蕴含不同的意思。因此就产生了个性化的PageRank[14]与主题敏感的PageRank[15]来弥补这些问题。如果将PageRank和IF-TDF结合起来[16]能够基于文档内容与用户查询的相似性对文档进行排名。同时，PageRank也可以应用到电力系统[17]和军事通信系统中 [18] 。

3 历史图

历史图数据，又可以称为临时图数据(temporal graph)、动态图数据(dynamic graph)。其顶点可表示某个实体对象，例如网页、通信双方等。其边可表示为对象的关系。图的边或者点上存在时间戳，表示边或者点出现或消失的时间。

历史图结构会随时间的变化而变化，其动态性主要表现为点和边的不确定性。

历史图数据由诸多个Δ构成，每个Δ可以看做一个四元组(v1,v2,operation,timestamp)，分别表示节点1、节点2、操作类型(增\减)和时间戳，一下算法用到的四元组数据就是如此结构。

在做历史图相关的计算时，为了避免目标时间距离开始时间过长，我们在线下保存一个整体中部的快照(如图1)，用以表示该时刻的图结构,如果查询时间大于snapshot的时间，那么我们直接读取snapshot的内容即可获得整个时间线半程时的状态。

4 CSR结构

4.1 结构介绍

CSR结构是一种用两个数组表示图数据的数据结构。一个数组（点数组）记录每个点的邻居在另一个数组（边数组）中的位置，边数组就用于存放邻居的编号。如此就可以根据两个数组中的内容还原图中的所有数据。

4.2 结构特点与优势

在空间方面，链表的每个元素包含两个部分，一个部分是存储的数据，另一个部分是指向下一个结点地址的指针，因此用于表示图的时候需要多占用m个指针所需要的空间(m表示边的数目)。而使用CSR结构只需要m+n个int型的空间即可表示同样的图(n表示点的数目)。因此，CSR结构更加省空间。

在时间方面，由于数组的元素在内存空间中是连续存放，而链表存放的空间可以是连续的，也可以是不连续的，因此在遍历数据获取图信息的时候，CSR结构会比链表更快。同时，在处理边的删除操作时，链表需要进行查找、删除、重新指向的操作，比较费时。

5 使用CSR结构实现PageRank

5.1 LinkedList Method

使用最直观的链表维护一个图，对每个delta操作，如果是加边，则到对应的点指向的链表处加上新邻居节点，如果是减边，则在该点的邻居链表中找到对应邻居，删除节点后连接两端。在遇到需要计算PageRank的时间点时，根据当前的图，可以获取所需要的所有信息（节点数目、终止点数目、节点邻居等），然后调用PageRank函数进行计算。

在算法2-1中，首先获取历史图的四元组v(Line2~3)，对于增/减操作进行不同的处理(Line7~11)，如果碰到目标时间则将目标时间的所有操作完成后进行计算PageRank值的操作(3~6)

算法2-1 链表方法

输入：Historical graph data v[4],target time array t[]

输出： PageRank Value in every target time

1. while True do

2. reload v /*读取四元组数据*/

3. node1,node2,ope,time←v[0],v[1],v[2],v[3]

4. if time is one of target times then

5. calPR() /*计算PageRank值*/

6. end if

7. if ope=1 then

8. addNode(node1,node2) /*添边*/

9. else

10. deleteNode(node1,node2) /*减边*/

11. end if

12.end while

5.2 Serial Method

对于CSR结构，最直观的想法是按照时间顺序进行计算。如图2所示，在snapshot处存在一个CSR结构来保存快照（CSR-A，如图2-1），同时将区域A的所有delta按照入射节点排序后生成另一个CSR结构（CSR-B，如图2-2）。相比CSR-A，CSR-B中还存储的增减操作。计算PageRank时，对于点A，从CSR-A中获取邻居（B、C、D），计算PageRank。然后访问CSR-B，补充区域A的操作带来的改变，如果CSR-B中B指向A的边被删除，就说明之前我们多累加了一个值，那么这时候减去即可。以此类推其他点。