Computer Science

Computer Science ›› 2020, Vol. 47 ›› Issue (9): 88-93.doi: 10.11896/jsjkx.190800122

• Database & Big Data & Data Science • Previous Articles     Next Articles

CSR-based PageRank Algorithm on Historical Graphs

PAN Pei-xian, ZOU Zhao-nian, LI Fa-ming   

  1. School of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001,China
  • Received:2019-08-26 Published:2020-09-10
  • About author:PAN Pei-xian,born in 1996,master candidate.His main research interests include graph data mining and so on.
    ZOU Zhao-nian,born in 1979,Ph.D,associate professor,Ph.D supervisor,is a member of China Computer Federation.His main research interests include big data,graph databases and data mining.
  • Supported by:
    Surface Project of National Natural Science Foundation of China (61672189) and Key Program of National Natural Science Foundation of China (61532015).

PDF (PC)

797

Abstract: 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.

Key words: Compressed Sparse Row structure, Historical graph, PageRank

CLC Number: 

  • TP311
[1] WU J P,LIN S,XU K,et al.Advances in Evolvable New Generation Internet Architecture[J].Chinese Journal of Computer,2012,35(6):1094-1108.
[2] PRZYTYCKA T M,SINGH M,SLONIM D K.Toward the dynamic interactome:It's about time[J].Briefings in Bioinforma-tics,2010,11(1):15-29.
[3] CAO J.Analysis of Google’s PageRank technology[J].Journal of Information,2002(10):15-18.
[4] CHANG J W,DAI D H.Personalized Recommendation Algorithm Based on PageRank and Spectral Method[J].Computer Science,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 Mo-dernization,2018(7):24-27,38.
[6] PEDROCHE F,GARCÍA E,ROMANCE M,et al.On the spectrum of two-layer approach and Multiplex PageRank[J].Journal of Computational and Applied Mathematics,2018,344:161-172.
[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(2):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.Proceedings 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] HAVELIWALATH.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 Page-Rank: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(9):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.
[1] WANG Xin-sheng,MA Shu-zhang. Method of Weibo User Influence Calculation Integrating Users’ Own Factors and Interaction Behavior [J]. Computer Science, 2020, 47(1): 96-101.
[2] LIU Xiao-jie, LV Xiao-qiang, WANG Xiao-ling, ZHANG Wei, ZHAO An. Mining User Interests on Twitter Using Wikipedia Category Graph [J]. Computer Science, 2019, 46(9): 79-84.
[3] WANG Rong-bing, AN Wei-kai, FENG Yong and XU Hong-yan. Important Micro-blog User Recommendation Algorithm Based on Label and PageRank [J]. Computer Science, 2018, 45(2): 276-279.
[4] CHANG Jia-wei, DAI Mu-hong. Personalized Recommendation Algorithm Based on PageRank and Spectral Method [J]. Computer Science, 2018, 45(11A): 398-401.
[5] QI Yu-dong, HE Cheng and YUAN Wei. Algorithm of Importance Ranking for Influencing Factors of Website Service Quality Based on PageRank [J]. Computer Science, 2017, 44(Z11): 80-83.
[6] XUE Zhu-jun, YANG Shu-qiang and SHU Yang-xue. Microblog Text Summarization Based on Entity Relation Network [J]. Computer Science, 2016, 43(9): 77-81.
[7] XU Wen-tao, LIU Feng and ZHU Er-zhou. Research on Novel Ranking Algorithm of Microblog User’s Influence Based on MapReduce [J]. Computer Science, 2016, 43(9): 66-70.
[8] ZHU Ming-feng, YE Shi-ren and YE Ren-ming. Extract Summarization Method Based on Lex-PageRank in Chinese Microblog [J]. Computer Science, 2016, 43(9): 261-265.
[9] WANG Chong and JI Xian-hui. Improved PageRank Algorithm Based on User Interest and Topic [J]. Computer Science, 2016, 43(3): 275-278.
[10] BAI Liang, YU Tian-yuan, LIU Shi, LAO Song-yang and YANG Zheng. Ranking Algorithm of Search Engine Using Improved Spectral Clustering [J]. Computer Science, 2016, 43(10): 220-224.
[11] YANG Jun-hui, LIU Zong-tian, LIU Wei and SU Xiao-ying. Extraction Method of Text Summarization Based on Event Network [J]. Computer Science, 2015, 42(3): 210-213.
[12] YU Yi,GAN Ruo-xun,FAN Suo-hai,LIU Qing and SHAO Qing. Journal Evaluation Based on PageRank Algorithm and HITS Algorithm [J]. Computer Science, 2014, 41(Z6): 110-113.
[13] ZHOU Yong-mei,YANG Ai-min and YANG Jia-neng. Construction Method of Sentiment Lexicon for News Reviews [J]. Computer Science, 2014, 41(8): 67-69.
[14] CAO Shan-shan and WANG Chong. Improved PageRank Algorithm Based on Links and User Feedback [J]. Computer Science, 2014, 41(12): 179-182.
[15] GONG Xiu-wen and ZHANG Pei-yun. Research on Propagation Model and Algorithm for Influence Maximization in Social Network Based on PageRank [J]. Computer Science, 2013, 40(Z6): 136-140.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.