Abstract
We analyze the distribution of PageRank on a directed configuration model and show that as the size of the graph grows to infinity, the PageRank of a randomly chosen node can be closely approximated by the PageRank of the root node of an appropriately constructed tree. This tree approximation is in turn related to the solution of a linear stochastic fixed-point equation that has been thoroughly studied in the recent literature.
The second author was partially funded by the EU-FET Open grant NADINE (288956). The third author was supported by the NSF grant CMMI-1131053.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Alsmeyer, G., Damek, E., Mentemeier, S.: Tails of fixed points of the two-sided smoothing transform. In: Springer Proceedings in Mathematics & Statistics: Random Matrices and Iterated Random Functions (2012)
Alsmeyer, G., Meiners, M.: Fixed points of the smoothing transform: Two-sided solutions. Probab. Theory Relat. Fields 155(1–2), 165–199 (2013)
Avrachenkov, K., Lebedev, D.: PageRank of scale-free growing networks. Internet Mathematics 3(2), 207–231 (2006)
Brin, S., Page, L.: The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems 33, 107–117 (1998)
Chen, N., Litvak, N., Olvera-Cravioto, M.: Ranking algorithms on directed configuration networks. ArXiv:1409.7443, pp. 1–39 (2014)
Chen, N., Olvera-Cravioto, M.: Directed random graphs with given degree distributions. Stochastic Systems 3(1), 147–186 (2013)
Jelenković, P.R., Olvera-Cravioto, M.: Information ranking and power laws on trees. Adv. Appl. Prob. 42(4), 1057–1093 (2010)
Jelenković, P.R., Olvera-Cravioto, M.: Implicit renewal theory and power tails on trees. Adv. Appl. Prob. 44(2), 528–561 (2012)
Jelenković, P.R., Olvera-Cravioto, M.: Implicit renewal theory for trees with general weights. Stochastic Process. Appl. 122(9), 3209–3238 (2012)
Langville, A.N., Meyer, C.D.: Google PageRank and beyond. Princeton University Press (2006)
Litvak, N., Scheinhardt, W.R.W., Volkovich, Y.: In-degree and PageRank: Why do they follow similar power laws? Internet Mathematics 4(2), 175–198 (2007)
Olvera-Cravioto, M.: Tail behavior of solutions of linear recursions on trees. Stochastic Process. Appl. 122(4), 1777–1807 (2012)
Pandurangan, G., Raghavan, P., Upfal, E.: Using PageRank to characterize web structure. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol. 2387, pp. 330–339. Springer, Heidelberg (2002)
van der Hofstad, R.: Random graphs and complex networks (2009)
Volkovich, Y., Litvak, N.: Asymptotic analysis for personalized web search. Adv. Appl. Prob. 42(2), 577–604 (2010)
Volkovich, Y., Litvak, N., Donato, D.: Determining factors behind the pagerank log-log plot. In: Proceedings of the 5th International Workshop on Algorithms and Models for the Web-graph, pp. 108–123 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Chen, N., Litvak, N., Olvera-Cravioto, M. (2014). PageRank in Scale-Free Random Graphs. In: Bonato, A., Graham, F., Prałat, P. (eds) Algorithms and Models for the Web Graph. WAW 2014. Lecture Notes in Computer Science(), vol 8882. Springer, Cham. https://doi.org/10.1007/978-3-319-13123-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-13123-8_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13122-1
Online ISBN: 978-3-319-13123-8
eBook Packages: Computer ScienceComputer Science (R0)