Approximation de l’entropie de von Neumann de graphes pour une analyse de vulnérabilité

Abstract

Dans ce travail, nous exploitons la variation de l’entropie de von Neumann de graphes comme mesure de vulnérabilité en proposant une nouvelle forme approchée de cette entropie basée sur des attributs structurels du graphe, à savoir le nombre d’arêtes, de sommets ou encore des degrés du graphe. L’utilisation d’une telle forme est motivée par l’optimisation du temps de calcul qui en découle. Disposant d’une forme simplifiée de l’entropie, nous l’utilisons pour la caractérisation de la vulnérabilité des graphes via l’étude de la variation entropique du graphe suite à la suppression d’arêtes. Les résultats obtenus sur des graphes de grandes tailles montrent la pertinence d’une telle approximation.