Have a personal or library account? Click to login
An Efficient Monte Carlo Approach to Compute PageRank for Large Graphs on a Single PC Cover

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

Foundations of Computing and Decision Sciences
Volume 41 (2016): Issue 1 (March 2016)
By: Tomohiro Sonobe  
Open Access
|Mar 2016

References

  1. [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/050643799
    Search in Google Scholar
  2. [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.1989425
    Search in Google Scholar
  3. [3] Bahman Bahmani, Abdur Chowdhury, and Ashish Goel. Fast incremental and personalized pagerank. VLDB Endow., 4(3):173–184, 2010.10.14778/1929861.1929864
    Search in Google Scholar
  4. [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.988752
    Search in Google Scholar
  5. [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.1031248
    Search in Google Scholar
  6. [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.2020513
    Search in Google Scholar
  7. [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.1376928
    Search in Google Scholar
  8. [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_2
    Search in Google Scholar
  9. [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_9
    Search in Google Scholar
  10. [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. [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. [12] U. Kang and Christos Faloutsos. Big graph mining: Algorithms and discoveries. SIGKDD Explorations Newsletter, (2):29–36, April 2013.10.1145/2481244.2481249
    Search in Google Scholar
  13. [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_22
    Search in Google Scholar
  14. [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.1772751
    Search in Google Scholar
  15. [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. [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.1807184
    Search in Google Scholar
  17. [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.1060829
    Search in Google Scholar
  18. [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. [19] Mark E. J. Newman. Fast algorithm for detecting community structure in networks. Physical review E, 69(6):066133, 2004.10.1103/PhysRevE.69.06613315244693
    Search in Google Scholar
  20. [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. [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.1014135
    Search in Google Scholar
  22. [22] Marcin Sydow. Random surfer with back step. Fundamental Informaticae, 68(4):379–398, 2005.
    Search in Google Scholar
  23. [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_17
    Search in Google Scholar
  24. [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.2350193
    Search in Google Scholar
DOI: https://doi.org/10.1515/fcds-2016-0002 | Journal eISSN: 2300-3405 | Journal ISSN: 0867-6356
Journal RSS Feed
Language: English
Page range: 29 - 43
Submitted on: Jan 27, 2015
Accepted on: Jan 30, 2016
Published on: Mar 31, 2016
Published by: Poznan University of Technology
In partnership with: Paradigm Publishing Services
Publication frequency: 4 issues per year
Keywords:
Graph,
Monte Carlo,
PageRank,
Random Walk
Related subjects:
Computer sciences,
Artificial intelligence,
Software development

© 2016 Tomohiro Sonobe, published by Poznan University of Technology
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Previous articleVolume 41 (2016): Issue 1 (March 2016)Next article