Nos tutelles

CNRS

Nom tutelle 1

Nos partenaires

Nom tutelle 2 Nom tutelle 3

Rechercher





Accueil > Recrutements > Offres de thèses > Archives

Etude des réseaux complexes dirigés à partir de leurs matrices de Google

Projet de thèse : Étude des réseaux complexes dirigés à partir de leurs matrices de Google

Les systèmes complexes forment naturellement d’immenses réseaux comportant un nombre très important de nœuds interconnectés. Par exemple, dans les systèmes vivants, les protéines agissent entre elles via des réactions chimiques, dans le cerveau, l’influx nerveux est transmis aux neurones par les axones, dans les réseaux sociaux, les participants sont liés par relations, dans le commerce international, les pays exportent/importent entre eux des produits. . .

De nos jours, l’archétype des réseaux complexes dirigés est le World Wide Web (WWW) contenant plus de 1012 pages reliées entre elles par des hyperliens. Ces réseaux, à la topologie extrêmement compliquée, possèdent des propriétés d’invariance d’échelle [1] et des propriétés dites de ultrasmall world [2]. L’étude des propriétés physiques de ces réseaux complexes dirigés nécessite l’utilisation d’outils statistiques spécifiques : en empruntant le paradigme du WWW, un surfeur aléatoire peut sauter d’un nœud A à un nœud B avec une certaine probabilité (chaîne de Markov). Les réseaux complexes dirigés peuvent alors être représentés par un opérateur stochastique (la matrice de Google appartenant à la classe des opérateurs de Perron-Frobenius [3].

L’analyse des réseaux complexes à l’aide de leurs matrices de Google permet de caractériser et classer les quantités massives d’informations enfouies dans ces réseaux, et cela de manière extrêmement efficace [4]. L’analyse de la matrice de Google a été réalisée pour des systèmes complexes très variés. On citera par exemple les réseaux WWW des universités d’Oxford et de Cambridge, Wikipédia, les réseaux sociaux tels Twitter, le commerce international, les séquences d’ADN, les réseaux de neurones, le noyau Linux. . . cf. la revue faite dans [5]. Récemment, le groupe de Physique Théorique et Astrophysique de l’Institut UTINAM et le Laboratoire de Physique Théorique de Toulouse ont proposé conjointement un classement mondial des Universités [6] en sondant 24 éditions linguistiques de Wikipédia. Ce travail a été remarqué par la presse internationale [7] dont Le Monde [8], MIT Technology Review [9], Times Higher Education [10]. . .

Au cours de ce projet, nous envisageons d’étudier prioritairement :

- les propriétés de la matrice de Google associée au réseau Wikipédia multilingues (18 millions de nœuds) construit en tirant profit des hyperliens existant entre les éditions linguistiques. Cette matrice de Google nous permettra d’étudier l’intrication entre les cultures et de déterminer les articles associés à des sujets formant des communautés cachées (corrélations à grande distance) ;

- les réseaux omiques, en particulier les réseaux de protéines en « interaction », où chaque protéine agit sur un ensemble d’autres protéines via une ou plusieurs fonctions inhibitrices, activatrices, régulatrices. . .
La matrice de Google est alors multifonctionnelle puisque la nature d’un lien directionnel varie suivant sa fonction. Le groupe de Physique Théorique et Astrophysique de l’Institut UTINAM a débuté une collaboration avec le groupe de Biologie Computationnelle des Systèmes du Cancer de l’Institut Curie (https://sysbio.curie.fr/) ayant pour but de faire -émerger de ces réseaux omiques les communautés de protéines responsables de certains cancers ;

- les réseaux d’Ulam associés aux systèmes dynamiques : la discrétisation de l’espace des phases permet de définir les nœuds du réseau d’Ulam, une orbite donnée passe alors par un certain nombre de nœuds définissant une chaîne de Markov. L’étude de celle-ci permet de définir des modes de fonctionnement du système dynamique. On cherchera en particulier à caractériser les systèmes dynamiques chaotiques et/ou dissipatifs empruntés aux domaines de l’astrophysique et de la physique atomique ;

- les récurrences de Poincaré pour les réseaux complexes tels que le WWW. Puisqu’un système dynamique peut être assimilé à un réseau, en retour on peut chercher à caractériser les propriétés dynamiques d’un réseau complexe ;

- la progression harmonique dans le Jazz et la musique classique en créant le réseau des degrés harmoniques d’un corpus composé d’oeuvres musicales d’un même compositeur. En considérant la succession de mots" harmoniques de n \lettres" (degrés), il est possible de définir des réseaux dont la complexité croît avec n. L’analyse harmonique de l’oeuvre d’un compositeur peut alors être entreprise à l’aide de la matrice de Google associée à ces réseaux. Il est alors possible de faire une analyse quantitative des différences harmoniques entre plusieurs compositeurs.

Ce travail de thèse se déroulera en étroite collaboration avec le Laboratoire de Physique Théorique de Toulouse. Le candidat sélectionné devra idéalement posséder un master de physique ou mathématiques, et de très bonnes aptitudes au codage (FORTRAN ou C++, et python).

Encadrants

José Lages Dima Shepelyansky
Maître de Conférences DR1 CNRS
jose.lages chez utinam.cnrs.fr dima chez irsamc.ups-tlse.fr
Institut UTINAM, UMR CNRS 6213 Laboratoire de Physique Théorique
Observatoire des Sciences de l’Univers THETA UMR CNRS 5152
Université de Franche-Comté, Besançon Université Paul Sabatier, Toulouse
PDF - 332.8 ko
Proposition de thèse J. Lagès

[1A.-L. Barabasi and R. Albert, "Emergence of scaling in random networks", Science, 286 :509-512 (1999)

[2R. Cohen and S. Havlin, "Scale-free networks are ultrasmall", Phys. Rev. Lett. 90, 058701 (2003)

[3A.N. Langville and C.D. Meyer, "Google’s PageRank and Beyond : The Science of Search Engine Rankings", Princeton University Press, 2006

[4Cette matrice est par exemple au cœur de l’algorithme de classement des pages du WWW par Google

[5L. Ermann, K. M. Frahm and D.L. Shepelyansky, "Google matrix analysis of directed networks", Rev. Mod.
Phys. 87, 1261 (2015)

[6J. Lages, A. Patt, D.L. Shepelyansky, "Wikipedia Ranking of World Universities", soumis à Eur. J. Phys.B, arXiv:1511.09021, les données ainsi que le classement sont disponibles à http://perso.utinam.cnrs.fr/~lages/datasets/WRWU/

[7La page http://perso.utinam.cnrs.fr/~lages/datasets/WRWU/press/Press.html recense 95 articles de presse dans 21 pays différents

[8Des Français inventent le classement Wikipédia des universités", Le Monde, December 18, 2015

[9"Wikipedia-Mining Algorithm Reveals World’s Most Influential Universities", MIT Technology Review, De
cember 7, 2015 ;Best of 2015 : Wikipedia-Mining Algorithm Reveals World’s Most Influential Universities",ibid., December 26, 2015

[10Wikipedia Ranking of World Universities : the top 100", Times Higher Education, December 15, 2015