Partenaires

CNRS
UPS



Rechercher

Sur ce site

Sur le Web du CNRS


Accueil du site > Recrutement > Thèses au LPT > Applications du chaos quantique à l’étude de la matrice de Google de réseaux dirigés

Applications du chaos quantique à l’étude de la matrice de Google de réseaux dirigés

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)irsamc.ups-tlse.fr ; +33 (0)5 61 55 65 63)

Site Web : http://quantware.ups-tlse.fr/

Ces dernières années, les réseaux sociaux et de communication sont devenus de plus en plus importants. De plus, les réseaux apparaissent dans de nombreux contextes scientifiques comme la génétique, la linguistique, les systèmes dynamiques... Le World Wide Web par exemple contient environ 50 milliards de pages Web indexées, et la classification et la recherche d’information y représente une tâche colossale que la société doit effectuer tous les jours. Plusieurs moteurs de recherche ont été développés par des compagnies privées comme Google ou Yahoo !, qui sont utilisés intensivement par les usagers d’internet. Pour manipuler d’aussi énormes bases de données, des outils mathématiques fondamentaux et des algorithmes appropriés doivent être développés. L’algorithme du PageRank qui a été à la base du développement du moteur de recherche de Google utilise les propriétés d’une matrice de très grande taille -la matrice de Google- pour produire un vecteur qui assigne un coefficient d’importance aux différents noeuds du réseau et permet donc de les ordonner.

L’équipe de Toulouse possède une longue expérience d’utilisation des outils du chaos quantique dans différents domaines de la physique (matière condensée, systèmes dynamiques, information quantique, atomes froids...). En effet, le domaine du chaos quantique concerne l’étude de fonctions d’onde quantiques complexes, au moyen d’outils comme la théorie des matrices aléatoires, et peut éclairer de nombreux problèmes d’ondes complexes ou de vecteurs propres de grandes matrices. Récemment, l’équipe a appliqué de telles techniques à l’étude de l’algorithme du PageRank de Google, qui est directement relié aux propriétés mathématiques d’opérateurs de Perron-Frobenius et de chaînes de Markov. Des études spécifiques sur les propriétés de localisation des matrices de Google ont permis de montrer qu’une transition de délocalisation était présente dans le spectre des matrices de Google, montrant en particulier que l’algorithme de PageRank peut échouer pour certains types de réseaux [1]. D’autres études ont appliqué les techniques de PageRank aux systèmes dynamiques [2], au commerce mondial [3], aux réseaux sociaux [4], aux citatations scientifiques [5], au jeu de go [6] et aux articles de Wikipédia [7]. L’équipe a développé des outils numériques spécifiques fondés sur la méthode d’Arnoldi pour trouver le spectre de matrices non-hermitiennes très larges, et les a utilisés pour explorer de nouveaux types de réseaux comme les appels de procédure du noyau de Linux. L’expertise de l’équipe a été reconnue par l’obtention d’un contrat européen dont elle est coordinateur.

Le but du travail de doctorat sera de poursuivre ces études, utilisant l’expertise accumulée par l’équipe, pour construire de nouveaux outils d’analyse et de recherche pour les réseaux dirigés, incluant le classement des sites à deux dimensions, l’analyse du spectre des matrices de Google et ses relations avec la structure des réseaux, l’applicabilité de la loi de Weyl fractale aux modes propres des matrices de Google. Ces outils seront appliqués en parallèle à des exemples spécifiques de réseaux réels comme par exemple le World Wide Web, les articles de Wikipedia, les appels de procédure du noyau de Linux, les réseaux associés aux systèmes dynamiques, le commerce mondial, le réseau du jeu de go et les réseaux sociaux.

Le doctorat sera encadré par une équipe de chercheurs du Laboratoire de Physique Théorique de l’IRSAMC, Toulouse. Un stage de M2 est aussi possible.

Références :

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