# Generalized network dismantling

Edited by H. Eugene Stanley, Boston University, Boston, MA, and approved February 15, 2019 (received for review April 12, 2018)

## Significance

The proper functioning of many sociotechnical systems depends on their level of connectivity. By removing or deactivating a specific set of nodes, a network structure can be dismantled into isolated subcomponents, thereby disrupting the malfunctioning of a system or containing the spread of misinformation or an epidemic. We propose a generalized network-dismantling framework, which can take realistic removal costs into account such as the node price, the protection level, or removal energy. We discuss applications of cost-efficient dismantling strategies to real-world problems such as containing an epidemic or dismantling criminal or corruption networks.

## Abstract

Finding an optimal subset of nodes in a network that is able to efficiently disrupt the functioning of a corrupt or criminal organization or contain an epidemic or the spread of misinformation is a highly relevant problem of network science. In this paper, we address the generalized network-dismantling problem, which aims at finding a set of nodes whose removal from the network results in the fragmentation of the network into subcritical network components at minimal overall cost. Compared with previous formulations, we allow the costs of node removals to take arbitrary nonnegative real values, which may depend on topological properties such as node centrality or on nontopological features such as the price or protection level of a node. Interestingly, we show that nonunit costs imply a significantly different dismantling strategy. To solve this optimization problem, we propose a method which is based on the spectral properties of a node-weighted Laplacian operator and combine it with a fine-tuning mechanism related to the weighted vertex cover problem. The proposed method is applicable to large-scale networks with millions of nodes. It outperforms current state-of-the-art methods and opens more directions for understanding the vulnerability and robustness of complex systems.

### Sign up for PNAS alerts.

Get alerts for new articles, or get an alert when an article is cited.

Networking the world creates many opportunities, but sometimes also produces undesired side effects. For instance, in a hyperconnected world, systemic instability can seriously undermine the functionality of a network based on cascading effects (1). The quick global spread of rumors and fake news may be seen as recent examples (2, 3), while the spread of epidemics (4, 5) or failure propagation (6, 7) is a problem that has been around much longer. Furthermore, it is known that the network structure, for example the exponent characterizing scale-free networks, is of particular importance for the controllability of cascading effects (8). For certain scaling exponents of scale-free networks, the variance or mean value of relevant quantities may not be well defined, which means that unpredictable or uncontrollable behavior may result. 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 not only is relevant for the quick increase of cyberthreats, but also may undermine the functionality of markets or societal or political institutions.

However, the removal or deactivation of even a small set of nodes may dismantle the network into isolated subcomponents and thereby stop the malfunctioning of a system. The effectiveness of node removal depends on the network structure and the removal strategy. For example, scale-free networks (9, 10) are known to be more robust to random removals than Erdős–Rényi networks (11, 12), but at the same time more vulnerable to targeted attacks (13–16).

Finding the most efficient removal strategy which dismantles a network (17, 18) into isolated subcomponents of a specified maximum size at minimum overall cost belongs to a class of hard computational problems, called nondeterministic polynomial hard (NP-hard) problems. Essentially, this implies that there is currently no algorithm that can find the best dismantling solution for large-scale networks. It is, therefore, a challenge to find good approximations of the optimal dismantling strategy. For example, novel approximations (17–23) have been proposed based on spin-glass and optimal percolation theory. However, all these methods make the implicit assumption that the cost of removing nodes is the same. Only recently have people been interested in the effect of removal costs that depends on the node degree (24, 25). However, these studies were restricted to random network structures (24) or edge-based strategies (25), but they did not tackle the generalized network-dismantling optimization problem.

This paper addresses the question of how to select the set of nodes in a network that, when removed or (de)activated, can stop the spread of (dis)information, mitigate an epidemic, or disrupt a malicious system by fragmenting it into small components at minimum overall cost. In the generalized network-dismantling problem, the cost of removing a node can be an arbitrary nonnegative real value, which can, for example, be specified as a function of a node’s centrality properties (26) or also nontopological variables. Understanding the key relationships between dismantling solutions and their overall costs enables one to increase the level of robustness of real-world systems.

