皮盼资讯网移动版

本文在历史图的数据上进行PageRank问题的相关计算，介绍了历史图的基本特征和PageRank的基本思路。在研究主要解决思路时，考虑到历史图的各种性质（如频繁增删）和处理效率，若使用链表结构，在数据量庞大的情况下其查询所耗费的时间将会很大，因此我们使用CSR结构作为主要的数据结构。在此基础上借鉴串行计算和并行计算的思想产生了两个不同的方法，并分析了他们各自的特点。

实验表明，使用CSR结构解决历史图上PageRank问题的性能确实会优于使用链表结构，而且效果明显。

目前，在单机情况下，对于处理多个问询Parallel Method的效率低于Serial Method的效率。在接下来的工作中会考虑使用分布式数据处理系统来对Parallel Method进行实验优化，尝试提高其计算效率。

参考文献

[1]WU J P,LIN S,XU K,et al.Advances in Evolvable New Generation Internet Architecture[J].Chinese Journal of Computer,2012,35(06):1094-1108.

吴建平,林嵩,徐恪等.可演进的新一代互联网体系结构研究进展[J].计算机学报,2012,35(06):1094-1108.

[2]Przytycka T M, Singh M , Slonim D K.Toward the dynamic interactome:It's about time[J].Briefings in Bioinformatics,2010,11(1):15–29.

[3]CAO J.Analysis of Google's PageRank techno-

logy[J].Journal of Information,2002(10):15-18.

曹军.Google的PageRank技术剖析[J].情报杂志2002(10):15-18.

[4]Chang J W,DAI D H.Personalized Recommend-

ation Algorithm Based on PageRank and Spectral Method[J].Computer Science,2018,45(S2):398-401.

常家伟,戴牡红.基于PageRank和谱方法的个性化推荐算法[J].计算机科学,2018,45(S2):398-401.

[5]LI C S,LIU X G,JIAO H T et al.An Improved PageRank Algorithm Based on APP Search System[J].Computer and Modernization, 2018(07):24-27+38.

李春生,刘小刚,焦海涛,张可佳.基于APP搜索系统的PageRank改进算法[J].计算机与现代化,2018(07):24-27+38.

[6]Francisco Pedroche,Esther García,Miguel Romance,et al.On the spectrum of two-layer approach and Multiplex PageRank[J]. Journal of Computational and Applied Mathematics,2018,344.

[7]Harary F,Gupta G.Dynamic graph models[J]. Mathematical and Computer Modelling, 1997, 25(7):79-87.

[8]DING L L,LI Z D,JI W T, et al.Reachability Query of Large Scale Dynamic Graph Based on Improved Huffman Coding[J]. Acta Electronica Sinica,2017,45(02):359-367.

丁琳琳,李正道,纪婉婷,宋宝燕.基于改进哈夫曼编码的大规模动态图可达查询方法[J].电子学报2017,45(02):359-367.

[9]WANG C,CHEN L.Continuous Subgraph Pattern Search over Graph Streams[C]// International Conference on Data Engineering. IEEE, 2009.

[10] FAN W , LI J , LUO J , et al.Incremental graph pattern matching[C]//Acm Sigmod International Conference on Management of Data. ACM, 2011.

[11]Choudhury S, Holder L, Chin G, et al.Proc. of the Workshop on Dynamic Networks Management and Mining[C]// International Conference on Management of Data. SIGMOD/PODS'13, 2013.

[12]WU L K,XIAO X K,DENG D X, et al.Shortest Path and Distance Queries on Road Networks:An Experimental Evaluation[J].Proceeding of the VLDB Endowment, 2012,5(5):406-417.

[13] Page L,Brin S,Motwani R,et al. The PageRank Citation Ranking: Bringing Order to the Web[J]. Stanford Digital Libraries Working Paper,1998, 9(1):1-14.

[14]WEI Z W,HE X D,X X K,et al. TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs[C].// International Conference on Management of Data.SIGMOD,2018.

[15]HAVELIWALA,T.H .Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search[J]. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(4):784-796.

[16] ROUL R.K., SAHOO J.K., ARORA K. Query-Optimized PageRank: A Novel Approach[M]. Computational Intelligence in Data Mining. Advances in Intelligent Systems and Computing. Singapore:Springer,2019:673-683

[17]LI C C,KANG Z J,YU H G, et al. Identification Method of Key Nodes in Power System Based on Improved PageRank Algorithm[J]. Transactions of China Electrotechnical Society,2019,34(09):168-175.

李昌超, 康忠健, 于洪国, et al. 基于PageRank改进算法的电力系统关键节点识别[J].电工技术学报, 2019, 34(09):168-175.

[18]LIU Z Y,LI Q F,CENG C, et al.An Optimization Method of PageRank Based on Spark and its Application Research[J].Journal of CAEIT, 2018(4):399-405.

刘振宇, 李钦富, 曾操, et al.基于Spark的PageRank算法优化及其军事应用研究[J]. 中国电子科学研究院学报, 2018(4):399-405 

(责编：刘扬、赵光霞)