An Aitken-extrapolated Gauss-Seidel method for computing PageRank

References

• P. Berkhin, “A survey on pagerank computing,” Internet Math., vol. 2, no. 1, pp. 73–120, 2005. doi: 10.1080/15427951.2005.10129098
   Google Scholar
• L. Page, S. Brin, R. Motwani, and T. Winograd, “The PageRank citation ranking: Bringing order to the web.,” 1999.
   Google Scholar
• A. Cicone and S. Serra-Capizzano, “Google PageRanking problem: The model and the analysis,” J. Comput. Appl. Math., vol. 234, no. 11, pp. 3140–3169, 2010. doi: 10.1016/j.cam.2010.02.005
   Web of Science ®Google Scholar
• H.-H. Fu and J. C.-T. Wu, “Quality of search engines: how good is Google pagerank?,” J. Inf. Optim. Sci., vol. 31, no. 2, pp. 455–468, 2010.
   Google Scholar
• Srivastava, Atul Kumar, Rakhi Garg, and P. K. Mishra. “Analysis of iterative methods in PageRank computation.” Journal of Information and Optimization Sciences 39.1 (2018): 129-142. doi: 10.1080/02522667.2017.1372914
   Web of Science ®Google Scholar
• S. Brin and L. Page, “Reprint of: The anatomy of a large-scale hypertextual web search engine,” Comput. networks, vol. 56, no. 18, pp. 3825–3833, 2012. doi: 10.1016/j.comnet.2012.10.007
   Web of Science ®Google Scholar
• Y. Zhu, S. Ye, and X. Li, “Distributed PageRank computation based on iterative aggregation-disaggregation methods,” in Proceedings of the 14th ACM international conference on Information and knowledge management, 2005, pp. 578–585.
   Google Scholar
• A. N. Langville and C. D. Meyer, “Deeper inside pagerank,” Internet Math., vol. 1, no. 3, pp. 335–380, 2004. doi: 10.1080/15427951.2004.10129091
   Google Scholar
• M. Brinkmeier, “PageRank revisited,” ACM Trans. Internet Technol., vol. 6, no. 3, pp. 282–301, 2006. doi: 10.1145/1151087.1151090
   Google Scholar
• M. Bianchini, M. Gori, and F. Scarselli, “Inside pagerank,” ACM Trans. Internet Technol., vol. 5, no. 1, pp. 92–128, 2005. doi: 10.1145/1052934.1052938
   Google Scholar
• N. Eiron, K. S. McCurley, and J. A. Tomlin, “Ranking the web frontier,” in Proceedings of the 13th international conference on World Wide Web, 2004, pp. 309–318.
   Google Scholar
• R. S. Varga, Matrix iterative analysis, vol. 27. Springer Science & Business Media, 2009.
   Google Scholar
• C. D. Meyer, Matrix analysis and applied linear algebra, vol. 2. Siam, 2000.
   Google Scholar
• H. Sun and Y. Wei, “A note on the PageRank algorithm,” Appl. Math. Comput., vol. 179, no. 2, pp. 799–806, 2006.
   Web of Science ®Google Scholar
• P. Boldi, M. Santini, and S. Vigna, “PageRank as a function of the damping factor,” in Proceedings of the 14th international conference on World Wide Web, 2005, pp. 557–566.
   Google Scholar
• S. Serra-Capizzano, “Jordan canonical form of the Google matrix: a potential contribution to the PageRank computation,” SIAM J. Matrix Anal. Appl., vol. 27, no. 2, pp. 305–312, 2005. doi: 10.1137/S0895479804441407
   Web of Science ®Google Scholar
• K. Avrachenkov, N. Litvak, and K. S. Pham, “A singular perturbation approach for choosing the PageRank damping factor,” Internet Math., vol. 5, no. 1–2, pp. 47–69, 2008. doi: 10.1080/15427951.2008.10129300
   Google Scholar
