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

International audienceIn this work, we use the von Neumann graph entropy variation as a measure of graph vulnerability and we propose a new approximate form of this entropy based on structural attributes of the graph, namely the number of edges, vertices or degrees of the graph. The use of such a simplification is mainly motivated by the resulting optimized computation time. Having a simplified form of the entropy, we use it as a characterization of graph vulnerability through the study of the entropy variation following the deletion of edges. Obtained results in large size graphs show the effectiveness of the proposed approximation.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