Graph fibrations, graph isomorphism, and pagerank
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 227-253.

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 $O\left(n\right)$ space occupancy (where $n$ is the number of nodes) may be acceptable, but $O\left(m\right)$ is not (where $m$ is the number of arcs).

DOI : https://doi.org/10.1051/ita:2006004
Classification : 05C50,  05C85,  05C60,  94C15,  60J10,  15A51
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},
zbl = {1112.68002},
mrnumber = {2252637},
language = {en},
url = {http://www.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
DA  - 2006///
SP  - 227
EP  - 253
VL  - 40
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2006004/
UR  - https://zbmath.org/?q=an%3A1112.68002
UR  - https://www.ams.org/mathscinet-getitem?mr=2252637
UR  - https://doi.org/10.1051/ita:2006004
DO  - 10.1051/ita:2006004
LA  - en
ID  - ITA_2006__40_2_227_0
ER  - 
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. http://www.numdam.org/articles/10.1051/ita:2006004/

[1] P. Boldi, M. Santini and S. Vigna, 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] P. Boldi and S. Vigna, Fibrations of graphs. Discrete Math. 243 (2002) 21-66. | Zbl 0988.05073

[3] P. Boldi and S. Vigna, The WebGraph framework I: Compression techniques, in Proc. of the Thirteenth International World Wide Web Conference. ACM Press, Manhattan, USA (2004) 595-601.

[4] A. Cardon and M. Crochemore, Partitioning a graph in $O\left(|A|{log}_{2}|V|\right)$. Theoret. Comput. Sci. 19 (1982) 85-98. | Zbl 0478.68067

[5] D.G. Corneil and C.C. Gotlieb, An efficient algorithm for graph isomorphism. J. Assoc. Comput. Mach. 17 (1970) 51-64. | Zbl 0199.27801

[6] L. Eldén, 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] G.H. Golub and C. Greif, Arnoldi-type algorithms for computing stationary distribution vectors, with application to PageRank, Technical Report SCCM-04-15, Stanford University Technical Report (2004).

[8] M. Gori, M. Maggini and L. Sarti, Exact and approximate graph matching using random walks. IEEETPAMI: IEEE Trans. Pattern Anal. Machine Intelligence 27 (2005) 1100-1111.

[9] J.L. Gross and T.W. Tucker, Topological Graph Theory. Series in Discrete Mathematics and Optimization, Wiley-Interscience (1987). | MR 898434 | Zbl 0621.05013

[10] A. Grothendieck, 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 0229.14007

[11] T.H. Haveliwala, Efficient computation of PageRank. Technical Report 31, Stanford University Technical Report, October 1999. Available at http://dbpubs.stanford.edu/pub/1999-31.

[12] T.H. Haveliwala, Topic-sensitive pagerank, in The eleventh International Conference on World Wide Web Conference. ACM Press (2002) 517-526.

[13] T.H. Haveliwala and S.D. Kamvar, 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] P. Híc, R. Nedela and S. Pavlíková, Front-divisors of trees. Acta Math. Univ. Comenian. (N.S.) 61 (1992) 69-84. | Zbl 0821.05041

[15] J.E. Hopcroft, An $nlogn$ algorithm for minimizing states in a finite automaton, in Theory of Machines and Computations, edited by Z. Kohavi and A. Paz. Academic Press (1971).

[16] M. Iosifescu, Finite Markov Processes and Their Applications. John Wiley & Sons (1980). | MR 587116 | Zbl 0436.60001

[17] S.D. Kamvar, T.H. Haveliwala, C.D. Manning and G.H. Golub, 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] S.D. Kamvar, T.H. Haveliwala, C.D. Manning and G.H. Golub, Extrapolation methods for accelerating PageRank computations, in Proceedings of the twelfth international conference on World Wide Web. ACM Press (2003) 261-270.

[19] T. Kato, Perturbation Theory for Linear Operators. Springer-Verlag, second edition (1976). | MR 407617 | Zbl 0342.47009

[20] L. László, 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] C. Pan-Chi Lee, G.H. Golub and S.A. Zenios, 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] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge UK (1995). | MR 1369092 | Zbl 1106.37301

[23] B.D. Mckay, Practical graph isomorphism. Congressus Numerantium 30 (1981) 45-87. | Zbl 0521.05061

[24] C.D. Meyer, Matrix analysis and applied linear algebra. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2000). | MR 1777382 | Zbl 0962.15001

[25] M. Nasu, Constant-to-one and onto global maps of homomorphisms between strongly connect graphs. Ergod. Th. & Dynam. Sys. 3 (1983) 387-413. | Zbl 0544.05029

[26] N. Norris, Universal covers of graphs: Isomorphism to depth $n-1$ implies isomorphism to all depths. Discrete Appl. Math. 56 (1995) 61-74. | Zbl 0815.68074

[27] L. Page, S. Brin, R. Motwani and T. Winograd, 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] D.M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs. Academic Press (1978). | MR 572262

[29] J.P. Schweitzer. Perturbation theory and finite markov chains. J. Appl. Probab. 5 (1968) 401-413. | Zbl 0196.19803

[30] E. Seneta, Non-negative matrices and Markov chains. Springer-Verlag, New York (1981). | Zbl 0471.60001

[31] S.H. Unger, GIT - A heuristic program for testing pairs of directed line graphs for isomorphism. Comm. ACM 7 (1964) 26-34. | Zbl 0123.33710

[32] S. Vigna, 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] K. Yosida, Functional Analysis. Springer-Verlag, (1980), Sixth Edition. | MR 617913

Cité par Sources :