Open Access

An Efficient Monte Carlo Approach to Compute PageRank for Large Graphs on a Single PC


[1] K. Avrachenkov, N. Litvak, D. Nemirovsky, and N. Osipova. Monte carlo methods in pagerank computation: When one iteration is sufficient. SIAM Jounal on Numerical Analysis, (2):890–904, February 2007.10.1137/050643799Search in Google Scholar

[2] Bahman Bahmani, Kaushik Chakrabarti, and Dong Xin. Fast personalized pagerank on mapreduce. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, pages 973–984, 2011.10.1145/1989323.1989425Search in Google Scholar

[3] Bahman Bahmani, Abdur Chowdhury, and Ashish Goel. Fast incremental and personalized pagerank. VLDB Endow., 4(3):173–184, 2010.10.14778/1929861.1929864Search in Google Scholar

[4] Paolo Boldi and Sebastiano Vigna. The WebGraph framework I: Compression techniques. In Proceedings of the Thirteenth International World Wide Web Conference (WWW 2004), pages 595–601, 2004.10.1145/988672.988752Search in Google Scholar

[5] Yenyu Chen, Qingqing Gan, and Torsten Suel. Local methods for estimating pagerank values. In Proceedings of the Thirteenth ACM International Conference on Information and Knowledge Management, pages 381–389, 2004.10.1145/1031171.1031248Search in Google Scholar

[6] Shumo Chu and James Cheng. Triangle listing in massive networks and its applications. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 672–680, 2011.10.1145/2020408.2020513Search in Google Scholar

[7] Atish Das Sarma, Sreenivas Gollapudi, and Rina Panigrahy. Estimating pagerank on graph streams. In Proceedings of the Twenty-seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 69–78, 2008.10.1145/1376916.1376928Search in Google Scholar

[8] Atish Das Sarma, AnisurRahaman Molla, Gopal Pandurangan, and Eli Upfal. Fast distributed pagerank computation. In Distributed Computing and Networking, pages 11–26. 2013.10.1007/978-3-642-35668-1_2Search in Google Scholar

[9] Dániel Fogaras and Balázs Rácz. Towards scaling fully personalized pagerank. In Algorithms and Models for the Web-Graph, pages 105–117. 2004.10.1007/978-3-540-30216-2_9Search in Google Scholar

[10] Wookshin Han, Sangyeon Lee, Kyungyeol Park, Jeonghoon Lee, Minsoo Kim, Jinha Kim, and Hwanjo Yu. Turbograph: a fast parallel graph engine handling billion-scale graphs in a single pc. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 77–85, 2013.Search in Google Scholar

[11] Sepandar Kamvar, Taher Haveliwala, Christopher Manning, and Gene Golub. Exploiting the block structure of the web for computing pagerank. Stanford University Technical Report, 2003.Search in Google Scholar

[12] U. Kang and Christos Faloutsos. Big graph mining: Algorithms and discoveries. SIGKDD Explorations Newsletter, (2):29–36, April 2013.10.1145/2481244.2481249Search in Google Scholar

[13] Christian Kohlschütter, Paul-Alexandru Chirita, and Wolfgang Nejdl. Efficient parallel computation of pagerank. In Advances in Information Retrieval, pages 241–252. 2006.10.1007/11735106_22Search in Google Scholar

[14] Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. What is Twitter, a social network or a news media? In Proceedings of the 19th International Conference on World Wide Web, pages 591–600, 2010.10.1145/1772690.1772751Search in Google Scholar

[15] Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. Graphchi: Large-scale graph computation on just a pc. In Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation, pages 31–46, 2012.Search in Google Scholar

[16] Grzegorz Malewicz, Matthew H Austern, Aart JC Bik, James C Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. Pregel: a system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, pages 135–146, 2010.10.1145/1807167.1807184Search in Google Scholar

[17] Frank McSherry. A uniform approach to accelerated pagerank computation. In Proceedings of the 14th international conference on World Wide Web, pages 575–582, 2005.10.1145/1060745.1060829Search in Google Scholar

[18] Julie L Morrison, Rainer Breitling, Desmond J Higham, and David R Gilbert. Generank: using search engine technology for the analysis of microarray experiments. BMC bioinformatics, (1):233, 2005.Search in Google Scholar

[19] Mark E. J. Newman. Fast algorithm for detecting community structure in networks. Physical review E, 69(6):066133, 2004.10.1103/PhysRevE.69.06613315244693Search in Google Scholar

[20] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. 1999.Search in Google Scholar

[21] Jiayu Pan, Hyungjeong Yang, Christos Faloutsos, and Pinar Duygulu. Automatic multimedia cross-modal correlation discovery. In Proceedings of the tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 653–658, 2004.10.1145/1014052.1014135Search in Google Scholar

[22] Marcin Sydow. Random surfer with back step. Fundamental Informaticae, 68(4):379–398, 2005.Search in Google Scholar

[23] John Wicks and Amy Greenwald. Parallelizing the computation of pagerank. In Algorithms and Models for the Web-Graph, pages 202–208. 2007.10.1007/978-3-540-77004-6_17Search in Google Scholar

[24] Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, pages 1–8, 2012.10.1145/2350190.2350193Search in Google Scholar

Publication timeframe:
4 times per year
Journal Subjects:
Computer Sciences, Artificial Intelligence, Software Development