Come decomporre in modo efficiente le reti

Nella scena finale del film di successo "Il pianeta delle scimmie: Prevoluzione" Dal 2011, un pilota di aereo sponsorizza inconsapevolmente un pericoloso virus influenzale da San Francisco a Parigi. Da lì, innumerevoli passeggeri delle compagnie aeree lo diffondono in tutto il mondo. A differenza delle scimmie, la maggior parte dell'umanità non sopravvive alla successiva pandemia.

Naturalmente, l'ascesa delle scimmie intelligenti (il film originale si chiama L'ascesa del pianeta delle scimmie) Fantascienza. La diffusione di virus patogeni attraverso i viaggi aerei, invece, è un rischio reale. I ricercatori dell'ETH Professorship of Computational Social Science e del Dipartimento di Informatica hanno ora studiato come la scomposizione delle reti possa aiutare a limitare la diffusione dei virus attraverso il traffico aereo in modo più economico.

Una misura di protezione talvolta discussa è la chiusura di alcuni aeroporti e la loro messa in quarantena. Un'opzione potrebbe essere quella di concentrarsi sugli hub aeroportuali più grandi del mondo e con il maggior numero di collegamenti aerei - dopo tutto, molti passeggeri atterrano o cambiano aereo lì. Tuttavia, questa non è l'idea migliore.

L'intervento sarebbe massiccio a causa dell'elevato numero di viaggiatori aerei interessati. I ricercatori dell'ETH Xiao-Long Ren, Niels Gleinig, Dirk Helbing e Nino Antulov-Fantulin hanno ora dimostrato sulla rivista scientifica PNAS che potrebbero esistere misure meno radicali e più efficaci che interesserebbero un numero molto inferiore di passeggeri.

Prima le medie imprese

"Ad esempio, se chiudessimo prima alcuni aeroporti di medie dimensioni invece degli hub più grandi, lo scenario che abbiamo analizzato costerebbe quattro volte meno. Tuttavia, questo sembra essere altrettanto efficace nel contenere la diffusione del virus", afferma Nino Antulov-Fantulin.

I ricercatori dell'ETH hanno analizzato questo scenario per l'Europa, il Nord America e l'Asia come componenti di una rete di traffico aereo globale. I risultati mostrano che la chiusura degli aeroporti di medie dimensioni avrebbe un impatto solo sul 6% dei passeggeri aerei globali, mentre la chiusura degli hub più grandi avrebbe un impatto sul 25%.

Per scoprire quali aeroporti è meglio chiudere se si vuole contenere il virus in modo economico ed efficace, i ricercatori hanno adottato un approccio noto nella ricerca sulle reti come "problema dello smantellamento", uno dei problemi fondamentali della ricerca sulle reti. Si tratta di determinare quali nodi devono essere disattivati o rimossi da una rete per risolvere un problema o un malfunzionamento che si verifica al suo interno.

I ricercatori del Fare all'ETH hanno cercato di suddividere le varie reti difettose in sottoreti isolate al costo totale più basso possibile, al fine di contenere la diffusione dei guasti e mantenere la funzionalità della rete complessiva. A seconda che si tratti di una rete sociale, biologica o tecnica, gli errori possono essere, ad esempio, virus informatici, agenti patogeni dell'influenza o criminali.

Arginare il crimine

In altri casi di studio, i ricercatori del Fare all'ETH sono riusciti a dimostrare che è più economico ed efficace smantellare una rete concentrandosi inizialmente sui nodi di medie dimensioni piuttosto che su quelli più grandi: Questo vale, ad esempio, per le reti criminali.

Se si parte dai vertici delle reti criminali, i costi sono molto elevati. Non solo a causa delle speciali misure di protezione per i boss, ma anche perché di solito qualcun altro assume rapidamente la leadership e continua a gestire la rete. Secondo i ricercatori, se si eliminano prima le posizioni intermedie, la rete può essere smantellata con la stessa efficacia e con uno sforzo significativamente minore.

"Rispetto a un metodo all'avanguardia, il costo della decomposizione della rete nel nostro approccio è 2,5 volte inferiore quando riduciamo una rete criminale al 10% della sua dimensione originale", spiega Xiao-Long Ren, dottorando e primo autore dello studio. Il caso della rete criminale illustra un'altra caratteristica speciale dell'approccio dell'ETH: A differenza di altri metodi, non tratta tutti i nodi allo stesso modo.

"Non assumiamo più che tutti i nodi di una rete abbiano gli stessi costi di rimozione", continua Ren, "ma piuttosto che i costi di rimozione dei nodi più grandi siano più alti perché sono più fortemente connessi agli altri".

Sfide teoriche e applicative

I ricercatori dell'ETH hanno fatto progressi anche nella decomposizione di reti particolarmente grandi, che comprendono diversi milioni di nodi. Il "problema della decomposizione" appartiene alla classe di problemi informatici difficili noti come problemi NP-hard.

Anche se il metodo teorico è stato dimostrato con dati empirici, si raccomandano studi supplementari prima della sua applicazione pratica. Il metodo deve essere adattato al rispettivo settore di applicazione e testato. Non solo la struttura della rete e i costi di distanza dei nodi della rete, ma anche altri fattori possono giocare un ruolo.

I ricercatori sottolineano inoltre: "Le applicazioni legittime del nostro metodo devono tenere conto delle questioni etiche in modo sufficiente, appropriato e trasparente".