Soutenance de thèse - J.-P. ATTAL

Nouveaux algorithmes pour la détection de communautés disjointes et chevauchantes basés sur la propagation de labels et adaptés aux grands graphes

Jean-Philippe ATTAL

Jean-Philippe ATTAL, enseignant à l'EISTI, est désormais docteur en informatique. Il a obtenu le 19 janvier 2017 sa thèse intitulée "Nouveaux algorithmes pour la détection de communautés disjointes  et chevauchantes basés sur la propagation de labels et adaptés aux grands graphes".

Composition du jury

Rapporteurs

Monsieur Arnaud MARTIN (Université de Rennes 1, laboratoire IRISA )
Monsieur Guy MELANÇON (Université de Bordeaux, Laboratoire LaBRI)

Examinateurs
Monsieur Dominique Laurent (Université de Cergy-Pontoise, Laboratoire ETIS)
Madame Maria MALEK (EISTI, Laboratoire Quartz)
Monsieur Henry SOLDANO (Institut Galilée - Université Paris-Nord, Laboratoire LIPN)

Directeur de thèse
Monsieur Marc ZOLGHADRI (SUPMECA, Laboratoire Quartz)

Résumé

Les graphes sont des structures mathématiques capable de modéliser certains systèmes complexes. Une des nombreuses problématiques liée aux graphes concerne la détection de communautés qui vise à trouver une partition en sommet d'un graphe en vue d'en comprendre la structure. A titre d'exemple, en représentant des contrats d'assurances par des nœuds et leurs degrés de similarité par une arête, détecter des groupes de nœuds fortement connectés conduit à détecter des profils similaires, et donc a voir des profils à risques.
De nombreux algorithmes ont essayé de répondre à ce problème.
Une des méthodes est la propagation de labels qui consiste à ce que chaque nœud puisse recevoir un label par un vote majoritaire de ses voisins. Bien que cette méthode soit simple à mettre en œuvre, elle présente une grande instabilité due au non déterminisme de l'algorithme et peut dans certains cas ne pas détecter de structures communautaires.
La première contribution  de cette thèse sera de

i) proposer une méthode de stabilisation de la propagation de labels tout en appliquant des barrages artificiels pour limiter les possibles mauvaises propagations.  Les réseaux complexes ont également comme caractéristique que certains nœuds  puissent appartenir à plusieurs communautés, on parle alors de recouvrements. 

C'est en ce sens que la seconde contribution de cette thèse portera sur ii) la création d'un algorithme auquel seront adjointes des fonctions d'appartenances pour détecter de possibles recouvrements via des nœuds candidats au chevauchement. La taille des graphes est également une notion à considérer dans  la mesure où certains réseaux peuvent contenir plusieurs millions de nœuds et d'arêtes.

Nous proposons iii) une version parallèle et distribuée de la détection de communautés en utilisant la propagation de labels par cœur. Une étude comparative sera effectuée pour observer la qualité de partitionnement et de recouvrement des algorithmes proposés.