Fixing Over-Connectivity

The functioning of many socio-technical systems depends on the ability of its subcomponents or nodes to communicate or interact via its connections, but high connectivity may imply problems. By removing or deactivating a specific set of nodes, a network structure can be dismantled into isolated subcomponents, thereby disrupting the (mal)functioning of a system or containing the spread of misinformation or an epidemic. The researchers (Ren, Gleinig, Helbing, Antulov-Fantulin) at the Swiss Federal Institute of Technology ETH Zurich recently proposed and published insights about Generalized Network Dismantling in the Proceedings of the National Academy of Sciences of the United States of America (PNAS). Link https://doi.org/10.1073/pnas.1806108116

In a hyper-connected world, systemic instability, based on cascading effects, can seriously undermine the functionality of a network. The quick global spread of rumors and fake news may be seen as recent examples, while the spread of epidemics or failure propagation is a problem that has been around much longer. Many of today’s networks contain highly connected nodes with a much higher frequency than expected according to a normal, bell-shaped distribution. As a consequence, for some of these networks even the variance or mean value of relevant quantities may not anymore be well-defined. This means that unpredictable or uncontrollable behavior may result. For example, it may then be impossible to contain epidemic spreading processes. Similar circumstances may make it impossible to contain the spread of computer viruses or misinformation – a problem that is not only relevant for the quick increase of cyberthreats, but which may also undermine the functionality of markets, societal or political institutions.

For example, finding an optimal subset of nodes in a network that is able to successfully disrupt the functioning of a corrupt or criminal organization is still a great challenge. In principle, the dismantling of a network into isolated subcomponents might stop the (mal)functioning of a system, i.e. the removal or deactivation of even a small set of influential nodes may allow one to fix the problem. However, this problem belongs to the class of computationally hard problems. For these problems, it is numerically demanding to find the best solution efficiently. The publication of Ren et al. presents a new, approximate dismantling solution.

A typical approach to fight organized crime and corruption is to try to identify the underlying organization’s network, and then to remove the leader of the organization. It turns out, however, that it often requires an extremely high effort to remove the higher echelons of such organizations, because of their special protection measures. Removal costs of criminals or corrupt persons largely depend on their position in the network. It has also been found that it is often ineffective to remove the boss of a corruption or criminal network, as someone else will quickly take the leadership position of the organization and continue running the criminal or corruption network; besides, the transition period is often characterized by an increase in the level of crime, until the power struggle is decided. Therefore, the dismantling problem, which has been studied primarily for situations with identical node removal costs before, has been generalized to arbitrary, non-uniform removal costs. This class of problems has different kinds of solutions. Specifically, the dismantling procedure does not go for the big nodes first. It is less costly (i.e. more effective) to dismantle the network by initially removing some medium-sized nodes.

Ren et al. present a new algorithm to solve the generalized network dismantling problem, and apply it to a variety of problems ranging from crime networks over epidemic spreading to corruption networks. The new approach is based on a combination of three sophisticated methods and is applicable to large-scale networks with millions of nodes. Understanding the theory behind (generalized) network dismantling opens up more research directions for all scientists interested in designing more robust and resilient systems in the future. It requires the combination of diverse fundamental insights, for example, from theoretical computer science, mathematics, statistical physics, and even game theory. 

The results of the study are relevant for the robustness and recommended (re)organization of current socio-technical systems for different realistic costs. In particular, the authors point that the method offers a possible solution for emergencies where cutting a dysfunctional network into pieces can restore the functionality. However, they also warn of potential misuses or dual uses. When not applied in appropriate contexts and ways, the use of the dismantling approach may undermine the proper functionality of networks. Therefore, they point out that related ethical issues must be always sufficiently, appropriately, and transparently addressed, when the method is applied. 

Visualization of a strategy to potentially reduce the epidemic spreading of a disease.