LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » Actualité » Doctorants

SEIFI Massoud

Docteur
Équipe : ComplexNetworks
Date de départ : 15/03/2012
Direction de recherche : Matthieu LATAPY
Co-encadrement : GUILLAUME Jean-Loup

Cœurs stables de communautés dans les graphes de terrain

Dans de nombreux contextes, des ensembles d'entités en relation peuvent être modélisés par des graphes, dans lesquels les entités individuelles sont représentées par des sommets et les relations entre ces entités par des liens. Ces graphes, que nous appellerons "graphes de terrain", peuvent être rencontrés dans le monde réel dans différents domaines tels que les sciences sociales, l'informatique, la biologie, le transport, la linguistique, etc. La plupart des graphes de terrain sont composés de sous-graphes denses faiblement inter-connectés appelés "communautés" et de nombreux algorithmes ont été proposés afin d'identifier cette structure communautaire automatiquement. Nous nous sommes intéressés dans cette thèse aux problèmes des algorithmes de détection de communatés, notamment leur non-déterminisme et l'instabilité qui en découle. Nous avons présenté une méthodologie qui tire parti de ce non-déterminisme afin d'améliorer les résultats obtenus avec les techniques actuelles de détection de communautés. Nous avons proposé une approche basée sur le concept de communautés fortes ou "cœurs de communautés" et nous avons montré l'amélioration apportée par notre approche en l'appliquant à des graphes réels et artificiels. Nous avons aussi étudié la structure des cœurs des graphes aléatoires et nous avons montré qu'à la différence des algorithmes classiques de détection de communautés qui peuvent trouver des partitions en communautés dans des graphes n'ayant pourtant aucune structure communautaire intrinsèque, notre approche indique clairement l'absence de structure communautaire dans les graphes aléatoires et permet en ce sens de distinguer les graphes aléatoires des graphes réels. Nous avons étudié également l'évolution des cœurs dans des réseaux dynamiques via une dynamique simulée simple et contrôlable ainsi qu'une dynamique réelle. Nous avons montré que les cœurs sont beaucoup plus stables que les communautés obtenues par les techniques actuelles de détection de communautés et que notre approche peut donc pallier les défauts des méthodes stabilisées qui ont été proposées récemment.
Soutenance : 12/03/2012 - 14h - Site Jussieu 25-26/105
Membres du jury :
Bertrand Jouve, Professeur Université Lumière Lyon 2 [Rapporteur]
Christine Largeron, Professeur Université Jean Monnet, [Rapporteur]
Christophe Crespelle, MdC, Université Claude Bernard Lyon 1
Marcelo Dias de Amorin, Directeur de Recherche CNRS
Matthieu Latapy, Directeur de Recherche CNRS
Jean-Loup Guillaume, MdC, Uuniversité Pierre et Marie Curie

Publications 2010-2013

 Mentions légales
Carte du site |