Accelerating PageRank computations

• Autorzy: Wierzchoń S. T. , Kłopotek M. A. , Ciesielski K. , Czerski D. , Dramiński M.
• Języki publikacji: EN

Abstrakty

EN

Different methods for computing PageRank vectors are analysed. Particularly, we note the opposite behavior of the power method and the Monte Carlo method. Further, a method of reducing the number of iterations of the power method is suggested.

Słowa kluczowe

EN

Page rank; power method; Jacobi iterations; Monte Carlo

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2011
• Tom: Vol. 40, no 2
• Strony: 259--274
• Opis fizyczny: Bibliogr. 26 poz., il.

Twórcy

autor

Wierzchoń S. T.

autor

Kłopotek M. A.

autor

Ciesielski K.

autor

Czerski D.

autor

Dramiński M.

• Institute of Computer Science, Polish Academy of Sciences Ordona 21, 01-237 Warszawa, Poland

Bibliografia

• Avrachenkov, K., Litvak, N., Nemirovsky, D. and Osipova, N. (2007) Monte Carlo methods in PageRank computation: When one iteration is sufficient. SIAM Journal of Numerical Analysis, 45(2), 890-904.
• Barrett, R., Berry, M., Chan, T.F., Demmel, J., Donato, J.,Dongarra, J., Eijkhout, V., Pozo, R., Romine, C. and van der Vorst, H. (1994) Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM, Philadelphia, PA.
• Boldi, P. (2005) TotalRank: Ranking without damping. In: Poster Proc. of the 14-th International Conference on the World Wide Web WWW05. ACM, New York, 898-899.
• Boldi,P., Posenato,R., Santini,M. and Vigna, S. (2008) Traps and pitfalls of topic-biased PageRank. In: W. Aiello, A. Broder, J. Janssen, and E. Milios, eds., Proc. WAW 2006. 4-th Workshop on Algorithms and Models for the Web-Graph, LNCS 4936, Springer, 107-116.
• Brin, S. and Page, L. (1998) The anatomy of a large-scale hypertextualWeb search engine. In: Proc. 7-th International World-Wide Web Conference, WWW 1998. ACM, New York.
• Chung, F. (2007) The heat kernel as the PageRank of a graph. PNAS, 105(50), 19735-19740.
• Constantine,P.G. and Gleich,D.F. (2009) Random Alpha PageRank. Internet Mathematics, 6(2), 189-236.
• Dean, J. and Ghemawat, S. (2008) MapReduce: simplified data processing on large clusters. Communications of the ACM, 51 (1), 107-113.
• DelCorso, G.M., Gulli, A. and Romani, F. (2005) Fast PageRank computation via a sparse linear system. Internet Mathematics, 2(3), 251-273.
• Fagin, R., Kumar, R. and Sivakumar, D. (2004) Comparing top k lists. SIAM Journal on Discrete Mathematics, 17(1), 134 - 160.
• Fogaras, D. and Rácz, B. (2004) Towards scaling fully personalized PageRank. In: S. Leonardi, ed., Proc. of the 3rd Workshop on Algorithms and Models for the Web-Graph (WAW 2004), LNCS 3243, Springer, 105-117.
• Gleich, D. and Zhukov, L. (2005) Scalable Computing for Power Law Graphs: Experience with Parallel PageRank. In: SuperComputing, S.C./05.ACM, New York.
• Golub, G.H. and van Loan, Ch.F. (1996) Matrix Computation. Third edition. Hindustan Book Agency, New Delhi, India.
• Haveliwala,T. (1999) Efficient Computation of PageRank. Technical Report 1999-31, Stanford InfoLab, http://ilpubs.stanford.edu:8090/386/.
• Haveliwala, T.H. and Kamvar, S.D. (2003) The Second Eigenvalue of the Google Matrix. Technical report, Stanford University.
• Kamvar, S.D., Haveliwala,T.H. and Golub,G.H. (2004) Adaptive methods for the computation of PageRank. Linear Algebra and its Applications, 386, 51-65.
• Kamvar, S.D., Haveliwala,T.H., Manning,C.D. and Golub,G.H. (2003) Exploiting the block structure of the Web for computing PageRank. Technical report, Stanford University.
• Lam, Ch and Warren, J. (2009) Hadoop in Action, Manning.
• Langville, A.N. and Meyer, C.D. (2006a) Google’s PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press.
• Langville, A.N. and Meyer, C.D. (2006b) Information Retrieval and Web Search. In: L. Hogben, R. Brualdi, A. Greenbaum, and R. Mathias, eds., Handbook of Linear Algebra, chapter 63, 63-1, CRC Press.
• Meyer, C.D. (2000) Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia.
• Page, L., Brin, S., Motwani, R. and Winograd, T. (1998) The PageRank Citation Ranking: Bringing Order to the Web. Technical report, Stanford Digital Library Technologies Project.
• Singitham, P.K.C., Mahabhashyam, M.S. and Raghavan, P. (2004) Efficiency- quality tradeoffs for vector score aggregation. In: M.A. Nascimento, M.T. Özsu, D. Kossmann, R.J. Miller, J.A. Blakeley, and K.B. Schiefer, eds., Proc. of the 30-th International Conf. on Very Large Data Bases, 30, 624-635, Morgan Kaufmann, Toronto, Canada.
• Stewart, W.J. (1994) Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton.
• Thorson, K. (2004) Modeling the Web and the computation of PageRank. Undergraduate thesis, Hollins University.
• Vigna, S. (2010) Spectral ranking. ArXiv e-prints (0912.0238).