Comment décomposer efficacement les réseaux

Dans la scène finale du film à succès "La Planète des singes : Prévolution". de 2011, un pilote d'avion transporte à son insu un dangereux virus de la grippe de San Francisco à Paris. De là, d'innombrables passagers aériens le propagent dans le monde entier. Contrairement aux singes, une grande partie de l'humanité ne survit pas à la pandémie qui s'ensuit.

Bien sûr, l'ascension des singes intelligents (dans l'original, le film s'appelle Rise of the Planet of the Apes) La science-fiction. La propagation de virus pathogènes par le biais du trafic aérien est en revanche un risque bien réel. Des chercheurs de la chaire de sciences sociales computationnelles de l'ETH et du département d'informatique ont étudié comment la décomposition des réseaux pourrait aider à limiter de manière plus rentable la propagation des virus par le trafic aérien.

Une mesure de protection parfois discutée consiste à fermer certains aéroports et à les mettre en quarantaine. Une possibilité serait de se concentrer sur les plus grands hubs aéroportuaires du monde avec le plus grand nombre de liaisons aériennes - après tout, c'est là que de très nombreux passagers atterrissent ou changent d'avion. Ce n'est toutefois pas la meilleure idée.

L'intervention serait massive en raison du nombre élevé de voyageurs aériens concernés. Les chercheurs de l'ETH Xiao-Long Ren, Niels Gleinig, Dirk Helbing et Nino Antulov-Fantulin viennent de montrer dans la revue scientifique PNAS qu'il pourrait exister des mesures moins radicales et plus efficaces, qui affecteraient nettement moins de passagers.

Les moyens d'abord

"Si, par exemple, on fermait d'abord quelques aéroports de taille moyenne au lieu des plus grands hubs, le scénario que nous avons étudié entraînerait quatre fois moins de coûts. Néanmoins, cela semble tout aussi efficace pour endiguer la propagation du virus", conclut Nino Antulov-Fantulin.

Les chercheurs de l'ETH ont imaginé ce scénario pour l'Europe, l'Amérique du Nord et l'Asie en tant que composantes d'un réseau mondial de transport aérien. Leurs résultats montrent que la fermeture des aéroports de taille moyenne ne concernerait que 6 pour cent des passagers aériens dans le monde, contre 25 pour cent si les plus grands hubs étaient fermés.

Afin de déterminer quels sont les meilleurs aéroports à fermer si l'on veut endiguer le virus de manière efficace et à moindre coût, les chercheurs ont adopté une approche connue dans la recherche sur les réseaux sous le nom de "Dismantling Problem" (dts. "Problème de décomposition"), qui fait partie des problèmes fondamentaux de la recherche sur les réseaux. Il s'agit de déterminer quels nœuds doivent être désactivés ou supprimés d'un réseau afin de résoudre un problème ou un dysfonctionnement qui s'y produit.

Les chercheurs de l'ETH ont tenté de décomposer différents réseaux défectueux en sous-réseaux isolés, avec un coût total aussi minime que possible, afin de limiter la propagation des erreurs et de préserver la fonctionnalité du réseau global. Selon qu'il s'agit d'un réseau social, biologique ou technique, les erreurs peuvent par exemple être des virus informatiques, des agents pathogènes de la grippe ou des criminels.

Endiguer la criminalité

Dans d'autres études de cas, les chercheurs de l'ETH ont également pu montrer que le démantèlement d'un réseau est moins coûteux et plus efficace si l'on se concentre d'abord non pas sur les plus gros nœuds, mais sur ceux de taille moyenne : C'est le cas par exemple des réseaux criminels.

Commencer au sommet des réseaux criminels entraîne des coûts très élevés. Non seulement en raison des mesures de protection particulières pour les chefs, mais aussi parce qu'en règle générale, quelqu'un d'autre prend rapidement la tête et continue à diriger le réseau. Si l'on commence par supprimer les postes intermédiaires, le réseau peut être démantelé au moins aussi efficacement et il faut déployer nettement moins d'efforts pour cela, selon les chercheurs.

"Par rapport à une méthode de l'état de l'art, le coût de la décomposition d'un réseau dans notre approche est 2,5 fois moins élevé si nous réduisons un réseau criminel à 10 % de sa taille initiale", explique Xiao-Long Ren, doctorant et premier auteur de l'étude. Le cas du réseau criminel illustre une autre particularité de l'approche ETH : Contrairement à d'autres méthodes, elle ne traite pas tous les nœuds de la même manière.

"Nous ne partons plus du principe que tous les nœuds d'un réseau ont le même coût de suppression", poursuit Ren, "au contraire, le coût pour supprimer les gros nœuds est plus élevé parce qu'ils sont plus fortement connectés aux autres".

Un défi en théorie et en application

Les chercheurs de l'ETH ont également progressé dans la décomposition de réseaux particulièrement vastes, comprenant plusieurs millions de nœuds. Le "problème de décomposition" appartient en effet à la classe des problèmes informatiques difficiles, appelés problèmes NP durs.

Même si la méthode théorique a été démontrée à l'aide de données empiriques, il est recommandé de réaliser des études complémentaires avant de l'appliquer dans la pratique. La méthode doit être adaptée et testée en fonction du domaine d'application. Non seulement la structure du réseau et les coûts de distance des nœuds du réseau, mais aussi d'autres facteurs peuvent jouer un rôle.

En outre, les chercheurs soulignent que "les applications légitimes de notre méthode doivent prendre en compte les questions éthiques de manière suffisante, appropriée et transparente".