Le 3 décembre 2018, à 14h, salle des thèses de la faculté Jean Perrin.

Résumé :

Cette thèse se situe dans le domaine de l’analyse des réseaux complexes. Un réseau complexe peut être défini comme un système d’entités en interaction représenté souvent par un graphe. Deux problématiques liées à l’analyse des grands graphes sont abordées dans cette thèse. Notre premier objectif est d’extraire de la connaissance pertinente dans les graphes par la recherche des structures communautaires. Le deuxième problème concerne la représentation compacte des grands graphes complexes. Le premier problème est connue sous le nom de détection de communautés. En effet, l’existence des zones plus denses que d’autres est l’une des caractéristiques des graphes complexes. Ces zones sont appelées communautés. Ces communautés peuvent être chevauchantes ou disjointes et peuvent avoir plusieurs significations selon le type de graphe en question. Le deuxième problème étudié est celui de la compression de graphes : il s’agit de tirer parti de la structure du graphe pour en faire une représentation compacte. Notre première contribution apportée à la détection de communautés chevauchantes introduit un nouveau concept de communauté appelée communauté k-liée. Ce nouveau concept permet de caractériser une communauté avec un diamètre au plus k. Une telle communauté admet un sommet ou un une arête ayant une distance d’au plus k/2 de tout autre sommet de cette même communauté.

Premièrement, nous montrons comment le problème de détection de communautés k-liées chevauchantes peut être exprimé sous forme d’un problème d’optimisation Max-SAT. Deuxièmement, nous montrons comment sélectionner les centroïdes des communautés k-liées selon des relations de préférences. Dans une seconde contribution, nous proposons deux modèles basés sur l’extension des graines pour la détection de communautés chevauchantes dans les grands réseaux complexes. Un premier modèle consiste à relaxer la structure de clique. Cette relaxation donne lieu à une nouvelle notion de communauté appelée k-clique-star. Un deuxième modèle consiste à étendre les cliques maximales pour identifier les communautés chevauchantes recherchées. Dans la dernière contribution, nous proposons une nouvelle approche pour la compression de grands graphes. Nous montrons d’abord que certaines classes de graphes peuvent être représentées de manière efficace par des contraintes Pseudo Booléennes (PB). Ensuite, nous proposons plusieurs nouvelles structures de graphes incluant les cliques et diverses extensions de la classe des graphes bi-partis. Enfin, nous présentons un nouvel algorithme basé sur les contraintes PB pour résumer les grands graphes. Toutes les approches proposées sont efficaces, très compétitives et donnent de meilleurs résultats que de nombreuses approches de l’état de l’art.