论文部分内容阅读
随着互联网和社交网络的发展，PageRank的地位日益凸显。网络规模的不断增大，同时网络变化带来的时效性要求，也使PageRank计算对计算资源的要求不断提高。为降低上述问题对计算资源的消耗水平，降低计算成本，本文提出了一种基于增量计算思想的并行PageRank算法:IncPR。IncPR基于蒙特卡罗方法，通过重用已有的结果，根据图的变化情况增量式地计算以得到正确的结果。相较于已有的PageRank算法，IncPR在保证结果精度的前提下，能有效地避免反复计算中的重复计算，从而显著降低计算量。IncPR的时间复杂度低且在计算过程中不引入额外的存储开销。 本文对IncPR的正确性进行了证明，在同等条件下IncPR计算得到的结果与基于蒙特卡罗方法的PageRank算法(BasicPR)计算得到的结果具有相同量级的精度水平。此外，理论分析得出当增加m个点和n条边时，IncPR的时间复杂度为O((cm+n)R/c2)（其中参数c和R分别代表蒙特卡罗方法的停止概率和启动次数）。通过分析比较发现，IncPR的时间复杂度优于已有的其它相关增量算法。 本文在基于BSP计算模型的Hama集群上的实验，验证了理论分析的结论。实验使用了来自于不同应用背景的真实数据集，以结果的相对误差的累积大小和算法发送消息的总量作为算法正确性和计算量的评价标准，针对不同的数据集的变化情况、变化规模、反复计算次数、初始结果精度等多种场景，对IncPR和BasicPR进行了实验。实验数据显示，当增加0.01％的边时，IncPR的计算量不足BasicPR的0.09％;当增加10％的边时，IncPR的计算量不足BasicPR的21％。通过相关实验可以得出结论，在得到与BasicPR同等（甚至更高）结果精度的情况下，IncPR显著地降低了计算量，且IncPR的计算量与增加的节点和边的规模大致呈线性关系。 综上，针对在大规模频繁变化的数据集上的计算PageRank的问题，本文提出的IncPR能够在不影响精度的情况下，有效地降低计算量，缩短计算时间。IncPR的计算方法还可以扩展到个性化PageRank、单元最短路径等其它基于随机游走的问题的增量算法的设计上。