• complex systems
• robustness
• network fragmentation
• spectral partitioning
• network immunization

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(n⋅log2+ϵ(n))$O\left(n\cdot {\log }^{2+ϵ}\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).

Generalized Network-Dismantling Problem

For a network G(V,E)$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 |V|$\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 wi∈R$w_i\in \mathcal{R}$. More formally, for a given network G(V,E)$G\left(V,E\right)$ with costs (w1,…,w|V|)$\left(w_1,\dots ,w_{\left|V\right|}\right)$ written to diagonal matrix W, we aim to find a set of nodes S(G,W,C)⊆V$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(G,W,C)$Cost\left(G,W,C\right)$. In 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$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

wminCost(G,I,C)≤Cost(G,W,C)≤wmaxCost(G,I,C),$$w_{min}Cost\left(G,I,C\right)\le Cost\left(G,W,C\right)\le w_{max}Cost\left(G,I,C\right),$$

where wmin,wmax$w_{min},w_{max}$ denote the minimal and maximal node removal costs.

Node-Weighted Partition.

Let us assume that we want to partition the network G=(V,E)$G=\left(V,E\right)$ into two parts M⊆V$M\subseteq V$ and its complement M¯¯¯¯¯=V\M$\overline{M}=V\backslash M$. Whether a node i belongs to the set M or not is represented by the following vector v∈Rn$v\in R^n$:

vi≔{+1 −1 i∈M,otherwise.$$v_i≔\begin{array}{cc}+1\hspace{1em}\hfill & i\in M,\hfill \\ -1\hspace{1em}\hfill & otherwise.\hfill \end{array}$$

[1]The classical spectral bisection of a graph aims to minimize the number of edges that have to be removed between M and M¯¯¯¯¯$\overline{M}$. In this paper we propose a node-weighted spectral cut objective function, where the cost of cutting the edge (i,j)$\left(i,j\right)$ is equal to the cost of removing nodes i and j. Then the upper bound of the removal cost is

12∑i,j−12(vivj−1)Ai,j(wi+wj−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]where A is the adjacency matrix of the network. Therefore, if an edge (i,j)$\left(i,j\right)$ connects nodes from different parts, the associated cost is wi+wj−1$w_i+w_j-1$, as vivj=−1$v_i{v}_j=-1$ and Ai,j=1$A_{i,j}=1$. In contrast, if the edge (i,j)$\left(i,j\right)$ connects nodes from the same cluster (vivj=1$v_i{v}_j=1$), it will not be removed and the associated cost is zero. Without loss of generality (see SI Appendix, section 1 for more details), we assume that the proxy for the weight is proportional to the degree centrality wi∝di$w_i\propto d_i$. The term (wi+wj−1)$\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 Bi,j=Ai,j(wi+wj−1)$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$B=AW+WA-A$ by Lw=DB−B$L_w=D_B-B$. In matrix notation the optimization problem can now be written as

min14vTLwv$$min\frac{1}{4}{v}^T{L}_{w}v$$

[3]subject to

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

[4]

vi∈{+1,−1},i∈{1,2,…,n}.$$v_i\in \left.+1,-1\right\},i\in \left.\mathrm{1,2},\dots ,n\right\}.$$

[5]Matrices W and DB$D_B$ are diagonal matrices with the elements Wii=di$W_{ii}=d_i$ and (DB)ii=∑nj=1Bij${\left(D_B\right)}_{ii}={\sum }_{j=1}^n{B}_{ij}$. See SI Appendix, section 1 for more details.

