Détection de Noeuds Critiques dans les réseaux

Le Problème des Noeuds Critiques (CNP) est un problème dont a formalisation est relativement récente mais qui recouvre un grand nombre d'applications potentielles. Il consiste à identifier un sous-ensemble des noeuds d'un graphe tels que leur "élimination" (ou retrait) du graphe en impacte la connectivité de manière maximale. En d'autres termes, ce sont les noeuds les plus critiques à la connectivité du réseau, qui peut se concevoir comme la capacité des noeuds à communiquer entre eux. Les domaines d'applications recensés dans la littérature vont des réseaux de télécommunications à la distribution d'énergie en passant par des problématiques d'immunisation de réseau en situation de pandémie ou encore l'analyse de réseaux sociaux.