皮盼资讯网移动版

我们知道PageRank值需要通过多次迭代才能达到收敛，我们意在探寻不同大小的图的收敛轮次之间存在的一些关系以及同一个数据集迭代的轮次和计算收敛的阈值之间的变换关系。

我们对于每个数据集，控制其计算阈值，记录不同阈值下的迭代轮次，以阈值为横轴，迭代轮次为纵轴作图。实验结果如图3-1所示。

6.2.2 实验分析

从图中可以看出，随着阈值的增大，迭代轮次全部表现为下降趋势，即阈值越小，所需迭代轮次越大；阈值越大，所需迭代轮次越小。

另外，普遍来说，数据集越大，对于相同的阈值所需的迭代次数越大，但是也存在不同数据集在相同阈值下迭代轮次相同或者小的数据集迭代轮次大于大的数据集的情况。

我们可以得出普遍的结论：阈值越大，数据集越大，所需的迭代轮次也就越大。

6.3 实验2：多参数的性能测试

6.3.1 实验说明

实验测试上述三个方法随着查询量增大而发生的改变。其中可变的参数包含查询位置、查询跨度。查询位置的前后分别代表着查询集中在时间轴的前半部分和后半部分，这样表示两种情况，分别是查询均匀分布在时间轴前半部分和后半部分。

6.3.2 实验数据图

6.3.3 实验分析

由图3-2可以看出一般来说计算的查询时间集中在后半部分的时候计算时间会比集中在前半部分的多，因为需要读取snapshot数据的原因。

另外，无论数据大小、查询位置是什么参数，计算时间会随着问询量的增大而增大，而且，根据图中的线条来看，查询时间和查询的数量是呈线性关系。

整体来看，使用其他两个使用CSR结构的方法会比使用链表的来得快些。其中LinkedList Method大大快于链表，而Parallel Method在准备数据过程中可能有所耗时，但是后续计算可以并行进行，也会对效率有所提高。

6.4 实验3：单次问询性能测试

6.4.1 实验说明

之前的测试是在不同跨度，不同问询量的情况下进行测试的。而我们测试的时间是诸多个问询量总共的计算时间，我们也只能得到计算每个问询的平均时间，而无法获知这些在时间戳轴上不同位置的问询所需时间的不同。

为了更加直观的获知数据集大小和查询时间的关系，我们针对不同数据集，只问询其最大时间戳处的PageRank值，以此来获得他们之间的关系。实验结果如图3-3-1所示。

另外，为了探究整个过程的时间主要耗费在什么地方，实验统计了三个方法在不同数据集下准备数据时间与总时间的比（总时间包括准备数据时间和计算时间）。实验详情如图3-3-2所示。

6.4.2 实验分析

从实验图3-3-1中可以看出随着数据集的不断增大，使用链表来解决问题的时间将会急剧增加，而使用CSR结构来解决问题的Serial Method、Parallel Method则表现出平稳的态势，二者性能大大优于使用链表的方法。

从实验图3-3-2中可以看出，链表方法的大部分时间都花费在准备数据上，也就是对图结构的维护操作中。在准备数据上，LinkedList Method花费了总时间的90%左右，而Serial Method也花费了75%左右，Parallel Method花费40%左右。由此我们可以得出，计算部分的时间并不是总耗时的决定因素，如何能高效地维护更新数据才是提高效率的关键。

结束语