皮盼资讯网移动版

在算法3-1中首先判断查询时间是否集中在时间轴后半部分，是则利用是先处理好的数据生成CSR-A(Line2~5)。之后不断将v添加到ope_array中(Line14)。如果time是目标时间则将ope_array按被指向节点(node2)进行排序，然后生成CSR-B。之后即可根据CSR-A和CSR-B进行PageRank的计算。

算法3-1 线性法PageRank

输入：Historical graph data v[4],half historical graph file h_hg_file,target time array t[]

输出： PageRank Value in every target time

1. initialize:int array ope_array[][4] /*四元组载体*/

2. if first target time >= half_time then

3. h_hg_file.rdbuf()

4. create CSR-A

5. end if

6. while True do

7. reload v

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

9. if time is one of target time then

10. sort(ope_array) by node2

11. create CSR-B

12. calPR(CSR-A,CSR-B)

13. end if

14. ope_array.append(v)

15. end while

在算法3-2中按照与算法2-2一样的方法初始化PR[](Line1)，之后开始迭代，对于每个点，收集其在CSR-A中的邻居，对PageRank值进行累加。再根据该点在CSR-B中的相关操作进行PR值的更新（Line5~6），如果是减边操作则要扣除之前多加上的值，而如果是加边操作则要加上对应的值。当某轮PR值与上一轮的差值小于设定阈值时结束迭代。

算法3-2 链表方法calPR

输入：CSR-A,CSR-B

输出： PageRank Value in the target time

1. initialize:float array PR[]

2. for i=0 up to max_interation do

3. change = 0

4. for node in nodes do

5. accumulate rank in CSR-A

6. update rank according to ope in CSR-B

7. rank += damping_value

8. change += |PR[node] - rank|

9. update PR[node] with rank

10. end for

11. if change < threshold then

12. break

13. end if

14.end for

15.return PR

5.3 Parallel Method

维护一个邻居集合来表示某个点出现过的邻居，同时维持一个bitset<query_count>结构来表示每个目标时间该邻居是否存在，所以如果需要表示所有边，就需要一个长度为边长，元素为bitset的数组bitset<query_count> nei_exist[edge_count]。假若在第二个目标时间中，CSR结构中边数组的第index个边存在，那么nei_exist[index][1] = 1，反之则为0。同时维护两个二维数组node_exist,以此来记录每个目标时刻中节点存在状态和出度的信息。比如在第二个目标时间中这样扫一遍数据之后就知道所有的信息。不同的计算模块凭借时间去遍历每个点的所有出现过的邻居，看看该时间对应的标志位上是否为1，为1表示该邻居该时刻存在，否则不存在。然后就可以计算每个点的PageRank值，以此达到并行的效果。

在算法4-1中，如果目标时间都集中在前半部分，那么我们只需读snapshot数据，否则我们需要读取全部数据(Line2~5)，这些文档都按照被指向节点排序过。之后根据存在v中的Δ数据来更新nei_exist，同时逐步建立CSR结构(Line7~12)。之后根据每个target time与nei_exist中相应的状态进行PageRank并行计算(Line13)。

算法4-1 并行法PageRank

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

输出： PageRank Value in every target time

1. initialize:bitset array nei_exist[]

2. if last target time < half_time then

3. read front part of the historical file

4. else

5. read whole part of the historical file

6. end if

7. while True do

8. reload v

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

10. update nei_exist

11. Build CSR

12.end while

13.calPR(nei_exist,all target time) in Parallel way

5.4 算法总结

Serial Method中使用的CSR结构则是利用两个数组来实现的，数组的物理存储是连续的，空间占用也较链表来得小，但是我们需要给出数组的长度，以至于其不会浪费空间也不会造成溢出。访问数组中的数据会快于链表。在整合构建CSR前需要对已有数据进行排序，时间复杂度为O(nlogn),之后计算PageRank值时访问数据只需要在CSR中访问即可，时间复杂度为O(1)。

Parallel Method中仅需要扫描一遍按时间及被指向结点排好序的数据，之后按照操作类型填入该边该时刻是否存在即可，该步骤时间复杂度为O(n)，a代表每个点平均。在计算某时刻PageRank值时候访问CSR结构，获取数据的时间复杂度都为O(1)，即可计算。

6 实验

6.1 实验设置

实验数据来自KONECT，内容纪录的是网页互相连接的Hyperlink networks，实验中不同大小的数据集都源自该数据集。

数据集中每行数据都是一个四元组(v1,v2,+/-,t)，表示在t时间增加或者删除v1指向v2的边。

表1展示了实验参数的设置，表2展示了每个数据集的特征。

实验在以下环境进行：

CPU：16 Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz，总核数：8

内存：231022144 kB，约220GB

操作系统：Linux

6.2 实验1：PageRank迭代轮次实验

6.2.1 实验说明