PageRank is a ranking method that assigns scores to web pages using the limit distribution of a random walk on the web graph. A fibration of graphs is a morphism that is a local isomorphism of in-neighbourhoods, much in the same way a covering projection is a local isomorphism of neighbourhoods. We show that a deep connection relates fibrations and Markov chains with restart, a particular kind of Markov chains that include the PageRank one as a special case. This fact provides constraints on the values that PageRank can assume. Using our results, we show that a recently defined class of graphs that admit a polynomial-time isomorphism algorithm based on the computation of PageRank is really a subclass of fibration-prime graphs, which possess simple, entirely discrete polynomial-time isomorphism algorithms based on classical techniques for graph isomorphism. We discuss efficiency issues in the implementation of such algorithms for the particular case of web graphs, in which
Mots-clés : graph fibrations, pagerank, Markov chain with restart
@article{ITA_2006__40_2_227_0,
author = {Boldi, Paolo and Lonati, Violetta and Santini, Massimo and Vigna, Sebastiano},
title = {Graph fibrations, graph isomorphism, and pagerank},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {227--253},
publisher = {EDP-Sciences},
volume = {40},
number = {2},
year = {2006},
doi = {10.1051/ita:2006004},
mrnumber = {2252637},
zbl = {1112.68002},
language = {en},
url = {https://numdam.org/articles/10.1051/ita:2006004/}
}
TY - JOUR AU - Boldi, Paolo AU - Lonati, Violetta AU - Santini, Massimo AU - Vigna, Sebastiano TI - Graph fibrations, graph isomorphism, and pagerank JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 227 EP - 253 VL - 40 IS - 2 PB - EDP-Sciences UR - https://numdam.org/articles/10.1051/ita:2006004/ DO - 10.1051/ita:2006004 LA - en ID - ITA_2006__40_2_227_0 ER -
%0 Journal Article %A Boldi, Paolo %A Lonati, Violetta %A Santini, Massimo %A Vigna, Sebastiano %T Graph fibrations, graph isomorphism, and pagerank %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 227-253 %V 40 %N 2 %I EDP-Sciences %U https://numdam.org/articles/10.1051/ita:2006004/ %R 10.1051/ita:2006004 %G en %F ITA_2006__40_2_227_0
Boldi, Paolo; Lonati, Violetta; Santini, Massimo; Vigna, Sebastiano. Graph fibrations, graph isomorphism, and pagerank. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 227-253. doi : 10.1051/ita:2006004. https://numdam.org/articles/10.1051/ita:2006004/
[1] , and, PageRank as a function of the damping factor, in Proc. of the Fourteenth International World Wide Web Conference. ACM Press. Chiba, Japan (2005) 557-566.
[2] and, Fibrations of graphs. Discrete Math. 243 (2002) 21-66. | Zbl
[3] and, The WebGraph framework I: Compression techniques, in Proc. of the Thirteenth International World Wide Web Conference. ACM Press, Manhattan, USA (2004) 595-601.
[4] and, Partitioning a graph in
[5] and, An efficient algorithm for graph isomorphism. J. Assoc. Comput. Mach. 17 (1970) 51-64. | Zbl
[6] , The eigenvalues of the google matrix. Technical Report LiTH-MAT-R-04-01, Department of Mathematics, Linköping University, 2004. Available at arXiv:math/0401177.
[7] and, Arnoldi-type algorithms for computing stationary distribution vectors, with application to PageRank, Technical Report SCCM-04-15, Stanford University Technical Report (2004).
[8] , and, Exact and approximate graph matching using random walks. IEEETPAMI: IEEE Trans. Pattern Anal. Machine Intelligence 27 (2005) 1100-1111.
[9] and, Topological Graph Theory. Series in Discrete Mathematics and Optimization, Wiley-Interscience (1987). | MR | Zbl
[10] , Technique de descente et théorèmes d'existence en géométrie algébrique, I. Généralités. Descente par morphismes fidèlement plats. Seminaire Bourbaki 190 (1959-1960). | Numdam | Zbl
[11] , Efficient computation of PageRank. Technical Report 31, Stanford University Technical Report, October 1999. Available at http://dbpubs.stanford.edu/pub/1999-31.
[12] , Topic-sensitive pagerank, in The eleventh International Conference on World Wide Web Conference. ACM Press (2002) 517-526.
[13] and, The second eigenvalue of the Google matrix. Technical Report 20, Stanford University Technical Report, March 2003. Available at http://dbpubs.stanford.edu/pub/2003-20.
[14] , and, Front-divisors of trees. Acta Math. Univ. Comenian. (N.S.) 61 (1992) 69-84. | Zbl
[15] , An
[16] , Finite Markov Processes and Their Applications. John Wiley & Sons (1980). | MR | Zbl
[17] ,, and, Exploiting the block structure of the web for computing PageRank. Technical Report 17, Stanford University Technical Report, March 2003. Available at http://dbpubs.stanford.edu/pub/2003-17.
[18] ,, and, Extrapolation methods for accelerating PageRank computations, in Proceedings of the twelfth international conference on World Wide Web. ACM Press (2003) 261-270.
[19] , Perturbation Theory for Linear Operators. Springer-Verlag, second edition (1976). | MR | Zbl
[20] , Random walks on graphs: A survey, in Combinatorics, Paul Erdős is Eighty, Vol. 2, Bolyai Society Mathematical Studies, 1993, in Proceedings of the Meeting in honour of P. Erdős, Keszthely, Hungary 7 (1993) 1-46.
[21] , and, A fast two-stage algorithm for computing PageRank and its extensions. Technical Report SCCM-03-15, Stanford University Technical Report (2003). Available at http://www-sccm.stanford.edu/pub/sccm/sccm03-15_2.pdf.
[22] and, An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge UK (1995). | MR | Zbl
[23] , Practical graph isomorphism. Congressus Numerantium 30 (1981) 45-87. | Zbl
[24] , Matrix analysis and applied linear algebra. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2000). | MR | Zbl
[25] , Constant-to-one and onto global maps of homomorphisms between strongly connect graphs. Ergod. Th. & Dynam. Sys. 3 (1983) 387-413. | Zbl
[26] , Universal covers of graphs: Isomorphism to depth
[27] ,, and, The PageRank citation ranking: Bringing order to the web. Technical Report 66, Stanford University, 1999. Available at http://dbpubs.stanford.edu/pub/1999-66.
[28] , and, Spectra of Graphs. Academic Press (1978). | MR
[29] . Perturbation theory and finite markov chains. J. Appl. Probab. 5 (1968) 401-413. | Zbl
[30] , Non-negative matrices and Markov chains. Springer-Verlag, New York (1981). | Zbl
[31] , GIT - A heuristic program for testing pairs of directed line graphs for isomorphism. Comm. ACM 7 (1964) 26-34. | Zbl
[32] , A guided tour in the topos of graphs. Technical Report 199-97, Università di Milano, Dipartimento di Scienze dell'Informazione, 1997. Available at http://vigna.dsi.unimi.it/ftp/papers/ToposGraphs.pdf.
[33] , Functional Analysis. Springer-Verlag, (1980), Sixth Edition. | MR
Cité par Sources :
