Ce 26 janvier, l’Institut Henri Fayol avait le plaisir d’accueillir le séminaire de recherche du laboratoire LIMOS sur le thème «Graphs and Cyber-Insurance Protection», présenté par Nabil Kazi-Tani (Université de Lorraine, IECL).
Résumé :
Dans cet exposé, nous considérons la situation où un graphe donné doit être protégé contre une interruption de communication, par des mesures d’assurance ou de prévention. L’objectif de l’acheteur de la protection est de maintenir de bonnes propriétés de connectivité du graphe après une attaque malveillante, provoquant la propagation d’un virus sur le réseau. Nous modélisons la propagation de l’épidémie à l’aide du processus de Markov standard Susceptible-Infecté-Susceptible (SIS). La connectivité du graphe est mesurée par une fonction du spectre laplacien moyen : la deuxième plus petite valeur propre, appelée connectivité algébrique. En utilisant des résultats standard sur l’optimisation des valeurs propres, nous avons refondu la maximisation de la connectivité algébrique comme un problème d’optimisation semi-défini, pour lequel une solution existe et peut être efficacement calculée numériquement. Nos résultats permettent de hiérarchiser les arêtes d’un graphe, en donnant plus d’importance à certaines arêtes pour lesquelles la demande de protection est élevée, faisant ainsi dépendre la demande d’assurance optimale directement de la topologie du réseau sous-jacent. Celle-ci s’appuie sur un travail commun avec Thierry Cohignac (Groupe CCR, Paris).