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

CSR-based PageRank Algorithm on Historical Graphs

作　　者：潘培贤 邹兆年[1] 李发明[1] PAN Pei-xian;ZOU Zhao-nian;LI Fa-ming(School of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001,China)

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机科学》2020年第9期88-93,共6页Computer Science

基　　金：国家自然科学基金面上项目(61672189);国家自然科学基金重点项目(61532015)。

摘　　要：近年来,学者们对静态图的研究越来越全面、深入,已经形成了完善的理论体系。但是,对于生活中的一些应用问题,如社交网络中不断变化的关系等,使用静态图表示此类动态变化的关系似乎显得有些乏力。而历史图可以表示动态的变化。PageRank算法是用于衡量网页重要程度的算法,而网络中不断有网站新建或删除,这样的网络用历史图来表示更为合适,因此考虑在历史图上利用CSR(Compressed Sparse Row)结构实现PageRank,使得程序能够给出几个目标时间上各网站的评分,进而能够提供网站评分的变化情况,给出网站影响力趋势的预测。在Wekipedia提供的网页互相连接的Hyperlink networks数据集上,将所提方法与在链表上实现PageRank算法做比较,结果显示其性能大大优于使用链表的结构,并且随着数据规模和目标时间规模的增大,其优势将会越来越明显。In recent years,the research on static graphs has become more and more comprehensive and in-depth,and a perfect theoretical system has been formed.However,for some application issues in life,such as the changing relationships in social networks,it seems a bit weak to use static graphs to show that such moments are changing.Historical graph can be used to represent dynamic changes.The PageRank algorithm is an algorithm for measuring the importance of a web page,and there are constantly new or deleted websites in the network.Considering all these factors,such a network is quite appropriate to be represented by historical graphs.Therefore,this paper considers using the CSR(Compressed Sparse Row)structure to implement PageRank on the history graph,so that the program can give the scores of each website at several target times.In turn,it can provide changes in website ratings and give forecasts of website influence trends.Comparing its performance with the PageRank algorithm implemented on the linked list based on the hyperlinks network dataset provided by Wekipedia,the results show that its performance is much better than the use of linked list structure,and its advantages will become more and more obvious as the data size and target time scale increase.

关 键 词：PAGERANK CSR结构 历史图 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]