How to efficiently dismantle networks
Viruses, crime, and many other problems spread through networks. ETH researchers have now developed a new method of protecting them cost-effectively. When budget matters, networks are best dismantled starting with some middle nodes.
In the final scene of the 2011 blockbuster film Rise of the Planet of the Apes, a pilot unwittingly carries a dangerous flu virus from San Francisco to Paris. From there, countless air passengers spread it around the world. Unlike the apes, a large proportion of humanity does not survive the subsequent pandemic.
Of course, this was pure science fiction, but the spread of infectious viruses via air travel is a real risk. Researchers from the ETH Professorship of Computational Social Science and a collaborator from the ETH Department of Computer Science have investigated how network dismantling could help containing the global spread of viruses through air transport more cost-effectively.
A protective measure, which is sometimes discussed, is to close certain airports and put them under quarantine. Then, one option would be to focus on the world’s largest airport hubs with most flight connections – after all, a large number of passengers land there or change planes. This might actually not be the best idea.
The intervention would be massive due to the large number of passengers involved. In the scientific journal PNAS, ETH researchers Xiao-Long Ren, Niels Gleinig, Dirk Helbing and Nino Antulov-Fantulin have now been able to show that there might be less radical and more effective ways to achieve the same level of protection, affecting much fewer passengers.
Start with the medium-sized ones
“For example, if you would close down a few medium-sized airports first instead of the largest hubs, it would cost four times less in the scenario we studied, but it appears to be just as effective in containing the spread of a virus,” says Nino Antulov-Fantulin.
The ETH researchers explored this scenario for Europe, North America and Asia as parts of the worldwide air traffic network. Their results show that the closure of medium-sized airports would affect only 6 percent of global air passengers, while closing the largest hubs would affect 25 percent.
To find out which airports to close in order to stop the virus cheaply and effectively, the researchers investigated a question known in network research as the “dismantling problem”, which is one of the fundamental problems in the field of network science. It examines which nodes need to be deactivated or removed from a network in order to disrupt the malfunctioning of a system.
The ETH researchers attempted to break down various faulty networks into isolated subnetworks at the lowest possible total cost, in order to contain the spread of trouble and maintain the functionality of the overall network. Depending on whether it is a social, biological or technical network, the trouble can take the form of computer viruses, the flu, or criminals.
Containing crime
In other case studies as well, the ETH researchers were able to show that it is cheaper and more effective to dismantle a network by removing some middle nodes first, rather than the largest ones; for example, in criminal networks.
If you start at the top of a criminal network, you incur very high costs. Not only due to the special protection provided for the bosses, but also because typically someone else assumes leadership quickly and continues running the network. If you remove the middle positions first, you can break up the network more effectively at considerably reduced costs, the researchers state.
“Compared to a state-of-the-art method, the costs of network fragmentation are 2.5 times lower in our approach, when dismantling a criminal network to 10 percent of its original size,” says Xiao-Long Ren, doctoral student and first author of the study. The criminal network case illustrates another special feature of the ETH approach: unlike other methods, it does not treat all nodes equally.
“We no longer assume that all nodes in a network incur the same removal costs,” explains Ren. “Rather, the costs to remove the large nodes are higher because they are much more connected to other nodes.”
Big challenge in theory and application
The ETH scientists have also made progress with the dismantling of particularly large networks with millions of nodes. Solving the “dismantling problem” belongs to the category of particularly difficult computer problems known as NP-hard problems – a big challenge in mathematics and computer science.
Even though this theoretical method has been demonstrated with empirical data, the application to real-life scenarios may need further studies. The method should be adapted to and tested in the respective application domain. It is not just the network structure and node removal costs that matter, but there can be other factors as well.
Last but not least, “legitimate applications of our method must take ethical issues into account, appropriately and transparently,” the researchers stress.
References
Ren X-L, Gleinig N, Helbing D, Antulov-Fantulin, N. Generalized network dismantling. Proceedings of the National Academy of Sciences, March 2019, 201806108; DOI: external page 10.1073/pnas.1806108116.