LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » News » PhD students

DANISCH Maximilien

PhD graduated
Team : ComplexNetworks
Associate Professor
Supervision : Bénédicte LE GRAND
Co-supervision : GUILLAUME Jean-Loup

Mesures de proximité appliquées à la détection de communautés dans les grands graphes de terrain

Un grand nombre de données sont naturellement représentables sous la forme d'un graphe (ensemble de nœuds liés par des liens) : Facebook, où des profils sont associés par des liens d'amitié, Internet où des ordinateurs sont liés par des connexions internet, le cerveau où des neurones sont connectés par des synapses, ou bien des protéines réagissant chimiquement entre elles. D'autres types de données peuvent également être convertis, de manière moins naturelle, sous ce format : deux entités sont liées si elles sont suffisamment similaires.
Bien qu'ils viennent de milieux différents, ces graphes de terrain ont des propriétés topologiques communes et l’explosion de leur taille et de leur nombre a créé le besoin d'avoir des algorithmes rapides et génériques permettant de les comprendre et d'en extraire des connaissances utiles. L'une des problématiques privilégiées est liée à leur organisation ; en effet, le nombre de nœuds étant très important, il est intéressant de rassembler ces nœuds dans des groupes afin de mieux comprendre la structure générale du graphe. La détection de communautés qui sont généralement définies, de manière informelle, comme des groupes de nœuds fortement liés les uns aux autres et peu liés vers l'extérieur est un premier pas vers cette description mésoscopique. Une autre problématique est de savoir dans quelle mesure deux nœuds sont topologiquement proches et consiste en l'élaboration de mesures de proximité.
Dans cette thèse, je défends l'idée que ces deux problèmes majeurs, la détection de communautés et la mise au point de mesures de proximité sont fortement intriquées. En particulier, je présente une méthode qui permet, à l'aide d'une mesure de proximité, d'isoler des groupes de nœuds. Son principe général de fonctionnement est plutôt simple et peut être décrit comme suit. Étant donné un nœud d'intérêt dans le graphe, on calcule la proximité de chaque nœud dans le graphe à ce nœud d'intérêt. Ensuite, si un petit groupe de nœuds obtient une proximité très élevée à ce nœud d'intérêt et que tous les autres nœuds du graphe ont une proximité très faible, alors on peut directement conclure que le petit groupe de nœuds est "la communauté" du nœud d'intérêt. Je montre ensuite comment décliner cette idée pour résoudre efficacement les trois problèmes suivants : (i) trouver toutes les communautés auxquelles un nœud donné appartient, (ii) compléter un ensemble de nœuds en une communauté et (iii) trouver des communautés recouvrantes dans un réseau. Je valide les trois méthodes sur des jeux de données réels et synthétiques et montre qu'elles sont des alternatives viables aux approches classiques consistant en l'optimisation gloutonne d'une fonction de qualité.
Defence : 06/15/2015 - 14h - Site Jussieu 25-26/105
Jury members :
David Auber (Maître de Conférences HDR, Université de Bordeaux) [Rapporteur]
Céline Robardet (Professeur, Université de Lyon) [Rapporteur]
Alain Barrat (Directeur de Recherche, CNRS)
Rushed Kanawati (Maître de Conférences, Université Paris Nord)
Matthieu Latapy (Directeur de Recherche, CNRS)
Bivas Mitra (Professeur, Indian Institute of Technology Kharagpur)
Bénédicte Le Grand (Professeur, Université Panthéon-Sorbonne)
Jean-Loup Guillaume (Professeur, Université de La Rochelle)

1 PhD student (Supervision / Co-supervision)

2013-2019 Publications

 Mentions légales
Site map |