In this work we introduce and study a nonlocal version of the PageRank. In our approach, the random walker explores the graph using longer excursions than just moving between neighboring nodes. As a result, the corresponding ranking of the nodes, which takes into account a long-range interaction between them, does not exhibit concentration phenomena typical of spectral rankings which take into account just local interactions. We show that the predictive value of the rankings obtained using our proposals is considerably improved on different real world problems.
Keywords: Complex network, nonlocal dynamics, Markov chain, Perron–Frobenius
@article{M2AN_2021__55_1_77_0,
author = {Cipolla, Stefano and Durastante, Fabio and Tudisco, Francesco},
title = {Nonlocal pagerank},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis },
pages = {77--97},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {1},
doi = {10.1051/m2an/2020071},
mrnumber = {4216832},
language = {en},
url = {https://www.numdam.org/articles/10.1051/m2an/2020071/}
}
TY - JOUR AU - Cipolla, Stefano AU - Durastante, Fabio AU - Tudisco, Francesco TI - Nonlocal pagerank JO - ESAIM: Mathematical Modelling and Numerical Analysis PY - 2021 SP - 77 EP - 97 VL - 55 IS - 1 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/m2an/2020071/ DO - 10.1051/m2an/2020071 LA - en ID - M2AN_2021__55_1_77_0 ER -
%0 Journal Article %A Cipolla, Stefano %A Durastante, Fabio %A Tudisco, Francesco %T Nonlocal pagerank %J ESAIM: Mathematical Modelling and Numerical Analysis %D 2021 %P 77-97 %V 55 %N 1 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/m2an/2020071/ %R 10.1051/m2an/2020071 %G en %F M2AN_2021__55_1_77_0
Cipolla, Stefano; Durastante, Fabio; Tudisco, Francesco. Nonlocal pagerank. ESAIM: Mathematical Modelling and Numerical Analysis , Tome 55 (2021) no. 1, pp. 77-97. doi: 10.1051/m2an/2020071
[1] and , A survey of link prediction in social networks. In: Social Network Data Analytics. Springer, Boston (2011) 243–275. | MR | DOI
[2] , , and , Non-backtracking walk centrality for directed networks. J. Complex Networks 6 (2017) 54–78. | MR | DOI
[3] , and , A framework for second order eigenvector centralities and clustering coefficients. Proc. R. Soc. A 476 (2020) 20190724. | MR | DOI
[4] , Three hypergraph eigenvector centralities. SIAM J. Math. Data Sci. 1 (2019) 293–312. | MR | DOI
[5] , and , Higher-order organization of complex networks. Science 353 (2016) 163–166. | DOI
[6] , and , The spacey random walk: a stochastic process for higher-order data. SIAM Rev. 59 (2017) 321–345. | MR | DOI
[7] and , Total communicability as a centrality measure. J. Complex Networks 1 (2013) 124–149. | DOI
[8] and , Nonnegative Matrices in the Mathematical Sciences. In: Vol. 9 of Classics in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1994). | MR | Zbl
[9] and , The PageRank vector: properties, computation, approximation, and acceleration. SIAM J. Matrix Anal. Appl. 28 (2006) 551–575. | MR | Zbl | DOI
[10] , , , , , and , Emergence of network features from multiplexity. Sci. Rep. 3 (2013) 1344. | DOI
[11] , , and , Spectral properties of hypergraph Laplacian and approximation algorithms. J. ACM 65 (2018) 1–48. | MR | DOI
[12] , A class of graph-geodetic distances generalizing the shortest-path and the resistance distances. Disc. Appl. Math. 159 (2011) 295–302. | MR | Zbl | DOI
[13] , The graph bottleneck identity. Adv. Appl. Math. 47 (2011) 403–413. | MR | Zbl | DOI
[14] and , Comparison of perturbation bounds for the stationary distribution of a Markov chain. Linear Algebra App. 335 (2001) 137–150. | MR | Zbl | DOI
[15] , and , Euler-Richardson method preconditioned by weakly stochastic matrix algebras: a potential contribution to Pagerank computation. Electron. J. Linear Algebra 32 (2017) 254–272. | MR | DOI
[16] , and , Extrapolation methods for fixed-point multilinear PageRank computations. Numer. Linear Algebra App. 27 (2020) e2280. | MR | DOI
[17] , and , Shifted and extrapolated power methods for tensor -eigenpairs. Electron. Trans. Numer. Anal. 53 (2020) 1–27. | MR | DOI
[18] and , Complex Networks: Structure, Robustness and Function. Cambridge University Press (2010). | Zbl | DOI
[19] and , The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38 (2011) 1–25. | MR | DOI
[20] , , and , Navigability of interconnected networks under random failures. Proc. Natl. Acad. Sci. 111 (2014) 8351–8356. | MR | DOI
[21] , and , Fast PageRank computation via a sparse linear system. Internet Math. 2 (2005) 251–273. | MR | Zbl | DOI
[22] , Network centrality of metro systems. PloS one 7 (2012) e40575. | DOI
[23] , and , Sparse matrix test problems. ACM Trans. Math. Softw. 15 (1989) 1–14. | MR | Zbl | DOI
[24] , Path Laplacian matrices: introduction and application to the analysis of consensus in networks. Linear Algebra App. 436 (2012) 3373–3391. | MR | Zbl | DOI
[25] , The Structure of Complex Networks: Theory and Applications. Oxford University Press (2012). | Zbl
[26] , , , , , and , Random multi-hopper model: super-fast random walks on graphs. J. Complex Networks 6 (2017) 382–403. | MR | DOI
[27] , , and , Path Laplacian operators and superdiffusive processes on graphs. I. One-dimensional case. Linear Algebra App. 523 (2017) 307–334. | MR | DOI
[28] , , and , Path Laplacian operators and superdiffusive processes on graphs. II. Two-dimensional lattice. Linear Algebra App. 555 (2018) 373–397. | MR | DOI
[29] , and , Comparing top k lists. SIAM J. Disc. Math. 17 (2003) 134–160. | MR | Zbl | DOI
[30] and , A modularity based spectral method for simultaneous community and anti-community detection. Linear Algebra App. 542 (2018) 605–623. | MR | DOI
[31] and , Ergodicity coefficients for higher-order stochastic processes. SIAM J. Math. Data Sci. 2 (2020) 740–769. | MR | DOI
[32] , Algorithm 97: shortest path. Commun. ACM 5 (1962) 345. | DOI
[33] and , Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99 (2002) 7821–7826. | MR | Zbl | DOI
[34] and , An Arnoldi-type algorithm for computing PageRank. BIT Numer. Math. 46 (2006) 759–771. | MR | Zbl | DOI
[35] , A matrix perturbation view of the small world phenomenon. SIAM Rev. 49 (2007) 91–108. | MR | Zbl | DOI
[36] , and , Engineering a scalable high quality graph partitioner. In: 2010 IEEE International Symposium on Parallel Distributed Processing (IPDPS) 2010 1–12.
[37] , Efficient algorithms for shortest paths in sparse networks. J. ACM 24 (1977) 1–13. | MR | Zbl | DOI
[38] , On a question concerning condition numbers for Markov chains. SIAM J. Matrix Anal. App. 23 (2002) 1109–1119. | MR | Zbl | DOI
[39] , , , , and , Towards design principles for optimal transport networks. Phys. Rev. Lett. 104 (2010) 018701. | DOI
[40] , and , Optimizing generalized pagerank methods for seed-expansion community detection, edited by , , , , and . In: Vol. 32 of Advances in Neural Information Processing Systems. Curran Associates, Inc. (2019) 11710–11721.
[41] and , The link-prediction problem for social networks. J. Am. Soc. Inf. Sci. Technol. 58 (2007) 1019–1031. | DOI
[42] , and , Localized eigenvectors from widely spaced matrix modifications. SIAM J. Disc. Math. 16 (2003) 479–498. | MR | Zbl | DOI
[43] , and , Localization and centrality in networks. Phys. Rev. E 90 (2014) 052808. | DOI
[44] , and , Fast solvers for two-dimensional fractional diffusion equations using rank structured matrices. SIAM J. Sci. Comput. 41 (2019) A2627–A2656. | MR | DOI
[45] and , Improved bounds for a condition number for Markov chains. Linear Algebra App. 386 (2004) 225–241. | MR | Zbl | DOI
[46] , Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74 (2006) 036104. | MR | DOI
[47] Office of Railand Road. Estimate of London’s tube station usage. https://dataportal.orr.gov.uk/statistics/usage/estimates-of-station-usage/.
[48] , , and , The PageRank citation ranking: bringing order to the web. Technical report, Stanford InfoLab (1999).
[49] , and , Centrality analysis for modified lattices. SIAM J. Matrix Anal. App. 38 (2017) 1055–1073. | MR | DOI
[50] and , On the stability of network indices defined by means of matrix functions. SIAM J. Matrix Anal. App. 39 (2018) 1521–1546. | MR | Zbl | DOI
[51] and , Long-range navigation on complex networks using Lévy random walks. Phys. Rev. E 86 (2012) 056110. | DOI
[52] and , Kleinberg navigation in fractal small-world networks. Phys. Rev. E 74 (2006) 017101. | DOI
[53] , , and , Core-periphery structure in networks. SIAM J. Appl. Math. 74 (2014) 167–190. | MR | Zbl | DOI
[54] and , The network data repository with interactive graph analytics and visualization. AAAI (2015).
[55] , Perturbation of the stationary distribution measured by ergodicity coefficients. Adv. Appl. Probab. 20 (1988) 228–230. | MR | Zbl | DOI
[56] , Localization of eigenvector centrality in networks with a cut vertex. Phys. Rev. E 99 (2019) 012315. | MR | DOI
[57] , and , Transportation networks for research. https://github.com/bstabler/TransportationNetworks
[58] , Centrality of an urban rail system. Urban Rail Transit 1 (2015) 249–256. | DOI
[59] , A note on certain ergodicity coeflcients. Spec. Matrices 3 (2015). | MR | Zbl
[60] and , A nonlinear spectral method for core–periphery detection in networks. SIAM J. Math. Data Sci. 1 (2019) 269–292. | MR | Zbl | DOI
[61] , and , DNA electrophoresis studied with the cage model. J. Comput. Phys. 180 (2002) 313–326. | Zbl | DOI
[62] , A theorem on boolean matrices. J. ACM 9 (1962) 11–12. | MR | Zbl | DOI
[63] , , and , Lévy walk navigation in complex networks: a distinct relation between optimal transport exponent and network dimension. Sci. Rep. 5 (2015) 1–9. | DOI
Cité par Sources :
