×

Parametric controllability of the personalized PageRank: classic model vs biplex approach. (English) Zbl 1432.91094

Summary: Measures of centrality in networks defined by means of matrix algebra, like PageRank-type centralities, have been used for over 70 years. Recently, new extensions of PageRank have been formulated and may include a personalization (or teleportation) vector. It is accepted that one of the key issues for any centrality measure formulation is to what extent someone can control its variability. In this paper, we compare the limits of variability of two centrality measures for complex networks that we call classic PageRank (PR) and biplex approach PageRank (BPR). Both centrality measures depend on the so-called damping parameter \(\alpha\) that controls the quantity of teleportation. Our first result is that the intersection of the intervals of variation of both centrality measures is always a nonempty set. Our second result is that when \(\alpha\) is lower that \(0.48\) (and, therefore, the ranking is highly affected by teleportation effects) then the upper limits of PR are more controllable than the upper limits of BPR; on the contrary, when \(\alpha\) is greater than \(0.5\) (and we recall that the usual PageRank algorithm uses the value \(0.85)\), then the upper limits of PR are less controllable than the upper limits of BPR, provided certain mild assumptions on the local structure of the graph. Regarding the lower limits of variability, we give a result for small values of \(\alpha \). We illustrate the results with some analytical networks and also with a real Facebook network.
©2020 American Institute of Physics

MSC:

91D30 Social networks; opinion dynamics
05C82 Small world graphs, complex networks (graph-theoretic aspects)
15B51 Stochastic matrices

Software:

