Qinna Wang
Jeudi 12 Décembre 2013 à 14h,salle 25-26/101
Dans le contexte des réseaux complexes, la structure communautaire du réseau devient un sujet important pour plusieurs domaines de recherche. Les communautés sont en général vues comme des groupes intérieurement denses. La détection de tels groupes offre un éclairage intéressant sur la structure du réseau. Par exemple, une communauté de pages web regroupe des pages traitant du même sujet. La définition de communautés est en général limitée à une partition de lensemble des nœuds. Cela exclut par définition quun nœud puisse appartenir à plusieurs communautés, ce qui pourtant est naturel dans de nombreux (cas des réseaux sociaux par exemple). Une autre question importante et sans réponse est létude des réseaux et de leur structure communautaire en tenant compte de leur dynamique. Cettethèseporte sur létude de réseaux dynamiques et la détection de communautés recouvrantes. Nous proposons deux méthodes différentes pour la détection de communautés recouvrantes. La première méthode est appelée optimisationde clique. L’optimisation de clique vise à détecter les nœuds recouvrants granulaires. La méthode de l’optimisation de clique est une approche à grain fin. La seconde méthode est nommée détection floue (fuzzy detection). Cette méthode est à grain plus grossier et vise à identifier les groupes recouvrants. Nous appliquons ces deux méthodes à des réseaux synthétiques et réels. Les résultats obtenus indiquent que les deux méthodes peuvent être utilisées pour caractériser les nœuds recouvrants. Les deux approches apportent des points de vue distincts et complémentaires. Dans le cas des graphes dynamiques, nous donnons une définition sur la relation entre les communautés à deux pas de temps consécutif. Cette technique permet de représenter le changement de la structure en fonction du temps. Pour mettre en évidence cette relation, nous proposons des diagrammes de lignage pour la visualisation de la dynamique des communautés. Ces diagrammes qui connectent des communautés à des pas de temps successifs montrent lévolution de la structure et l’évolution des groupes recouvrantes., Nous avons également appliquer ces outils à des cas concrets.