The main contributions of this paper are as follows:(

*i*) We argue that some problems such as containing crime, corruption, epidemics, or fake news cannot be adequately addressed with the well-known network-dismantling problem assuming identical node removal costs and that for nonunit removal costs another, more efficient solution strategy is needed. (*ii*) We study the generalized network-dismantling problem, which seeks to find a set of nodes that, when removed from a network, results in a network fragmentation into components of at most size $C$ at minimal overall cost. Compared with the prevailing approach in network science (17–23), we allow for removal costs that have arbitrary nonnegative real values. (*iii*) We formulate a node-weighted graph-cutting objective function, which determines the upper bound for the node-weighted bisection. We study its analytical solution and approximation and present analytical bounds and convergence proofs. (*iv*) To dismantle large-scale networks, we propose an efficient iterative node-weighted spectral bisection method, which has complexity $O\left(n\cdot {\mathrm{log}}^{2+\u03f5}\left(n\right)\right)$. We combine the spectral approach with a fine-tuning mechanism by mapping the problem to the weighted vertex cover problem (28). (*v*) We show that our approach outperforms current state-of-the-art methods (17–22) for nonunit costs. In the unit cost scenario, our approach performs better than or comparable to the state-of-the-art methods.The generalized network-dismantling problem is related to the weighted partitioning problem in graph theory (29), which was addressed by means of vertex separators. The main difference is that the weighted partitioning problem specifies the number of partitions and the network-dismantling problem specifies only the target size $C$. For more differences between separator, partitioning, and dismantling problems, see

*SI Appendix*, section 7. Although different versions of weighted separator problems were studied long ago by graph theory (30, 31), the main focus was not on realistic node removal costs for real-world networks. Moreover, according to a recent review of graph partitioning methods (32), these methods are not well applicable to large-scale complex networks due to their broad (or even heavy-tailed) degree distribution compared with traditional graphs. Probably for this reason, the weighted partitioning problem has not been applied as much in the network science community (17–22).## Problems with Nonuniform Removal Costs

While criminal and corruption networks are one of humanity’s biggest problems, it seems that effective ways to dismantle them are still needed. 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 great 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 (33); besides, the transition period is often characterized by an increase in the level of crime, until the power struggle is decided. Therefore, we generalize the dismantling problem to nonunit node removal costs. As we will show, 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. In this paper, we propose an algorithm to solve the generalized network-dismantling problem and apply it to a variety of problems ranging from crime networks to epidemic spreading to corruption networks.

## Generalized Network-Dismantling Problem

For a network $G\left(V,E\right)$ with a set of nodes, $V$, and a set of edges, $E$, a set of nodes, $S$, is called a $C$-dismantling set, if the largest connected component of the network after removing $S$ contains at most $C$ nodes (17, 34). In this paper, the ratio of $C$ and $\left|V\right|$ is denoted by $c$. Finding a minimal $C$-dismantling set is an NP-hard problem. Current state-of-the-art methods (17–22) make the implicit assumption that the cost of node removal is the same for all of the nodes in a network, regardless of their importance. Here, thus, we generalize the network-dismantling problem in such a way that the cost of removing a node $i$ can be an arbitrary nonnegative value ${w}_{i}\in \mathcal{R}$. More formally, for a given network $G\left(V,E\right)$ with costs $\left({w}_{1},\dots ,{w}_{\left|V\right|}\right)$ written to diagonal matrix $W$, we aim to find a set of nodes $S\left(G,W,C\right)\subseteq V$, the removal of which will create a fragmentation of the network into components of at most size $C$ at a minimum overall removal cost. For the optimal set, the overall removal cost is denoted by $Cost\left(G,W,C\right)$. In where ${w}_{min},{w}_{max}$ denote the minimal and maximal node removal costs.

*SI Appendix*, section 7, we show more details about the hardness of (generalized) network dismantling. It is easy to see that the case when the cost matrix $W$ equals the identity matrix ($W=I$), this problem corresponds to the standard network-dismantling problem and its solution is related to the solution of the generalized problem by the inequalities$${w}_{min}Cost\left(G,I,C\right)\le Cost\left(G,W,C\right)\le {w}_{max}Cost\left(G,I,C\right),$$

### Node-Weighted Partition.