PrimAlign
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Agryzkov, T.; Curado, M.; Pedroche, F.; Tortosa, L.; Vicent, J. F., Extending the adapted PageRank algorithm centrality to multiplex networks with data using the PageRank two-layer approach, Symmetry, 11, 2, 284 (2019)
[2] Agryzkov, T.; Pedroche, F.; Tortosa, L.; Vicent, J. F., Combining the two-layers PageRank approach with the APA centrality in networks with data, ISPRS Int. J. Geo-Inf., 7, 12, 480 (2018)
[3] Allcott, H.; Gentzkow, M.; Yu, C., Trends in the diffusion of misinformation on social media, Res. Politics, 6, 2, 1-8 (2019)
[4] Aleja, D.; Criado, R.; García del Amo, A. J.; Pérez, Á.; Romance, M., Non-backtracking PageRank: From the classic model to Hashimoto matrices, Chaos, Solitons Fractals, 126, 283 (2019)
[5] Arrigo, F. and Tudisco, F., “Multi-dimensional, multilayer, nonlinear and dynamic HITS,” in Proceedings of the SIAM International Conference on Data Mining (SIAM<?xpag doi:10.1137/1.9781611975673.42?>, 2019), pp. 369-377.
[6] Barabási, A. L.; Albert, R., Emergence of scaling in random networks, Science, 286, 5439, 509-512 (1999) · Zbl 1226.05223
[7] Bavelas, A., A mathematical model for group structure, Hum. Organ., 7, 16-30 (1948)
[8] Benson, A. R., Three hypergraph eigenvector centralities, SIAM J. Math. Data Sci., 1, 2, 293-312 (2019)
[9] Berlingerio, M., Coscia, M., Giannotti, F., Monreale, A., and Pedreschi, D., “Foundations of multidimensional network analysis,” in 2011 International Conference on Advances in Social Networks Analysis and Mining (Kaohsiung, 2011), pp. 485-489.
[10] Boccaletti, S.; Bianconi, G.; Criado, R.; del Genio, C. I.; Gómez-Gardeñes, J.; Romance, M.; Sendiña-Nadal, I.; Wang, Z.; Zanin, M., The structure and dynamics of multilayer networks, Phys. Rep., 544, 1, 1-122 (2014)
[11] Boldi, P.; Vigna, S., Axioms for centrality, Internet Math., 10, 3-4, 222-262 (2014)
[12] Boldi, P.; Santini, M.; Vigna, S., PageRank: Functional dependencies, ACM Trans. Inf. Syst., 27, 4, 19:1-19:23 (2009)
[13] Bonacich, P., Factoring and weighting approaches to status scores and clique identification, J. Math. Sociol., 2, 1, 113-120 (1972)
[14] Borgatti, S. P.; Everett, M. G., A graph-theoretic perspective on centrality, Soc. Networks, 28, 4, 466-484 (2006)
[15] Buzzanca, M.; Carchiolo, V.; Longheu, A.; Malgeri, M.; Mangioni, G., Black hole metric: Overcoming the PageRank normalization problem, Inf. Sci., 438, 58-72 (2018)
[16] De Domenico, M.; Solé-Ribalta, A.; Omodei, E.; Gómez, S.; Arenas, A., Ranking in interconnected multilayer networks reveals versatile nodes, Nat. Commun., 6, 6868 (2015)
[17] DeFord, D. R.; Pauls, S. D., A new framework for dynamical models on multiplex networks, J. Complex Networks, 6, 353-381 (2018)
[18] Del Corso, G. M.; Romani, F., A multi-class approach for ranking graph nodes: Models and experiments with incomplete data, Inf. Sci., 329, 619-637 (2016)
[19] Dunford, N.; Schwartz, J. T., Linear Operators. Part I (1988), Wiley Classics Library, John Wiley & Sons, Inc.: Wiley Classics Library, John Wiley & Sons, Inc., New York
[20] Erdös, P.; Rényi, A., On random graphs I, Publ. Math. Debrecen, 6, 290-297 (1959) · Zbl 0092.15705
[21] Estrada, E.; Silver, G., Accounting for the role of long walks on networks via a new matrix function, J. Math. Anal. Appl., 449, 2, 1581-1600 (2017) · Zbl 1355.05233
[22] Festinger, L., The analysis of sociograms using matrix algebra, Hum. Relat., 2, 2, 153-158 (1949)
[23] Fiedler, M., A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czech. Math. J., 25, 4, 619-633 (1975) · Zbl 0437.15004
[24] Ford, L. R., Network Flow Theory (RAND Corporation, Santa Monica, CA, 1956).
[25] Fortunato, S., Boguñá, M., Flammini, A., and Menczer, F., “Approximating PageRank from in-degree,” in Algorithms and Models for the Web-Graph. WAW 2006, Lecture Notes in Computer Science Vol. 4936, edited by W. Aiello, A. Broder, J. Janssen, and E. Milios (Springer, Berlin, 2006). · Zbl 1142.68311
[26] Freeman, L. C., Centrality in social networks: Conceptual clarification, Soc. Networks, 1, 215-239 (1979)
[27] Ermann, L.; Frahm, K. M.; Shepelyansky, D. L., Google matrix analysis of directed networks, Rev. Mod. Phys., 87, 1261 (2015)
[28] Frahm, K. M.; Shepelyanskym, D. L., Ising-PageRank model of opinion formation on social networks, Phys. A Stat. Mech. Appl., 526, 121069 (2019)
[29] García, E.; Pedroche, F.; Romance, M., On the localization of the personalized PageRank of complex networks, Linear Algebra Appl., 439, 640-652 (2013) · Zbl 1282.91277
[30] Gleich, D. F., Constantine, P. G., Flaxman, A. D., and Gunawardana, A., “Tracking the random surfer: Empirically measured teleportation parameters in pageRank,” in Proceedings of the 19th International Conference on World Wide Web Pages (ACM, 2010), pp. 381-390.
[31] Gu, C.; Jiang, X.; Shao, C.; Chen, Z., A GMRES-power algorithm for computing PageRank problems, J. Comput. Appl. Math., 343, 113-123 (2018) · Zbl 06892258
[32] Halu, A.; Mondragón, R. J.; Panzarasa, P.; Bianconi, G., Multiplex PageRank, PLoS ONE, 8, 10, e78293 (2013)
[33] Horn, R. A.; Johnson, C. R., Topics in Matrix Analysis (1991), Cambridge University Press: Cambridge University Press, New York · Zbl 0729.15001
[34] Iacovacci, J.; Bianconi, G., Extracting information from multiplex networks, Chaos, 26, 065306 (2016)
[35] Iacovacci, J.; Rahmede, C.; Arenas, A.; Bianconi, G., Functional multiplex PageRank, Europhys. Lett., 116, 28004 (2016)
[36] Iván, G.; Grolmusz, V., When the web meets the cell: Using personalized PageRank for analyzing protein interaction networks, Bioinformatics, 27, 3, 405-407 (2011)
[37] Kalecky, K.; Cho, Y. R., PrimAlign: PageRank-inspired Markovian alignment for large biological networks, Bioinformatics, 34, 13, 537-546 (2018)
[38] Katz, L., Psychometrika, 18, 39 (1953) · Zbl 0053.27606
[39] Kruskal, J. B., “On the shortest spanning subtree of a graph and the traveling salesman problem,” in Proceedings of the American Mathematical Society (1956), Vol. 7, No. 1, pp. 48-50. · Zbl 0070.18404
[40] Langville, A. N.; Meyer, C. D., Deeper inside PageRank, Internet Math., 1, 3, 335-380 (2004) · Zbl 1098.68010
[41] Liu, Y. Y.; Slotine, J. J.; Barabasi, A. L., Controllability of complex networks, Nature, 473, 7346, 167-173 (2011)
[42] Lv, L.; Zhang, K.; Zhang, T.; Bardou, D.; Zhang, J.; Cai, Y., PageRank centrality for temporal networks, Phys. Lett. A, 383, 12, 1215-1222 (2019)
[43] McAuley, J.; Leskovec, J., Learning to discover social circles in ego networks, Adv. Neural Inf. Process. Syst., 1, 539-547 (2012)
[44] Massucci, F. A.; Docampo, D., Measuring the academic reputation through citation networks via PageRank, J. Informetr., 13, 1, 185-201 (2019)
[45] Masuda, N.; Porter, M. A.; Lambiotte, R., Random walks and diffusion on networks, Phys. Rep., 716-717, 1-58 (2017) · Zbl 1377.05180
[46] Migallón, H.; Migallón, V.; Penadés, J., Parallel two-stage algorithms for solving the PageRank problem, Adv. Eng. Softw., 125, 188-199 (2018)
[47] Newman, M., Networks: An Introduction (2010), Oxford University Press
[48] Nicosia, V.; Criado, R.; Romance, M.; Russo, G.; Latora, V., Controlling centrality in complex networks, Sci. Rep., 2, 218 (2012)
[49] Page, L., Brin, S., Motwani, R., and Winograd, T., “The PageRank citation ranking: Bridging order to the web,” Tech. Rep. 1999-66, Stanford University, 1998.
[50] Pedroche, F.; García, E.; Romance, M.; Criado, R., Sharp estimates for the personalized multiplex PageRank, J. Comput. Appl. Math., 330, 1030-1040 (2018) · Zbl 1380.68025
[51] Pedroche, F.; Tortosa, L.; Vicent, J. F., An eigenvector centrality for multiplex networks with data, Symmetry, 11, 6, 763 (2019)
[52] Pedroche, F.; Romance, M.; Criado, R., A biplex approach to PageRank centrality: From classic to multiplex networks, Chaos, 26, 065301 (2016) · Zbl 1374.68136
[53] Sciarra, C.; Chiarotti, G.; Laio, F.; Ridolfi, L., A change of perspective in network centrality, Sci. Rep., 8, 15269 (2018)
[54] Scholz, M.; Pfeiffer, J.; Rothlauf, F., Using PageRank for non-personalized default rankings in dynamic markets, Eur. J. Oper. Res., 260, 1, 388-401 (2017) · Zbl 1402.90069
[55] Shen, Y.; Gu, C.; Zhao, P., Structural vulnerability assessment of multi-energy system using a PageRank algorithm, Energy Procedia, 158, 6466-6471 (2019)
[56] Shen, Z. L.; Huang, T. Z.; Carpentieri, B.; Wen, C.; Gu, X. M.; Tan, X. Y., Off-diagonal low-rank preconditioner for difficult PageRank problems, J. Comput. Appl. Math., 346, 456-470 (2019) · Zbl 1402.65028
[57] Shepelyansky, D. L.; Zhirovc, O. V., Towards Google matrix of brain, Phys. Lett. A, 374, 3206-3209 (2010) · Zbl 1238.62114
[58] Sola, L.; Romance, M.; Criado, R.; Flores, J.; Garcia del Amo, A.; Boccaletti, S., Eigenvector centrality of nodes in multiplex networks, Chaos, 23, 033131 (2013) · Zbl 1323.05117
[59] Tian, Z.; Liu, Y.; Zhang, Y.; Tian, M., The general inner-outer iteration method based on regular splittings for the PageRank problem, Appl. Math. Comput., 356, 479-501 (2019) · Zbl 1429.65079
[60] Timm, C. and Perez, R., “Social networking infrastructure attacks,” in Seven Deadliest Social Network Attacks, edited by C. Timm and R. Perez (Syngress, 2010), pp. 1-22.
[61] Watts, D. J.; Strogatz, S. H., Collective dynamics of small-world networks, Nature, 393, 6684, 440 (1998) · Zbl 1368.05139
[62] Yun, T. S.; Jeong, D.; Park, S., Too central to fail systemic risk measure using PageRank algorithm, J. Econ. Behav. Organ., 162, 251-272 (2019)
[63] See file facebook.tar.gz in http://snap.stanford.edu/data/ego-Facebook.html with information about a Dataset of Facebook users’ network collected from survey participants using a Facebook app.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.