nach oben

Calcolo

Erschienen in:

01.03.2017

On the convergence of the minimally irreducible Markov chain method with applications to PageRank

verfasst von: Gang Wu

Erschienen in: Calcolo | Ausgabe 1/2017

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

PageRank is an important technique for determining the most important nodes in the Web. In this paper, we point out that the main result derived in Bao and Zhu [Acta Math Appl Sin (Engl Ser) 22:517–528, 2006] is incorrect, and establish new lower and upper bounds on the convergence of the minimally irreducible Markov chain method for PageRank. We show that the asymptotic convergence rates of the maximally and the minimally irreducible Markov chains are the same when the damping factor \(\frac{1}{2}\le \alpha <1\), however, they are not mathematically equivalent any more as \(0<\alpha <\frac{1}{2}\). Numerical experiments validate our theoretical results.

Vorheriger Artikel Gaussian radial basis function interpolant for the different data sites and basis centers

Nächster Artikel Fast indefinite multi-point (IMP) clustering

http://www.cise.ufl.edu/research/sparse/matrices/Gleich/index.html.

Avrachenkov, K., Litvak, N., Pham, K.: A singular perturbation approach for choosing PageRank damping factor. Internet Math. 5, 47–69 (2008)MathSciNetCrossRefMATH

Bao, Y., Zhu, Z.: Comparison of three Web search algorithms. Acta Math. Appl. Sin. (Engl. Ser.) 22, 517–528 (2006)MathSciNetCrossRefMATH

Benzi, M., Estrada, E., Klymko, C.: Ranking hubs and authorities using matrix functions. Linear Algebra Appl. 438, 2447–2474 (2013)MathSciNetCrossRefMATH

Benzi, M., Klymko, C.: On the limiting behavior of parameter-dependent network centrality measures. SIAM J. Matrix Anal. Appl. 36, 686–706 (2015)MathSciNetCrossRefMATH

Berman, A., Plemmons, R.: Nonnegative Matrices in the Mathematical Science. Academic Press, New York (1979). [SIAM, Philadelphia (1994)]

Boldi, P., Santini, M., Vigna. S.: PageRank: functional dependencies. ACM Trans. Inf. Syst. 27(4), Article 1 (2009)

Boldi, P., Santini, M., Vigna, S.: A deeper investigation of pagerank as a function of the damping factor. In: Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, vol. 07071 (2007)

Constantine, P., Gleich, D.: Random alpha PageRank. Internet Math. 6, 189–236 (2010)MathSciNetCrossRefMATH

Estrada, E.: The Structure of Complex Networks. Oxford University Press, Oxford (2011)CrossRef

10.

Estrada, E., Higham, D.: Network properties revealed through matrix functions. SIAM Rev. 52, 696–714 (2010)MathSciNetCrossRefMATH

11.

Gleich, D.: PageRank beyond the Web. SIAM Rev. 57, 321–363 (2015)MathSciNetCrossRefMATH

12.

Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. Johns Hopkins University Press, Baltimore (2013)MATH

13.

Kollias, G., Gallopoulos, E., Grama, A.: Surfing the network for ranking by multidamping. IEEE Trans. Knowl. Data Eng. 26, 2323–2336 (2014)CrossRef

14.

Haveliwala, T., Kamvar, S.: The Second Eigenvalue of the Google Matrix. Technical Report, Stanford University, Stanford (2003)

15.

Langville, A., Meyer, C.: Fiddling with PageRank. Techniqal Report, Department of Mathematics, North Carolina State University, Raleigh (2003)

16.

Langville, A., Meyer, C.: Deeper inside PageRank. Internet Math. 1, 335–380 (2005)MathSciNetCrossRefMATH

17.

Langville, A., Meyer, C.: A reordering for the PageRank problem. SIAM J. Sci. Comput. 27, 2112–2120 (2006)MathSciNetCrossRefMATH

18.

Langville, A., Meyer, C.: Updating the stationary vector of an irreducible Markov chain with an eye on Google’s PageRank. SIAM J. Matrix Anal. 27, 968–987 (2006)CrossRefMATH

19.

Langville, A., Meyer, C.: Google’s PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, Princeton (2006)MATH

20.

Meyer, C.: Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia (2000)CrossRef

21.

Newman, M.: Networks: An Introduction. Cambridge University Press, Cambridge (2010)CrossRefMATH

22.

Page, L., Motwami, R., Winograd, T.: The PageRank citation ranking: bring order to the web. Technical Report, Computer Science Department, Stanford University, Stanford (1998)

23.

Tomlin. J.: A new paradigm for ranking pages on the World Wide Web. In: Proceedings of the Twelfth International Conference on World Wide Web, pp. 350–355. ACM Press, New York (2003)

24.

Wills, R., Ipsen, I.: Ordinal ranking for Google’s PageRank. SIAM J. Matrix Anal. Appl. 30, 1677–1696 (2009)MathSciNetCrossRefMATH

25.

Wu, G.: Eigenvalues of certain augmented complex stochastic matrices with application in PageRank. In: Jin, X., Sun, H., Vong, S. (eds.) Recent Advances in Scientific Computing and Matrix Analysis, pp. 85–92. International Press, Boston (2011)

26.

Wu, G., Wang, Y., Jin, X.: A preconditioned and shifted GMRES algorithm for the PageRank problem with multiple damping factors. SIAM J. Sci. Comput. 34, A2558–A2575 (2012)MathSciNetCrossRefMATH

27.

Zhang, H., Goel, A., Govindan, R., Mason, K., Van Roy. B.: Making eigenvector-based reputation system robust to collusion. http://www.stanford.edu/group/reputation/WAWadapt (2004)

Titel: On the convergence of the minimally irreducible Markov chain method with applications to PageRank
verfasst von: Gang Wu
Publikationsdatum: 01.03.2017
Verlag: Springer Milan
Erschienen in: Calcolo / Ausgabe 1/2017
Print ISSN: 0008-0624
Elektronische ISSN: 1126-5434
DOI: https://doi.org/10.1007/s10092-016-0186-z

Springer Professional

On the convergence of the minimally irreducible Markov chain method with applications to PageRank

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 1/2017

Numerical approximation of stochastic differential delay equation with coefficients of polynomial growth

Gaussian radial basis function interpolant for the different data sites and basis centers

An extended Hessenberg form for Hamiltonian matrices

Fast indefinite multi-point (IMP) clustering

On the grad-div stabilization for the steady Oseen and Navier-Stokes equations

Premium Partner