• G. M. Del Corso, A. Gull\’\i, and F. Romani, “Comparison of Krylov subspace methods on the PageRank problem,” J. Comput. Appl. Math., vol. 210, no. 1, pp. 159–166, 2007. doi: 10.1016/j.cam.2006.10.080
   Web of Science ®Google Scholar
• A. Bourchtein and L. Bourchtein, “On some analytical properties of a general PageRank algorithm,” Math. Comput. Model., vol. 57, no. 9–10, pp. 2248–2256, May 2013. doi: 10.1016/j.mcm.2011.06.033
   Google Scholar
• C. Brezinski and M. Redivo-Zaglia, “Rational extrapolation for the PageRank vector,” Math. Comput., vol. 77, no. 263, pp. 1585–1598, 2008. doi: 10.1090/S0025-5718-08-02086-3
   Web of Science ®Google Scholar
• A. N. Langville and C. D. Meyer, “A reordering for the PageRank problem,” SIAM J. Sci. Comput., vol. 27, no. 6, pp. 2112–2120, 2006. doi: 10.1137/040607551
   Web of Science ®Google Scholar
• C. Brezinski, M. Redivo-Zaglia, and S. Serra-Capizzano, “Extrapolation methods for PageRank computations,” Comptes Rendus Math., vol. 340, no. 5, pp. 393–397, 2005. doi: 10.1016/j.crma.2005.01.015
   Web of Science ®Google Scholar
• S. Kamvar, T. Haveliwala, C. Manning, and G. Golub, “Exploiting the block structure of the web for computing pagerank,” 2003.
   Google Scholar
• G. Wu and Y. Wei, “An Arnoldi-extrapolation algorithm for computing PageRank,” J. Comput. Appl. Math., vol. 234, no. 11, pp. 3196–3212, 2010. doi: 10.1016/j.cam.2010.02.009
   Web of Science ®Google Scholar
• A. N. Langville and C. D. Meyer, Google’s PageRank and beyond: The science of search engine rankings. Princeton University Press, 2011.
   Google Scholar
• C. H. Bischof, “Adaptive blocking in the QR factorization,” J. Super-comput., vol. 3, no. 3, pp. 193–208, 1989. doi: 10.1007/BF00127828
   Google Scholar
• A. Arasu, J. Novak, A. Tomkins, and J. Tomlin, “PageRank computation and the structure of the web: Experiments and algorithms,” in Proceedings of the Eleventh International World Wide Web Conference, Poster Track, 2002, pp. 107–117.
   Google Scholar
• S. Kamvar, T. Haveliwala, and G. Golub, “Adaptive methods for the computation of PageRank,” Linear Algebra Appl., vol. 386, pp. 51–65, 2004. doi: 10.1016/j.laa.2003.12.008
   Web of Science ®Google Scholar
• X. Tan, “A new extrapolation method for PageRank computations,” J. Comput. Appl. Math., vol. 313, pp. 383–392, 2017. doi: 10.1016/j.cam.2016.08.034
   Web of Science ®Google Scholar
• Gu, C., & Wang, W., An Arnoldi-Inout algorithm for computing Pag-eRank problems. Journal of Computational and Applied Mathematics, vol. 309, pp. 219–229, 2017.. doi: 10.1016/j.cam.2016.05.026
   Web of Science ®Google Scholar
• W. J. Stewart, Introduction to the numerical solutions of Markov chains. Princeton Univ. Press, 1994.
   Google Scholar
• G. M. Del Corso, A. Gulli, and F. Romani, “Fast PageRank computation via a sparse linear system,” Internet Math., vol. 2, no. 3, pp. 251–273, 2005. doi: 10.1080/15427951.2005.10129108
   Google Scholar
• C. Moler, “The world’s largest matrix computation.” 2002.
   Google Scholar
• A. T. Tiruneh, “Higher order aitken extrapolation with application to converging and diverging Gauss-Seidel iterations,” arXiv Prepr. arXiv1310.4288, 2013.
   Google Scholar
• J. Leskovec and A. Krevl, “{SNAP Datasets}: {Stanford} Large Network Dataset Collection.” Jun-2014.
   Google Scholar