Sur ce site

Sur le Web du CNRS

Accueil du site > Recrutement > Thèses au LPT > Applications of quantum chaos to the study of the Google matrix of directed networks

Applications of quantum chaos to the study of the Google matrix of directed networks

par Bertrand Georgeot - 15 octobre 2015

Toutes les versions de cet article : English , français

PhD advisors : Bertrand Georgeot & Dima Shepelyansky

Contact : Bertrand Georgeot (georgeot(at) ; +33 (0)5 61 55 65 63)

Site Web :

In the past few years, social and communication networks have become more and more important. In addition, networks appear in many scientific contexts such as genetics, linguistics, dynamical systems... The World Wide Web alone has about 50 billion indexed webpages, so that their classification and information retrieval becomes a formidable task which the society has to face everyday. Various search engines have been developed by private companies such as Google, Yahoo ! and others which are extensively used by Internet users. To handle such enormous databases, fundamental mathematical tools and algorithms should be developed. The PageRank algorithm which was at the basis of the development of the Google search engine uses the properties of a very large matrix -the Google matrix- to produce a vector which gives an importance value to the different nodes of the network and thus enables to rank them.

The Toulouse team has a long experience of using tools from quantum chaos in various domains of physics (condensed matter, dynamical systems, quantum information, cold atoms...). Indeed, the field of quantum chaos deals with the study of complex quantum wave functions, using tools such as the theory of random matrices, and can shed light on many problems involving complex waves phenomena and complex eigenvectors of large matrices. Recently, the team has applied such techniques to the study of the Google PageRank algorithm, which is directly linked to the mathematical properties of Perron-Frobenius operators and Markov chains. Specific studies of the localisation properties of the Google matrices enabled to show that localization transitions are present in the spectrum of Google matrices, showing in particular that the PageRank algorithm may fail for certain types of networks [1]. Other studies pioneered the application of PageRank techniques to dynamical systems [2], world trade [3], social networks [4], scientific citations [5], the game of go [6] and Wikipedia articles [7]. The team has developped specific numerical tools based on the Arnoldi method to find the spectrum of very large non hermitian matrices, and used them to explore new types of networks such as Linux kernel procedure call. Expertise of the team was recognized by the award of a European Contract of which the Toulouse team was coordinator.

The aim of the PhD work will be to further these studies, using the expertise accumulated by the team, in order to build new tools of analysis and ranking of directed networks, including two-dimensional ranking, analysis of the spectrum of Google matrices and its relationship with network structure, applicability of fractal Weyl law to eigenmodes of Google matrices. These tools will be applied in parallel to specific examples of real networks such as for example the World Wide Web, Wikipedia articles, procedure calls of Linux kernels, networks associated with dynamical systems, world trade, the game of go or social networks among others.

The PhD will be supervised by a team of researchers of the Laboratoire de Physique Théorique de l’IRSAMC, Toulouse. A training (``stage de M2’’) is also possible.

References :

[1] O.Giraud, B.Georgeot and D.L.Shepelyansky, "Delocalization transition for the Google matrix", Phys. Rev. E v.80, p.026107 (2009).

[2] D.L.Shepelyansky and O.V.Zhirov, "Google matrix and dynamical attractors", Phys. Rev. E v.81, p.036213 (2010).

[3] L.Ermann and D.L.Shepelyansky, "Ecological analysis of world trade", Phys. Lett. A v.377, p.250-256 (2013)

[4] K.M.Frahm and D.L.Shepelyansky, "Google matrix of Twitter", Eur. Phys. J. B v.85, p.355 (2012) (arXiv:1207.3414)

[5] K.M.Frahm, Y.-H.Eom and D.L.Shepelyansky, "Google matrix of the citation network of Physical Review", Phys. Rev. E v.89, p.052814 (2014) (arXiv:1310.5624)

[6] V.Kandiah, B.Georgeot and O.Giraud,"Move ordering and communities in complex networks describing the game of go ", Eur. Phys. J. B 87, 246 (2014)( arXiv:1405.6077)

[7] Y.-H.Eom, P.Aragon, D.Laniado, A.Kaltenbrunner, S.Vigna and D.L.Shepelyansky, "Interactions of cultures and top people of Wikipedia from ranking of 24 language editions", PLoS ONE 10(3) : e0114825 (2015)( arXiv:1405.7183)