Supervision : Clémence MAGNIEN

Dynamique des graphes de terrain : caractérisation et étude du biais lié à la mesure

Les graphes dynamiques apparaissent dans de nombreux contextes, réseaux informatiques dans lesquels des machines ou des liens peuvent subir des pannes, réseaux sociaux dans lesquels des connexions entre individus apparaissent et disparaissent au cours du temps, graphes du web dans lesquels des pages sont créées ou supprimées, etc. Jusqu’à récemment ces objets étaient princi- palement étudiés sous un angle statique. Or, la plupart de ces graphes sont en réalité des graphes dynamiques. Cette dynamique peut apparaître d’une façon différente selon les contextes : réseaux sociaux dans lesquels des connexions entre individus apparaissent et disparaissent au cours du temps, graphes du web dans lesquels des pages sont créées ou supprimées, etc. Un grand nom- bre de résultats de ces 10 dernières années ont introduit un ensemble d’outils pour l’analyse et la description des graphes statiques, mais peu a été fait pour l’étude de leur dynamique. Nous avons abordé dans cette thèse la problématique de la caractérisation de la dynamique des graphes de terrain tout en prenant en compte le biais lié à la mesure, en nous appuyant sur des cas concrets de graphes dynamiques. Nos contributions se sont orientées dans deux directions. Nous nous somme tout d’abord intéressés à l’étude du biais dans l’observation de la dynamique induit par le fait que la période d’observation est finie. Nous avons proposé une nouvelle méthodolo- gie qui permet de déterminer si la longueur de la période d’observation est suffisante pour une caractérisation rigoureuse d’une propriété donnée. Cette méthodologie est générique et peut être appliquée à n’importe quelle propriété caractérisant un graphe de terrain dynamique. Pour démon- trer la pertinence de notre méthodologie, nous l’avons appliquée à l’étude de différentes propriétés dans un système P2P. Notre deuxième contribution consiste en une approche pour étudier des graphes dynamiques. Nous avons cherché à la fois à caractériser la dynamique globale de ces systèmes, et à identifier les éventuels nœuds ayant un comportement particulier. Nous avons étudié plusieurs jeux de données issus de réseaux de contacts entre personnes et nous avons montré que chaque jeu de données a ses particularités. Nous avons également constaté que certaines caractéristiques sont partagées par tous les jeux de données. En particulier, la dynamique globale du réseau change en fonction de la période d’observation et le comportement de certains nœuds diffère du comportement global du système.

2010-2011 Publications

• 2011
  • L. Benamara : “Dynamique des graphes de terrain : caractérisation et étude du biais lié à la mesure”, thesis, phd defence 11/29/2011, supervision Magnien, Clémence (2011)
  • L. Benamara, C. Magnien : “Removing bias due to finite measurement of dynamic systems: case study on P2P systems”, 13^es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), Cap Estérel, France (2011)
• 2010
  • L. Benamara, C. Magnien : “Estimating properties in dynamic systems: the case of churn in P2P networks”, Third International Workshop on Network Science for Communication Networks (NetSciCom 2010), In Conjuction with IEEE Infocom 2010., San Diego, CA, United States, pp. 1-6, (IEEE) (2010)