When the cost matrix equals the identity matrix (W=I$W=I$), we get the unweighted Laplacian, which corresponds to the classical bisection problem (30, 35). The additional constraint 1Tv=0${\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 vi∈{+1,−1}$v_i\in \left.+1,-1\right\}$ to vi∈R$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 λ2v(2)=Lwv(2)${\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(2)i≥0$v_i^{\left(2\right)}\ge 0$) and has a neighbor j with a negative entry (v(2)j<0$v_j^{\left(2\right)}<0$), the network will fragment into two subnetworks M and M¯¯¯¯¯$\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 M¯¯¯¯$\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 Lw$L_w$ is a real, symmetric, and positive semidefinite matrix. Then, it has real nonnegative eigenvalues λ1≤λ2≤…≤λn${\lambda }_1\le {\lambda }_2\le \dots \le {\lambda }_n$ with the eigenvectors v(1),…,v(n)$v^{\left(1\right)},\dots ,v^{\left(n\right)}$, which form an orthonormal basis of Rn${\mathbb{R}}^n$. In SI Appendix, section 2, we show spectral bounds for degree-based cost λn≤6⋅d2max${\lambda }_n\le 6\cdot d_{max}^2$, where dmax$d_{max}$ is the maximum degree of any node of the network. In the case of nontopological costs, we use the following spectral bound λn≤4dmax(wmax+1)${\lambda }_n\le 4d_{max}\left(w_{max}+1\right)$, where wmax$w_{max}$ is the maximum cost. To compute v(2)$v^{\left(2\right)}$, we consider the matrix L˜=6⋅d2max⋅I−Lw$\tilde{L}=6\cdot d_{max}^2\cdot I-L_w$, which has the same eigenvectors v(1),…,v(n)$v^{\left(1\right)},\dots ,v^{\left(n\right)}$ as Lw$L_w$. Now the corresponding eigenvalues are shifted such that λ1˜=6⋅d2max≥…≥λn˜=6⋅d2max−λn≥0$\widetilde{{\lambda }_1}=6\cdot d_{max}^2\ge \dots \ge \widetilde{{\lambda }_n}=6\cdot d_{max}^2-{\lambda }_n\ge 0$. Let v(1)$v^{\left(1\right)}$ be the eigenvector with the largest eigenvalue and v(2)$v^{\left(2\right)}$ be the eigenvector with the second-largest eigenvalue. Then, we find the eigenvector of Lw$L_w$ associated with the eigenvalue λ2${\lambda }_2$ via the following steps: (i) Start with a random vector v uniformly drawn from the unit sphere Sn$S^n$, (ii) force it to be perpendicular to the first eigenvector v1=(1,…,1)T$v_1={\left(1,\dots ,1\right)}^T$ of the weighted Laplacian Lw$L_w$, and (iii) apply the linear operator L˜k${\tilde{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−vT1vvT1v1⋅v1$v=v-\frac{v_1^{T}v}{v_1^T{v}_1}\cdot v_1$. (iii) For i=1$i=1$ to k=η(n)$k=\eta \left(n\right)$, set v=L˜v∥∥L˜v∥∥$v=\frac{\tilde{L}v}{\Vert \tilde{L}v\Vert }$.

The intuition that the random vector v converges exponentially to some eigenvector of Lw$L_w$ with eigenvalue λ2${\lambda }_2$ is closely related to the spectral properties of operator L˜k${\tilde{L}}^k$. Note that we can represent our random vector v in the orthonormal eigenvector basis as v=∑ni=1ψiv(i)$v={\sum }_{i=1}^n{\psi }_i{v}^{\left(i\right)}$. The second step of orthogonalization ensures ψ1=0${\psi }_1=0$ and ψ2≠0${\psi }_2\ne 0$ (almost surely). Finally, by applying the linear operator L˜k${\tilde{L}}^k$ to vector v we get

L˜kv=∑i=2nψiλi˜kv(i)∝ψ2v(2)+∑i=3nψi(λi˜λ2˜)kv(i).$${\tilde{L}}^{k}v=\sum _{i=2}^n{\psi }_i{\widetilde{{\lambda }_i}}^k{v}^{\left(i\right)}\propto {\psi }_2{v}^{\left(2\right)}+\sum _{i=3}^n{\psi }_i{\left.\frac{\widetilde{{\lambda }_i}}{\widetilde{{\lambda }_2}}\right)}^k{v}^{\left(i\right)}.$$

[6]When λ3>λ2${\lambda }_3>{\lambda }_2$, we have ∣∣λi˜λ2˜∣∣<1$\left|\frac{\widetilde{{\lambda }_i}}{\widetilde{{\lambda }_2}}\right|<1$, (λi˜λ2˜)kψivi→0${\left.\frac{\widetilde{{\lambda }_i}}{\widetilde{{\lambda }_2}}\right)}^k{\psi }_i{v}_i\to 0$ with exponential speed. The expected value of vector v converges to some eigenvector of Lw$L_w$ with eigenvalue λ2${\lambda }_2$,

E[∣∣∣λ2−vTLwvvTv∣∣∣]→0,$$\mathbb{E}\left.|{\lambda }_2-\frac{v^T{L}_{w}v}{v^{T}v}|\right]\to 0,$$

[7]when the power k of operator L˜$\tilde{L}$ scales as O(log(n)1+ϵ)$\mathcal{O}\left(\log {\left(n\right)}^{1+ϵ}\right)$ for every real number ϵ>0$ϵ>0$, where n is the size of the network.

