Graph fibrations, graph isomorphism, and pagerank

Boldi, Paolo; Lonati, Violetta; Santini, Massimo; Vigna, Sebastiano

doi:10.1051/ita:2006004

Boldi, Paolo ; Lonati, Violetta ; Santini, Massimo ¹ ; Vigna, Sebastiano

¹ Dipartimento di Scienze Sociali, Cognitive e Quantitative, Università degli Studi di Modena e Reggio Emilia, Via Giglioli Valle, 42100 Reggio Emilia, Italy;

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

Résumé

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

MR Zbl

DOI : 10.1051/ita:2006004

Classification : 05C50, 05C85, 05C60, 94C15, 60J10, 15A51
Mots-clés : graph fibrations, pagerank, Markov chain with restart

Affiliations des auteurs :

Boldi, Paolo ; Lonati, Violetta ; Santini, Massimo ¹ ; Vigna, Sebastiano

¹ Dipartimento di Scienze Sociali, Cognitive e Quantitative, Università degli Studi di Modena e Reggio Emilia, Via Giglioli Valle, 42100 Reggio Emilia, Italy;

@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://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
SP  - 227
EP  - 253
VL  - 40
IS  - 2
PB  - EDP-Sciences
UR  - https://www.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://www.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://www.numdam.org/articles/10.1051/ita:2006004/

Bibliographie
Cité par

[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

[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 (| A | {log}_{2} | V |)$ . Theoret. Comput. Sci. 19 (1982) 85-98. | Zbl

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

[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 | Zbl

[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

[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

[15] J.E. Hopcroft, An $n log n$ 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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

[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

[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

[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

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

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

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

[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

Monteiro, Higor S.; Leifer, Ian; Reis, Saulo D. S.; Andrade, José S.; Makse, Hernan A. Fast algorithm to identify minimal patterns of synchrony through fibration symmetries in large directed networks, Chaos: An Interdisciplinary Journal of Nonlinear Science, Volume 32 (2022) no. 3 | DOI:10.1063/5.0066741
Boldi, Paolo; Furia, Flavio; Vigna, Sebastiano Spectral Rank Monotonicity on Undirected Networks, Complex Networks Their Applications X, Volume 1072 (2022), p. 234 | DOI:10.1007/978-3-030-93409-5_20
Bojchevski, Aleksandar; Gasteiger, Johannes; Perozzi, Bryan; Kapoor, Amol; Blais, Martin; Rózemberczki, Benedek; Lukasik, Michal; Günnemann, Stephan, Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining (2020), p. 2464 | DOI:10.1145/3394486.3403296
Holzmann, Helge; Anand, Avishek; Khosla, Megha Estimating PageRank deviations in crawled graphs, Applied Network Science, Volume 4 (2019) no. 1 | DOI:10.1007/s41109-019-0201-9
KhudaBukhsh, Wasiur R.; Auddy, Arnab; Disser, Yann; Koeppl, Heinz Approximate lumpability for Markovian agent-based models using local symmetries, Journal of Applied Probability, Volume 56 (2019) no. 3, p. 647 | DOI:10.1017/jpr.2019.44
Iscen, Ahmet; Avrithis, Yannis; Tolias, Giorgos; Furon, Teddy; Chum, Ondrej, 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition (2018), p. 7632 | DOI:10.1109/cvpr.2018.00796
Gao, Li; Lu, Yao; Zhang, Qin; Yang, Hong; Hu, Yue, 2016 International Joint Conference on Neural Networks (IJCNN) (2016), p. 4715 | DOI:10.1109/ijcnn.2016.7727819
Bourchtein, Andrei; Bourchtein, Ludmila On some analytical properties of a general PageRank algorithm, Mathematical and Computer Modelling, Volume 57 (2013) no. 9-10, p. 2248 | DOI:10.1016/j.mcm.2011.06.033
Boldi, Paolo; Rosa, Marco, 2012 Eighth Latin American Web Congress (2012), p. 48 | DOI:10.1109/la-web.2012.19
Baeza-Yates, Ricardo; Boldi, Paolo Web Structure Mining, Advanced Techniques in Web Intelligence - I, Volume 311 (2010), p. 113 | DOI:10.1007/978-3-642-14461-5_5
Giammarresi, Dora A Brief Excursion Inside the Class of Tiling Recognizable Two-Dimensional Languages, Developments in Language Theory, Volume 6224 (2010), p. 4 | DOI:10.1007/978-3-642-14455-4_2
Cicone, Antonio; Serra-Capizzano, Stefano Google PageRanking problem: The model and the analysis, Journal of Computational and Applied Mathematics, Volume 234 (2010) no. 11, p. 3140 | DOI:10.1016/j.cam.2010.02.005
Boldi, Paolo; Santini, Massimo; Vigna, Sebastiano PageRank, ACM Transactions on Information Systems, Volume 27 (2009) no. 4, p. 1 | DOI:10.1145/1629096.1629097
Boldi, Paolo; Posenato, Roberto; Santini, Massimo; Vigna, Sebastiano Traps and Pitfalls of Topic-Biased PageRank, Algorithms and Models for the Web-Graph, Volume 4936 (2008), p. 107 | DOI:10.1007/978-3-540-78808-9_10
Boldi, Paolo; Bonchi, Francesco; Castillo, Carlos; Donato, Debora; Gionis, Aristides; Vigna, Sebastiano, Proceedings of the 17th ACM conference on Information and knowledge management (2008), p. 609 | DOI:10.1145/1458082.1458163
Anselmo, Marcella; Madonia, Maria Deterministic Two-Dimensional Languages over One-Letter Alphabet, Algebraic Informatics, Volume 4728 (2007), p. 147 | DOI:10.1007/978-3-540-75414-5_9
Giammarresi, Dora Tiling Recognizable Two-Dimensional Languages, Algebraic Informatics, Volume 4728 (2007), p. 75 | DOI:10.1007/978-3-540-75414-5_5
Anselmo, Marcella; Giammarresi, Dora; Madonia, Maria From Determinism to Non-determinism in Recognizable Two-Dimensional Languages, Developments in Language Theory, Volume 4588 (2007), p. 36 | DOI:10.1007/978-3-540-73208-2_7

Cité par 18 documents. Sources : Crossref