×

Local weak convergence for PageRank. (English) Zbl 1434.60027

Summary: PageRank is a well-known algorithm for measuring centrality in networks. It was originally proposed by Google for ranking pages in the World Wide Web. One of the intriguing empirical properties of PageRank is the so-called ‘power-law hypothesis’: in a scale-free network, the PageRank scores follow a power law with the same exponent as the (in-)degrees. To date, this hypothesis has been confirmed empirically and in several specific random graphs models. In contrast, this paper does not focus on one random graph model but investigates the existence of an asymptotic PageRank distribution, when the graph size goes to infinity, using local weak convergence. This may help to identify general network structures in which the power-law hypothesis holds. We start from the definition of local weak convergence for sequences of (random) undirected graphs, and extend this notion to directed graphs. To this end, we define an exploration process in the directed setting that keeps track of in- and out-degrees of vertices. Then we use this to prove the existence of an asymptotic PageRank distribution. As a result, the limiting distribution of PageRank can be computed directly as a function of the limiting object. We apply our results to the directed configuration model and continuous-time branching processes trees, as well as to preferential attachment models.

MSC:

60B20 Random matrices (probabilistic aspects)
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] Albert, R. and Barabási, A.-L. (2002). Statistical mechanics of complex networks. Rev. Modern Phys. 74 47-97. · Zbl 1205.82086
[2] Aldous, D. (1991). Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1 228-266. · Zbl 0733.60016 · doi:10.1214/aoap/1177005936
[3] Aldous, D. and Lyons, R. (2007). Processes on unimodular random networks. Electron. J. Probab. 12 1454-1508. · Zbl 1131.60003 · doi:10.1214/EJP.v12-463
[4] Aldous, D. and Steele, J. M. (2004). The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures. Encyclopaedia Math. Sci. 110 1-72. Springer, Berlin. · Zbl 1037.60008
[5] Andersen, R., Chung, F. and Lang, K. (2006). Local graph partitioning using PageRank vectors. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science 475-486.
[6] Athreya, K. B. (2007). Preferential attachment random graphs with general weight function. Internet Math. 4 401-418. · Zbl 1206.68225 · doi:10.1080/15427951.2007.10129150
[7] Athreya, K. B., Ghosh, A. P. and Sethuraman, S. (2008). Growth of preferential attachment random graphs via continuous-time branching processes. Proc. Indian Acad. Sci. Math. Sci. 118 473-494. · Zbl 1153.05020 · doi:10.1007/s12044-008-0036-2
[8] Athreya, K. B. and Ney, P. E. (2004). Branching Processes. Dover, Mineola, NY. Reprint of the 1972 original [Springer, New York; MR0373040]. · Zbl 1070.60001
[9] Avrachenkov, K., Kadavankandy, A., Prokhorenkova, L. O. and Raigorodskii, A. (2015). PageRank in undirected random graphs. In Algorithms and Models for the Web Graph. Lecture Notes in Computer Science 9479 151-163. Springer, Cham. · Zbl 1342.05131
[10] Avrachenkov, K. and Lebedev, D. (2006). PageRank of scale-free growing networks. Internet Math. 3 207-231. · Zbl 1122.68406 · doi:10.1080/15427951.2006.10129120
[11] Avrachenkov, K. and Litvak, N. (2006). The effect of new links on Google PageRank. Stoch. Models 22 319-331. · Zbl 1094.68005 · doi:10.1080/15326340600649052
[12] Bahmani, B., Chowdhury, A. and Goel, A. (2010). Fast incremental and personalized PageRank. Proc. VLDB Endow. 4 173-184.
[13] Benjamini, I., Lyons, R. and Schramm, O. (2015). Unimodular random trees. Ergodic Theory Dynam. Systems 35 359-373. · Zbl 1328.05166 · doi:10.1017/etds.2013.56
[14] Benjamini, I. and Schramm, O. (2001). Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 no. 23, 13. · Zbl 1010.82021 · doi:10.1214/EJP.v6-96
[15] Berger, N., Borgs, C., Chayes, J. T. and Saberi, A. (2014). Asymptotic behavior and distributional limits of preferential attachment graphs. Ann. Probab. 42 1-40. · Zbl 1296.60010 · doi:10.1214/12-AOP755
[16] Bianchini, M., Gori, M. and Scarselli, F. (2005). Inside PageRank. ACM Trans. Internet Technol. 5 92-128.
[17] Britton, T., Deijfen, M. and Martin-Löf, A. (2006). Generating simple random graphs with prescribed degree distribution. J. Stat. Phys. 124 1377-1397. · Zbl 1106.05086 · doi:10.1007/s10955-006-9168-x
[18] Cao, J. and Olvera-Cravioto, M. (2017). On a general class of inhomogeneous random digraphs. Preprint. Available at arXiv:1712.03319 [math.PR]. · Zbl 1453.82005
[19] Caravenna, F., Garavaglia, A. and van der Hofstad, R. (2019). Diameter in ultra-small scale-free random graphs. Random Structures Algorithms 54 444-498. · Zbl 1414.05098 · doi:10.1002/rsa.20798
[20] Chen, N., Litvak, N. and Olvera-Cravioto, M. (2014). PageRank in scale-free random graphs. In Algorithms and Models for the Web Graph. Lecture Notes in Computer Science 8882 120-131. Springer, Cham. · Zbl 1342.05136
[21] Chen, N., Litvak, N. and Olvera-Cravioto, M. (2017). Generalized PageRank on directed configuration networks. Random Structures Algorithms 51 237-274. · Zbl 1370.05199 · doi:10.1002/rsa.20700
[22] Chen, N. and Olvera-Cravioto, M. (2013). Directed random graphs with given degree distributions. Stoch. Syst. 3 147-186. · Zbl 1297.05212 · doi:10.1287/12-SSY076
[23] Chen, P., Xie, H., Maslov, S. and Redner, S. (2007). Finding scientific gems with Google’s PageRank algorithm. J. Informetr. 1 8-15.
[24] Chung, F. and Lu, L. (2001). The diameter of sparse random graphs. Adv. in Appl. Math. 26 257-279. · Zbl 0977.05127 · doi:10.1006/aama.2001.0720
[25] Chung, F. and Lu, L. (2002). Connected components in random graphs with given expected degree sequences. Ann. Comb. 6 125-145. · Zbl 1009.05124 · doi:10.1007/PL00012580
[26] Dereich, S., Mönch, C. and Mörters, P. (2012). Typical distances in ultrasmall random networks. Adv. in Appl. Probab. 44 583-601. · Zbl 1244.05199
[27] Dereich, S. and Mörters, P. (2009). Random networks with sublinear preferential attachment: Degree evolutions. Electron. J. Probab. 14 1222-1267. · Zbl 1185.05127 · doi:10.1214/EJP.v14-647
[28] Dereich, S. and Mörters, P. (2011). Random networks with concave preferential attachment rule. Jahresber. Dtsch. Math.-Ver. 113 21-40. · Zbl 1217.05206 · doi:10.1365/s13291-010-0011-6
[29] Dereich, S. and Mörters, P. (2013). Random networks with sublinear preferential attachment: The giant component. Ann. Probab. 41 329-384. · Zbl 1260.05143 · doi:10.1214/11-AOP697
[30] Dommers, S., van der Hofstad, R. and Hooghiemstra, G. (2010). Diameters in preferential attachment models. J. Stat. Phys. 139 72-107. · Zbl 1191.82020 · doi:10.1007/s10955-010-9921-z
[31] van den Esker, H., van der Hofstad, R. and Hooghiemstra, G. (2008). Universality for the distance in finite variance random graphs. J. Stat. Phys. 133 169-202. · Zbl 1152.82008 · doi:10.1007/s10955-008-9594-z
[32] Gabrysch, K. (2016). Convergence of directed random graphs to the Poisson-weighted infinite tree. J. Appl. Probab. 53 463-474. · Zbl 1342.05140 · doi:10.1017/jpr.2016.13
[33] Garavaglia, A. and van der Hofstad, R. (2018). From trees to graphs: Collapsing continuous-time branching processes. J. Appl. Probab. 55 900-919. · Zbl 1400.05210 · doi:10.1017/jpr.2018.57
[34] Garavaglia, A., van der Hofstad, R. and Woeginger, G. (2017). The dynamics of power laws: Fitness and aging in preferential attachment trees. J. Stat. Phys. 168 1137-1179. · Zbl 1373.60148 · doi:10.1007/s10955-017-1841-8
[35] Grimmett, G. R. (1980/81). Random labelled trees and their branching networks. J. Aust. Math. Soc. A 30 229-237. · Zbl 0455.05028 · doi:10.1017/S1446788700016517
[36] Haveliwala, T. H. (2002). Topic-sensitive PageRank. In Proceedings of the 11th International Conference on World-Wide Web 517-526.
[37] van der Hofstad, R. (2017). Random Graphs and Complex Networks. Vol. 1. Cambridge Series in Statistical and Probabilistic Mathematics 43. Cambridge Univ. Press, Cambridge. · Zbl 1361.05002
[38] van der Hofstad, R. (2019+). Random Graphs and Complex Networks. Vol. 2. In preparation. Available at http://www.win.tue.nl/ rhofstad/NotesRGCNII.pdf. · Zbl 1361.05002
[39] van der Hofstad, R. (2019+). Stochastic Processes on Random Graphs. Lecture Notes for the Saint-Flour Summer School in Probability 2017. Available at https://www.win.tue.nl/ rhofstad/SaintFlour_SPoRG.pdf.
[40] Holmgren, C. and Janson, S. (2017). Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees. Probab. Surv. 14 53-154. · Zbl 1406.60120 · doi:10.1214/16-PS272
[41] Jagers, P. (1975). Branching Processes with Biological Applications. Wiley Series in Probability and Mathematical Statistics—Applied Probability and Statistics. Wiley Interscience, London. · Zbl 0356.60039
[42] Jagers, P. and Nerman, O. (1984). The growth and composition of branching populations. Adv. in Appl. Probab. 16 221-259. · Zbl 0535.60075 · doi:10.2307/1427068
[43] Jelenković, P. R. and Olvera-Cravioto, M. (2010). Information ranking and power laws on trees. Adv. in Appl. Probab. 42 1057-1093. · Zbl 1211.60026 · doi:10.1239/aap/1293113151
[44] Lee, C. P. C., Golub, G. H. and Zenios, S. A. (2003). A fast two-stage algorithm for computing PageRank and its extensions. Sci. Comput. Comput. Math. 1 1-9.
[45] Lee, J. and Olvera-Cravioto, M. (2017). PageRank on inhomogeneous random digraphs. Preprint. Available at arXiv:1707.02492 [math.PR]. · Zbl 1437.05214
[46] Litvak, N., Scheinhardt, W. R. W. and Volkovich, Y. (2007). In-degree and PageRank: Why do they follow similar power laws? Internet Math. 4 175-198. · Zbl 1206.68352 · doi:10.1080/15427951.2007.10129293
[47] Ma, N., Guan, J. and Zhao, Y. (2008). Bringing PageRank to the citation analysis. Inf. Process. Manag. 44 800-810.
[48] Nerman, O. (1981). On the convergence of supercritical general (C-M-J) branching processes. Z. Wahrsch. Verw. Gebiete 57 365-395. · Zbl 0451.60078 · doi:10.1007/BF00534830
[49] Page, L., Brin, S., Motwani, R. and Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab, 1999.
[50] Pandurangan, G., Raghavan, P. and Upfal, E. (2002). Using PageRank to characterize Web structure. In Computing and Combinatorics. Lecture Notes in Computer Science 2387 330-339. Springer, Berlin. · Zbl 1077.68527
[51] Rudas, A., Tóth, B. and Valkó, B. (2007). Random trees and general branching processes. Random Structures Algorithms 31 186-202. · Zbl 1144.60051
[52] Volkovich, Y. and Litvak, N. (2010). Asymptotic analysis for personalized web search. Adv. in Appl. Probab. 42 577-604. · Zbl 1209.68180 · doi:10.1017/S0001867800004201
[53] Waltman, L. and van Eck, N. J. (2010). The relation between eigenfactor, audience factor, and influence weight. J. Am. Soc. Inf. Sci. Technol. 61 1476-1486.
[54] Wang, R., Zhang, W., Deng, H., Wang, N., Miao, Q. and Zhao, X. (2013). Discover community leader in social network with PageRank. In Advances in Swarm Intelligence: 4th International Conference 154-162.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.