If λ2=λ3=…=λk<λk+1${\lambda }_2={\lambda }_3=\dots ={\lambda }_k<{\lambda }_{k+1}$, this sequence converges to a unit length linear combination of v2,…,vk$v_2,\dots ,v_k$ and is therefore a vector which still minimizes vTLwvvTv$\frac{v^T{L}_{w}v}{v^{T}v}$ among all vectors that are orthogonal to v1$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(n⋅η(n)⋅log(n))$O\left(n\cdot \eta \left(n\right)\cdot \log \left(n\right)\right)$ for sparse networks. Due to the fast convergence, one can expect asymptotically good partitions when η(n)=log(n)1+ϵ$\eta \left(n\right)=\log {\left(n\right)}^{1+ϵ}$ and ϵ>0$ϵ>0$, which finally ends in the complexity of O(n⋅log2+ϵ(n))$O\left(n\cdot {\log }^{2+ϵ}\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∗$E^{*}$ the set of separating edges that connect nodes from the set {vi≥0}$\left.v_i\ge 0\right\}$ to the set {vi<0}$\left.v_i<0\right\}$. The set of nodes that are adjacent to the separating set E∗$E^{*}$ is denoted by V∗$V^{*}$. We can optimize the solution by finding a set of nodes which covers all of the edges in E∗$E^{*}$ with minimal cost. This is the weighted vertex cover problem (28) on the graph G∗=(V∗,E∗)$G^{*}=\left(V^{*},E^{*}\right)$ with weights wi$w_i$, from the original network G=(V,E)$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.

• Download figure
• Open in new tab
• Download powerpoint

Fig. 1.

(A) Steps of the GND algorithm. (A, 1) The inputs are the adjacency matrix A and the node removal cost matrix W. (A, 2) Construction of the cost-weighted network defined by the matrix B and its corresponding node-weighted Laplacian Lw$L_w$. (A, 3) Construction of the power Laplacian operator L˜k${\tilde{L}}^k$, which is applied to the random vector v'$v\prime$ on an n-dimensional sphere. The result gives an approximate solution to partition the network into two components {i:vi<0}$\left\{i:v_i<0\right\}$ and {i:vi≥0}$\left\{i:v_i\ge 0\right\}$. (A, 4) Fine-tuning of the spectral solution with the weighted vertex cover on the subgraph of nodes that contains edges between components (represented in black and red). (B) Illustration of the procedure of the iterative GND algorithm. (C) Contributions of different parts of our method to the dismantling solution for the Petster–Hamster network. The blue line shows the performance when only steps 1–3 are adopted. The red solid line (GND algorithm) shows the performance when steps 1–4 are applied, which generates a more efficient node removal process. The red dashed line (GNDR algorithm) shows the performance when the algorithm includes steps 1–4 and the reinsertion step, which is characterized by a smaller overall node removal cost.

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. 2C, 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.

• Download figure
• Open in new tab
• Download powerpoint

Fig. 2.

(A) Network dismantling of three strategies: Min-Sum algorithm (17), random removal (site percolation), and GND. For the same dismantling cost 0.4, the result of Min-Sum is 5% worse than the random removal. (B) Dynamical process [susceptible-infected-removed (SIR) model (27) with β=0.04$\beta =0.04$, γ=0.01$\gamma =0.01$] on the residual network after the node removal up to 40% of the total cost. The GND produces the best immunization. (C and D) Visualization of the set of removed nodes according to Min-Sum (red) and GND (blue).

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.

• Download figure
• Open in new tab
• Download powerpoint

Fig. 3.

Dismantling of the criminal and corruption networks and creation of firewalls to stop the spread of misinformation or malicious software in online networks. We show the size of the GCC vs. the overall dismantling cost for four different networks: (A) crime network (37), (B) corruption network (38), (C) Petster–Hamster online social network (37), and (D) power-grid network (37). The dismantling strategy with a smaller area under the curve performs better. The EGP-W, Min-Sum-W, and BPD-W algorithms are the weighted versions of the original EGP, Min-Sum, and BPD algorithms, generalized to nonunit node removal costs (SI Appendix, section 8). For comparison with more algorithms see SI Appendix, section 8 and Fig. S4.

• Download figure
• Open in new tab
• Download powerpoint

Fig. 4.

(A and B) Dismantling curves showing the performance of node removal for the unit-cost case, for the (A) Petster–Hamster online social network (37) and (B) power-grid network (37). We observe that even for unit costs and complete dismantling, our proposed dismantling strategy (GNDR) provides good solutions. For the comparison of more algorithms and more networks, see SI Appendix, section 8, Figs. S5 and S6, and Table S1.

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 wi$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.

• Download figure
• Open in new tab
• Download powerpoint

Fig. 5.

Comparison of the dismantling performance for the airport network, where the removal cost is the total passenger flow of the airport. (A) Setting the target size to c=80%$c=80\%$, the Min-Sum algorithm (17) implies a cost of closing airports with ∼25% of the total passenger flow. In contrast, our GND strategy dismantles the network to c=80%$c=80\%$ size by a cost of only 6%. In B–D, red circles visualize the airports that were closed by the Min-Sum (Upper) or the GND (Lower).

• Copyright © 2019 the Author(s). Published by PNAS.