Direction de recherche : Bénédicte LE GRAND

Co-encadrement : GUILLAUME Jean-Loup

Dynamique des graphes de terrain : analyse en temps intrinsèque

Nous sommes entourés par une multitude de réseaux d'interactions, issus de contextes très différents : réseau social, réseau d'interactions entre neurones, réseau de transport, etc. Ces réseaux d'interactions peuvent être modélisés par des graphes, appelés graphes de terrain. Les graphes de terrains possèdent le plus souvent une structure en communautés, c'est-à-dire en groupes de nœuds très liés entre eux, et peu liés avec les autres. L'identification des communautés permet de mieux comprendre la structure du graphe étudié, quel que soit son domaine. Elle permet par exemple de déterminer de manière automatique les groupes dans un réseau social : personnes travaillant au même endroit, promotion de classe, etc. Un autre phénomène que l'on étudie sur les graphes dans de nombreux contextes est la diffusion. La propagation d'une maladie en est un exemple : une personne atteinte d'un virus risque de contaminer les gens qu'elle côtoie. Ceux-ci peuvent alors contaminer à leur tour certaines de leurs relations, etc. Le virus se propage ainsi au sein de la population, en suivant les interactions entre les individus. Ces questions de recherche ont été beaucoup étudiées avec des graphes statiques. Cependant, les systèmes considérés sont en constante évolution, ce qui a donc naturellement donné lieu à l'utilisation de graphes dynamiques où les nœuds et les liens peuvent apparaître et disparaître au cours du temps.
Dans ce contexte, la façon d'étudier un phénomène dynamique dépend d'un paramètre important, mais souvent peu étudié : l'échelle de temps selon laquelle on observe ce phénomène. Selon l'échelle choisie, la dynamique du graphe peut varier de manière très importante. Dans cette thèse, nous proposons d'étudier des graphes et des processus dynamiques en utilisant une échelle de temps adaptée à leur dynamique. Afin que celle-ci soit pertinente quelle que soit la dynamique du phénomène étudié, il faut qu'elle dépende directement du graphe, et pas d'une unité absolue comme la seconde ou la journée. Nous considérons ici une notion de temps relatif, que nous appelons le temps intrinsèque, par opposition au temps "classique", que nous appelons temps extrinsèque. Nous étudions en premier lieu des phénomènes de diffusion selon une échelle de temps intrinsèque, et nous comparons les résultats obtenus avec une échelle de temps extrinsèque. Ceci nous permet à la fois de montrer l'intérêt de l'échelle de temps intrinsèque pour mieux comprendre un phénomène de diffusion et la dynamique d'un graphe, et de mettre en évidence le fait qu'un même phénomène observé à deux échelles de temps différentes puisse présenter un comportement très différent. Nous analysons ensuite la pertinence de l'utilisation du temps intrinsèque pour la détection de communautés dynamiques. Pour cela, nous utilisons un algorithme connu, que nous appliquons aux échelles de temps intrinsèque et extrinsèque. La comparaison des communautés obtenues selon les deux échelles de temps nous montre qu'une échelle de temps intrinsèque permet la détection de communautés beaucoup plus significatives et détaillées que l'échelle de temps extrinsèque.

Publications 2011-2014

• 2014
  • A. Albano : “Dynamique des graphes de terrain : analyse en temps intrinsèque”, thèse, soutenance 10/10/2014, direction de recherche Le grand, Bénédicte, co-encadrement : Guillaume, Jean-Loup (2014)
  • A. Albano, J.‑L. GUILLAUME, B. Le Grand : “On the use of intrinsic time scale for dynamic community detection and visualization in social networks”, Proceedings of the 8^th IEEE International Conference on Research Challenges in Information Science (RCIS 2014), Marrakech, Morocco, pp. 1-11 (2014)
  • A. Albano, J.‑L. GUILLAUME, S. Heymann, B. Le Grand : “Studying Graph Dynamics Through Intrinsic Time Based Diffusion Analysis”, Applications of Social Media and Social Network Analysis (2014)
• 2013
  • A. Albano, J.‑L. GUILLAUME, S. Heymann, B. Le Grand : “A Matter of Time - Intrinsic or Extrinsic - for Diffusion in Evolving Complex Networks”, Conference on Advances in Social Networks Analysis and Mining, Niagara Falls, Canada, pp. 202-206 (2013)
  • A. Albano, B. Le Grand, M. Latapy : “Visualisation de grands réseaux dynamiques: Application à la détection d’anomalies de routage dans l’Internet.”, Revue des Sciences et Technologies de l'Information - Série RIA : Revue d'Intelligence Artificielle, vol. 26 (4), pp. 409-427, (Lavoisier) (2013)
• 2012
  • A. Albano, J.‑L. GUILLAUME, B. Le Grand : “File Diffusion in a Dynamic Peer-to-peer Network”, WWW 2012 - MSND'12 Workshop, Lyon, France, pp. 1169-1172, (ACM) (2012)
• 2011
  • A. Albano : “Phénomènes de diffusion dans les réseaux dynamiques : simulation et modélisation”, Journée Fouille de Grands Graphes 2011, Grenoble, France (2011)