历史图上基于CSR结构的PageRank算法

摘要：

近年来,学者们对静态图的研究越来越全面、深入,已经形成了完善的理论体系.但是,对于生活中的一些应用问题,如社交网络中不断变化的关系等,使用静态图表示此类动态变化的关系似乎显得有些乏力.而历史图可以表示动态的变化.PageRank算法是用于衡量网页重要程度的算法,而网络中不断有网站新建或删除,这样的网络用历史图来表示更为合适,因此考虑在历史图上利用CSR(Compressed Sparse Row)结构实现PageRank,使得程序能够给出几个目标时间上各网站的评分,进而能够提供网站评分的变化情况,给出网站影响力趋势的预测.在Wekipedia提供的网页互相连接的Hyperlink networks数据集上,将所提方法与在链表上实现PageRank算法做比较,结果显示其性能大大优于使用链表的结构,并且随着数据规模和目标时间规模的增大,其优势将会越来越明显.

关键词：PageRank、CSR结构、历史图

所属期刊栏目：47

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金面上项目;国家自然科学基金重点项目

在线出版日期：2020-09-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：88-93