Avec l'expansion rapide d'Internet et le développement des réseaux sociaux, des graphes massifs comprenant des milliards de sommets et d'arêtes ont émergé. Les sous-structures denses, également appelées clusters, présentes dans ces graphes sont cruciales pour de nombreuses applications. Par exemple, elles peuvent être utilisées dans les systèmes de recommandation, la détection de fraude ou la compression de données. Le problème de l'identification des clusters dans un graphe est une question bien connue en informatique, avec des formalisations classiques comme les cliques jouant un rôle clé dans la théorie de la complexité. Dans cette thèse, nous avons exploré diverses formalisations du concept de cluster, mieux adaptées aux cas d'application mentionnés précédemment. Parallèlement à ces formalisations, notre étude s'est divisée en deux objectifs principaux : trouver des clusters maximaux, ou du moins de grands clusters, dans un graphe, et couvrir un graphe avec des clusters. Nous nous sommes principalement concentrés sur des méthodes exactes, en privilégiant les approches paramétrées. Concernant l'objectif de trouver de grands clusters, nous avons d'abord examiné des relaxations du concept de clique, telles que les s-clubs, s-cliques et quasi-cliques basées sur le degré. En raison de leur nature non-héréditaire sur les sous-graphes induits, ces relaxations sont difficiles à étudier, et de nombreuses questions liées à la complexité restent non résolues. Pour y remédier, nous avons introduit de nouvelles techniques spécialement adaptées aux formalisations non-héréditaires, ce qui nous a permis de classifier la complexité paramétrée des problèmes de recherche associés à ces relaxations. Nous avons ensuite exploré le concept de sous-graphes proportionnellement denses (PDS), où chaque sommet du sous-graphe a proportionnellement plus de voisins à l'intérieur du sous-graphe qu'à l'extérieur. Cette approche se distingue des relaxations précédemment mentionnées en prenant en compte à la fois les connexions internes et externes du sous-graphe. En adaptant certaines des techniques utilisées pour les relaxations de clique, nous avons réussi à classifier la complexité paramétrée du problème PDS pour grand nombre de paramètres. En ce qui concerne le second objectif, nous avons introduit une variante du problème d'édition de clusters, où le but est de transformer un graphe en une union disjointe de quasi-cliques avec un nombre minimal de modifications d'arêtes. Nous avons examiné différents types de modifications — ajouts, suppressions et éditions — ainsi que deux types de quasi-cliques : les quasi-cliques basées sur le degré et celles basées sur la densité. De plus, nous avons étudié le problème de la partition d'un graphe en quasi-cliques. Pour chaque problème introduit, nous avons fourni sa complexité classique et analysé sa paramétrisation en fonction de k, le nombre maximal de modifications autorisées. Nous avons également étendu la recherche de sous-graphes denses aux graphes temporels en introduisant le modèle de graphe activé, où les sommets peuvent alterner entre états actifs et inactifs pour mieux refléter la dynamique de certains réseaux. Dans ce contexte, nous nous sommes concentrés sur la recherche de sous-graphes induits vérifiant certaines propriétés spécifiques. Premièrement, nous avons prouvé que, comme pour les graphes statiques, trouver de tels sous-graphes est NP-difficile pour toute propriété pi héréditaire, non triviale et polynomiale en temps (HNTP). Deuxièmement, nous avons développé diverses approches paramétrées et proposé des algorithmes applicables aux propriétés pi HNTP. En conclusion, au cours de cette thèse, nous avons étudié la recherche de sous-graphes denses dans les graphes. Nous avons privilégié les approches de complexité paramétrée pour fournir des solutions exactes à nos problèmes tout en garantissant un niveau raisonnable d'efficacité algorithmique.
Mme Clarisse DHAENENS Université de Lille Directrice de thèse, Mme Cristina BAZGAN Université Paris Dauphine Rapporteure, M. Mathieu LIEDLOFF Université d'Orléans Rapporteur, Mme Hamida SEBA Université Claude Bernard Lyon 1 Co-directrice de thèse, M. Jean-Loup GUILLAUME Université de La Rochelle Examinateur, M. Lucas LETOCART Université Sorbonne Paris Nord Examinateur, M. Julien BASTE Université de Lille Examinateur, M. Mohammed HADDAD Université Claude Bernard Lyon 1 Examinateur.
Thesis of the team ORKAD defended on 28/10/2024
français
English