Let us assume that we want to partition the network $G=\left(V,E\right)$ into two parts $M\subseteq V$ and its complement $\overline{M}=V\backslash M$. Whether a node $i$ belongs to the set $M$ or not is represented by the following vector $v\in {R}^{n}$:The classical spectral bisection of a graph aims to minimize the number of edges that have to be removed between $M$ and $\overline{M}$. In this paper we propose a node-weighted spectral cut objective function, where the cost of cutting the edge $\left(i,j\right)$ is equal to the cost of removing nodes $i$ and $j$. Then the upper bound of the removal cost iswhere $A$ is the adjacency matrix of the network. Therefore, if an edge $\left(i,j\right)$ connects nodes from different parts, the associated cost is ${w}_{i}+{w}_{j}-1$, as ${v}_{i}{v}_{j}=-1$ and ${A}_{i,j}=1$. In contrast, if the edge $\left(i,j\right)$ connects nodes from the same cluster (${v}_{i}{v}_{j}=1$), it will not be removed and the associated cost is zero. Without loss of generality (see subject toMatrices $W$ and ${D}_{B}$ are diagonal matrices with the elements ${W}_{ii}={d}_{i}$ and ${\left({D}_{B}\right)}_{ii}={\sum}_{j=1}^{n}{B}_{ij}$. See

$${v}_{i}\u2254\left\{\begin{array}{cc}+1\hspace{1em}\hfill & i\in M,\hfill \\ -1\hspace{1em}\hfill & otherwise.\hfill \end{array}\right.$$

[1]

$$\frac{1}{2}\sum _{i,j}-\frac{1}{2}\left({v}_{i}{v}_{j}-1\right){A}_{i,j}\left({w}_{i}+{w}_{j}-1\right),$$

[2]

*SI Appendix*, section 1 for more details), we assume that the proxy for the weight is proportional to the degree centrality ${w}_{i}\propto {d}_{i}$. The term $\left({w}_{i}+{w}_{j}-1\right)$ contains the constant element −1 to lead to a more elegant notation. Now, we define the matrix $B$ by the elements ${B}_{i,j}={A}_{i,j}\left({w}_{i}+{w}_{j}-1\right)$ and define the node-weighted Laplacian of the matrix $B=AW+WA-A$ by ${L}_{w}={D}_{B}-B$. In matrix notation the optimization problem can now be written as$$min\frac{1}{4}{v}^{T}{L}_{w}v$$

[3]

$${\mathbf{1}}^{T}v=0,$$

[4]

$${v}_{i}\in \left\{+1,-1\right\},i\in \left\{\mathrm{1,2},\dots ,n\right\}.$$

[5]

*SI Appendix*, section 1 for more details.When the cost matrix equals the identity matrix ($W=I$), we get the unweighted Laplacian, which corresponds to the classical bisection problem (30, 35). The additional constraint ${\mathbf{1}}^{T}v=0$ enforces that clusters are of the same size. Unfortunately, the optimization problem is NP hard. Therefore, we follow the standard relaxation (30) from the integer constraint ${v}_{i}\in \left\{+1,-1\right\}$ to ${v}_{i}\in \mathcal{R}$. The solution to this relaxed constrained minimization problem is, according to the Courant–Fisher theorem, analytically given by the second-smallest eigenvector of the node-weighted Laplacian ${\lambda}_{2}{v}^{\left(2\right)}={L}_{w}{v}^{\left(2\right)}$. A more detailed derivation of this solution is presented in

*SI Appendix*, section 1. If we remove all of the nodes $i$ whose corresponding value in the second-smallest eigenvector is nonnegative (${v}_{i}^{\left(2\right)}\ge 0$) and has a neighbor $j$ with a negative entry (${v}_{j}^{\left(2\right)}<0$), the network will fragment into two subnetworks $M$ and $\overline{M}$. Note that we fine-tune the spectral approximation solution, which increases the performance of our algorithm and is described later.The node-weighted spectral cut is recursively applied to $M$ and $\overline{M}$ until the network is sufficiently fragmented into small subnetworks of maximum size $C$.

### Spectral Approximation.

To find the second-smallest eigenvectors for large-scale networks, we propose the following simple and elegant approximation algorithm, which falls into the class of power-iteration methods (36). Note that ${L}_{w}$ is a real, symmetric, and positive semidefinite matrix. Then, it has real nonnegative eigenvalues ${\lambda}_{1}\le {\lambda}_{2}\le \dots \le {\lambda}_{n}$ with the eigenvectors ${v}^{\left(1\right)},\dots ,{v}^{\left(n\right)}$, which form an orthonormal basis of ${\mathbb{R}}^{n}$. In

*SI Appendix*, section 2, we show spectral bounds for degree-based cost ${\lambda}_{n}\le 6\cdot {d}_{max}^{2}$, where ${d}_{max}$ is the maximum degree of any node of the network. In the case of nontopological costs, we use the following spectral bound ${\lambda}_{n}\le 4{d}_{max}\left({w}_{max}+1\right)$, where ${w}_{max}$ is the maximum cost. To compute ${v}^{\left(2\right)}$, we consider the matrix $\stackrel{\u0303}{L}=6\cdot {d}_{max}^{2}\cdot I-{L}_{w}$, which has the same eigenvectors ${v}^{\left(1\right)},\dots ,{v}^{\left(n\right)}$ as ${L}_{w}$. Now the corresponding eigenvalues are shifted such that $\stackrel{\u0303}{{\lambda}_{1}}=6\cdot {d}_{max}^{2}\ge \dots \ge \stackrel{\u0303}{{\lambda}_{n}}=6\cdot {d}_{max}^{2}-{\lambda}_{n}\ge 0$. Let ${v}^{\left(1\right)}$ be the eigenvector with the largest eigenvalue and ${v}^{\left(2\right)}$ be the eigenvector with the second-largest eigenvalue. Then, we find the eigenvector of ${L}_{w}$ associated with the eigenvalue ${\lambda}_{2}$ via the following steps: (*i*) Start with a random vector $v$ uniformly drawn from the unit sphere ${S}^{n}$, (*ii*) force it to be perpendicular to the first eigenvector ${v}_{1}={\left(1,\dots ,1\right)}^{T}$ of the weighted Laplacian ${L}_{w}$, and (*iii*) apply the linear operator ${\stackrel{\u0303}{L}}^{k}$ with unit normalization to our vector $v$. The pseudocode of this spectral approximation is as follows: (*i*) Draw $v$ randomly from a uniform distribution on the unit sphere. (*ii*) Set $v=v-\frac{{v}_{1}^{T}v}{{v}_{1}^{T}{v}_{1}}\cdot {v}_{1}$. (*iii*) For $i=1$ to $k=\eta \left(n\right)$, set $v=\frac{\stackrel{\u0303}{L}v}{\Vert \stackrel{\u0303}{L}v\Vert}$.The intuition that the random vector $v$ converges exponentially to some eigenvector of ${L}_{w}$ with eigenvalue ${\lambda}_{2}$ is closely related to the spectral properties of operator ${\stackrel{\u0303}{L}}^{k}$. Note that we can represent our random vector $v$ in the orthonormal eigenvector basis as $v={\sum}_{i=1}^{n}{\psi}_{i}{v}^{\left(i\right)}$. The second step of orthogonalization ensures ${\psi}_{1}=0$ and ${\psi}_{2}\ne 0$ (almost surely). Finally, by applying the linear operator ${\stackrel{\u0303}{L}}^{k}$ to vector $v$ we getWhen ${\lambda}_{3}>{\lambda}_{2}$, we have $\left|\frac{\stackrel{\u0303}{{\lambda}_{i}}}{\stackrel{\u0303}{{\lambda}_{2}}}\right|<1$, ${\left(\frac{\stackrel{\u0303}{{\lambda}_{i}}}{\stackrel{\u0303}{{\lambda}_{2}}}\right)}^{k}{\psi}_{i}{v}_{i}\to 0$ with exponential speed. The expected value of vector $v$ converges to some eigenvector of ${L}_{w}$ with eigenvalue ${\lambda}_{2}$,when the power $k$ of operator $\stackrel{\u0303}{L}$ scales as $\mathcal{O}\left(\mathrm{log}{\left(n\right)}^{1+\u03f5}\right)$ for every real number $\u03f5>0$, where $n$ is the size of the network.

$${\stackrel{\u0303}{L}}^{k}v=\sum _{i=2}^{n}{\psi}_{i}{\stackrel{\u0303}{{\lambda}_{i}}}^{k}{v}^{\left(i\right)}\propto {\psi}_{2}{v}^{\left(2\right)}+\sum _{i=3}^{n}{\psi}_{i}{\left(\frac{\stackrel{\u0303}{{\lambda}_{i}}}{\stackrel{\u0303}{{\lambda}_{2}}}\right)}^{k}{v}^{\left(i\right)}.$$

[6]

$$\mathbb{E}\left[|{\lambda}_{2}-\frac{{v}^{T}{L}_{w}v}{{v}^{T}v}|\right]\to 0,$$

[7]

If ${\lambda}_{2}={\lambda}_{3}=\dots ={\lambda}_{k}<{\lambda}_{k+1}$, this sequence converges to a unit length linear combination of ${v}_{2},\dots ,{v}_{k}$ and is therefore a vector which still minimizes $\frac{{v}^{T}{L}_{w}v}{{v}^{T}v}$ among all vectors that are orthogonal to ${v}_{1}$. Formal proofs for the convergence and bounds are given in

*SI Appendix*, section 3.The computational complexity of recursively applying this procedure to smaller and smaller partitions is $O\left(n\cdot \eta \left(n\right)\cdot \mathrm{log}\left(n\right)\right)$ for sparse networks. Due to the fast convergence, one can expect asymptotically good partitions when $\eta \left(n\right)=\mathrm{log}{\left(n\right)}^{1+\u03f5}$ and $\u03f5>0$, which finally ends in the complexity of $O\left(n\cdot {\mathrm{log}}^{2+\u03f5}\left(n\right)\right)$ for sparse networks. Further details about the asymptotic complexity are given in

*SI Appendix*, section 4.### Fine-Tuning of the Spectral Solution.

Let us represent by ${E}^{*}$ the set of separating edges that connect nodes from the set $\left\{{v}_{i}\ge 0\right\}$ to the set $\left\{{v}_{i}<0\right\}$. The set of nodes that are adjacent to the separating set ${E}^{*}$ is denoted by ${V}^{*}$. We can optimize the solution by finding a set of nodes which covers all of the edges in ${E}^{*}$ with minimal cost. This is the weighted vertex cover problem (28) on the graph ${G}^{*}=\left({V}^{*},{E}^{*}\right)$ with weights ${w}_{i}$, from the original network $G=\left(V,E\right)$. Further details about the fine-tuning approximation are provided in

*SI Appendix*, section 5. A general overview of our proposed method is given in Fig. 1, which we refer to as the generalized network dismantling (GND) method in the rest of this paper.Fig. 1.

### Reinsertion.

Finally, as the proposed GND method is offering a recursive solution, some of the nodes from early stages of fragmentation do not contribute to the final stage of complete fragmentation. Thus, to produce better dismantling solutions [GND with reinsertion (GNDR)], we apply the reinsertion method (19).

## Results

To demonstrate the applicability of the proposed generalized network-dismantling framework to realistic scenarios, we apply it to some real-world networks and show that the current state-of-the-art dismantling strategy (19) delivers different results from the nonunit cost problem, as expected. In addition to the complete dismantling, we also focus on the partial dismantling of the system’s giant connected component (GCC), which reflects the fact that the budget is usually limited such that only a partial dismantling is possible.

Fig. 2 shows some results of network dismantling, which correspond to suppressing the spread of misinformation, computer viruses, or other harmful contagion processes on the online social network [Petster–Hamster (37)]. The cost for the 80% partial dismantling with the state-of-the-art Min-Sum strategy (19) is 0.4. However, although the Min-Sum algorithm removes only 5% of nodes in this process, its cost is rather large. The reason for this becomes clear if we study the degree distribution of the removed nodes in Fig. 2

*C*, where we note that the largest hubs tend to be removed by Min-Sum. In contrast, the random removal of nodes, also known as the site percolation process, with the same cost of 0.4 achieves fragmentation to ∼75% of the original GCC size. This implies that the state-of-the-art algorithms for unit-cost problems tend to be inefficient when applied to problems with nonunit costs. However, with the same cost of 0.4, our GND method fragments the network to 62% of the original GCC size, and for the target of 80% of the GCC size, the corresponding cost is only 0.2.Fig. 2.

Next, we study the dismantling on different real-world networks for three different state-of-the-art methods: equal graph partitioning (EGP) (39), Min-Sum (17), and belief propagation-guided decimation (BPD) (20). The networks in the main text include (

*i*) a crime network with 754 nodes obtained by the projection of a bipartite network of persons and crimes (37), (*ii*) a corruption network (38) with 309 nodes and 3,281 edges, (*iii*) the online social network of Petster–Hamster (37) with 2,000 nodes and 16,631 edges, and (*iv*) a power-grid network (37) with 4,941 nodes and 6,594 edges. For more algorithms and networks see*SI Appendix*, section 8.In Fig. 3, the results show that, for partial dismantling, the proposed methodology (GND and GNDR) achieves the same fragmentation level with a much smaller overall dismantling cost:

*c*= 0.2 with 0.18 (GND) vs. 0.42 (BPD) for the crime network,*c*= 0.2 with 0.24 (GND) vs. 0.9 (Min-Sum) for the corruption network,*c*= 0.2 with 0.63 (GND) vs. 0.8 (BPD) for the Petster–Hamster network, and*c*= 0.3 with 0.11 (GND) vs. 0.17 (BPD) for the power-grid network. In Fig. 4, we show the performance of different algorithms for the unit-cost case on two networks, where the GND and GNDR algorithms show better or comparable performance. More detailed experiments for the unit and nonunit costs are in*SI Appendix*, section 8. Also in*SI Appendix*, section 8, we summarize the ratio of the removal cost of BPD, Min-Sum, and GNDR algorithms when the target size is 0.8, 0.6, 0.4, and 0.2, respectively. The results show that the performance of GNDR is better or at least comparable for both degree-based and unit node removal costs. In*SI Appendix*, section 7, we have constructed the benchmark network with many loops, for which we know the optimal solution. Interestingly, we observe that loops can create problems for the BPD and Min-Sum algorithms and that the optimal solutions for network dismantling and its generalized version may coincide or deviate, depending on the chosen value of $c$.Fig. 3.

Fig. 4.

If external information about the removal costs is available, we are able to incorporate it into the matrix $W$ and proceed with our GND method.

*SI Appendix*, section 2 gives spectral bounds for general nonnegative weights, for which the same spectral approximation method can be used. In Fig. 5, we show the results for the world airport network, where the cost ${w}_{i}$ of closing an airport $i$ is assumed to be given by the total passengers flux of the airport. The closing of an airport can represent quarantine. Correspondingly, the reduction of the GCC size represents the containment effect for the pandemic spread. In this example, we set the target size of the GCC to 80% of the initial size. It is interesting to observe that our GND method dismantles the network with only 0.06 of the total removal costs of all nodes, which is significantly less than the cost of 0.25 by Min-Sum. We also provide a geographical visualization of the dismantling solution, where the closed airports are represented by red circles.Fig. 5.

## Summary and Conclusions

In this paper, we have studied the generalized network-dismantling problem, which seeks to find a set of nodes allowing one to dismantle a network into components up to small size $C$ in the most cost-effective way. We do not make the assumption that the cost of removing nodes is the same for all of the nodes, which has been typically made before. Instead, we allow for node removal costs that are given by topological properties or nontopological features such as the price or protection level of a node. We acknowledge that, for the unit-cost scenario, the BPD and Min-Sum methods (17, 20) provide good solutions in many cases and have provided additional insights about the problem. However, for networked systems with nonunit node removal costs, current state-of-the-art dismantling methods will often not produce near-optimal results, while our proposed methods (GND and GNDR) do. These are based on a blend of spectral properties of a node-weighted Laplacian operator, a power-iteration method, and weighted vertex cover approximations. Understanding the theory behind network dismantling (17, 20, 24) opens up more research directions for all scientists interested in designing more robust and resilient systems in the future. Interestingly, our dismantling strategy is different from previous ones as it removes medium-size rather than big nodes first. Our results are relevant for the robustness and recommended (re)organization of current sociotechnical systems for different realistic costs. For example, we have demonstrated that generalized network dismantling can enable cost-effective immunization strategies against harmful contagion in social and transportation networks as well as the disruption of criminal and corruption networks.

## Ethics

The method presented in this paper aims at offering a possible solution for emergencies where cutting a dysfunctional network into pieces can restore its functionality. However, we 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, we point out that related ethical issues must be sufficiently, appropriately, and transparently addressed (40) when the method is applied. The method must be restricted to legitimate uses and actors. It may be justified to stop harmful cascading problems such as deadly epidemics and the spreading of disruptive computer malware or to dismantle criminal organizations or corruption networks. Note, however, that the use of dismantling strategies to contain misinformation can be potentially problematic, as it may result in censorship if a government, company, news agency, or other institution decides what is misinformation or not. See

*SI Appendix*, section 9 for more details.## Data Availability

Data deposition: The code and data have been deposited at https://github.com/renxiaolong/Generalized-Network-Dismantling.

## Acknowledgments

The authors thank K. K. Kleinberg and A. Lancic for useful comments. X.-L.R. thanks the China Scholarship Council for financial support. N.A.-F. and D.H. are grateful for support from the European Union Horizon 2020 projects: SoBigData under Grant 654024 and CIMPLEX under Grant 641191.

## Supporting Information

Appendix (PDF)

- Download
- 2.52 MB

## References

1

D Helbing, Globally networked risks and how to respond.

*Nature***497**, 51–59 (2013).2

M Del Vicario, et al., The spreading of misinformation online.

*Proc Natl Acad Sci USA***113**, 554–559 (2016).3

MM Waldrop, News feature: The genuine problem of fake news.

*Proc Natl Acad Sci USA***114**, 12631–12634 (2017).4

A Vespignani, Modelling dynamical processes in complex socio-technical systems.

*Nat Phys***8**, 32–39 (2011).5

D Brockmann, D Helbing, The hidden geometry of complex, network-driven contagion phenomena.

*Science***342**, 1337–1342 (2013).6

P Holme, BJ Kim, Vertex overload breakdown in evolving networks.

*Phys Rev E***65**, 066109 (2002).7

SV Buldyrev, R Parshani, G Paul, HE Stanley, S Havlin, Catastrophic cascade of failures in interdependent networks.

*Nature***464**, 1025–1028 (2010).8

SN Dorogovtsev, AV Goltsev, JFF Mendes, Critical phenomena in complex networks.

*Rev Mod Phys***80**, 1275–1335 (2008).9

A-L Barabási, R Albert, Emergence of scaling in random networks.

*Science***286**, 509–512 (1999).10

SN Dorogovtsev, JFF Mendes, AN Samukhin, Structure of growing networks with preferential linking.

*Phys Rev Lett***85**, 4633–4636 (2000).11

P Erdős, A Rényi, On the evolution of random graphs.

*Inst Hung Acad Sci***5**, 17–61 (1960).12

EN Gilbert, Random graphs.

*Ann Math Stat***30**, 1141–1144 (1959).13

R Albert, H Jeong, A-L Barabási, Error and attack tolerance of complex networks.

*Nature***406**, 378–382 (2000).14

R Cohen, K Erez, D Ben-Avraham, S Havlin, Breakdown of the internet under intentional attack.

*Phys Rev Lett***86**, 3682–3685 (2001).15

CM Schneider, AA Moreira, JS Andrade, S Havlin, HJ Herrmann, Mitigation of malicious attacks on networks.

*Proc Natl Acad Sci USA***108**, 3838–3841 (2011).16

LK Gallos, et al.

*Attack Strategies on Complex Networks*(Springer, Berlin), pp. 1048–1055 (2006).17

A Braunstein, L Dall’Asta, G Semerjian, L Zdeborová, Network dismantling.

*Proc Natl Acad Sci USA***113**, 12368–12373 (2016).18

F Morone, HA Makse, Influence maximization in complex networks through optimal percolation.

*Nature***524**, 65–68 (2015).19

L Zdeborová, P Zhang, H-J Zhou, Fast and simple decycling and dismantling of networks.

*Sci Rep***6**, 37954 (2016).20

S Mugisha, H-J Zhou, Identifying optimal targets of network attack by belief propagation.

*Phys Rev E***94**, 012305 (2016).21

F Morone, B Min, L Bo, R Mari, HA Makse, Collective influence algorithm to find influencers via optimal percolation in massively large social media.

*Sci Rep***6**, 30062 (2016).22

L Tian, A Bashan, D-N Shi, Y-Y Liu, Articulation points in complex networks.

*Nat Commun***8**, 14223 (2017).23

H-J Zhou, Spin glass approach to the feedback vertex set problem.

*Eur Phys J B***86**, 455 (2013).24

A Patron, R Cohen, D Li, S Havlin, Optimal cost for strengthening or destroying a given network.

*Phys Rev E***95**, 052305 (2017).25

X-L Ren, N Gleinig, D Tolić, N Antulov-Fantulin, Underestimated cost of targeted attacks on complex networks.

*Complexity***2018**, 1–15 (2018).26

L Lü, et al., Vital nodes identification in complex networks.

*Phys Rep***650**, 1–63 (2016).27

D Tolić, K-K Kleineberg, N Antulov-Fantulin, Simulating SIR processes on networks using weighted shortest paths.

*Sci Rep***8**, 6562 (2018).28

R Bar-Yehuda, S Even, A linear-time approximation algorithm for the weighted vertex cover problem.

*J Algorithms***2**, 198–203 (1981).29

U Feige, MT Hajiaghayi, JR Lee, Improved approximation algorithms for minimum weight vertex separators.

*SIAM J Comput***38**, 629–657 (2008).30

M Fiedler, Algebraic connectivity of graphs.

*Czechoslovak Math J***23**, 298–305 (1973).31

S Guattery, GL Miller, On the quality of spectral separators.

*SIAM J Matrix Anal Appl***19**, 701–719 (1998).32

A Buluç, H Meyerhenke, I Safro, P Sanders, C Schulz

*Recent Advances in Graph Partitioning*(Springer International Publishing, Cham, Switzerland), pp. 117–158 (2016).33

PAC Duijn, V Kashirin, PMA Sloot, The relative ineffectiveness of criminal network disruption.

*Sci Rep***4**, 4238 (2014).34

S Janson, A Thomason, Dismantling sparse random graphs.

*Combin Probab Comput***17**, 259–264 (2008).35

MA Riolo, MEJ Newman, First-principles multiway spectral partitioning of graphs.

*J Complex Networks***2**, 121–140 (2014).36

P Alex, HD Simon, K-P Liou, Partitioning sparse matrices with eigenvectors of graphs.

*SIAM J Matrix Anal Appl***11**, 430–452 (1990).37

J Kunegis, KONECT–The Koblenz network collection.

*Proceedings of International Conference on World Wide Web Companion*, ed D Schwabe (ACM, New York), pp. 1343–1350 (2013).38

HV Ribeiro, LGA Alves, AF Martins, EK Lenzi, M Perc, The dynamical structure of political corruption networks.

*J Complex Networks***6**, 989–1003 (2018).39

Y Chen, G Paul, S Havlin, S Liljeros, HE Stanley, Finding a better immunization strategy.

*Phys Rev Lett***101**, 58701 (2008).40

D Helbing, et al., Will democracy survive big data and artificial intelligence?

*Towards Digital Enlightenment*, ed D Helbing (Springer, Cham, Switzerland), pp. 73–98 (2019).## Information & Authors

### Information

#### Published in

#### Classifications

#### Copyright

Copyright © 2019 the Author(s). Published by PNAS. This open access article is distributed under Creative Commons Attribution-NonCommercial-NoDerivatives License 4.0 (CC BY-NC-ND).

#### Data Availability

Data deposition: The code and data have been deposited at https://github.com/renxiaolong/Generalized-Network-Dismantling.

#### Submission history

**Published online**: March 15, 2019

**Published in issue**: April 2, 2019

#### Keywords

#### Acknowledgments

The authors thank K. K. Kleinberg and A. Lancic for useful comments. X.-L.R. thanks the China Scholarship Council for financial support. N.A.-F. and D.H. are grateful for support from the European Union Horizon 2020 projects: SoBigData under Grant 654024 and CIMPLEX under Grant 641191.

#### Notes

This article is a PNAS Direct Submission.

### Authors

#### Competing Interests

The authors declare no conflict of interest.

## Metrics & Citations

### Metrics

#### Citation statements

#### Altmetrics

### Citations

If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.

#### Cited by

Loading...

## View Options

### View options

#### PDF format

Download this article as a PDF file

DOWNLOAD PDF#### Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Personal login Institutional Login#### Recommend to a librarian

Recommend PNAS to a Librarian#### Purchase options

Purchase this article to access the full text.