The generalized network dismantling (GND) method is designed to identify a minimal-cost set of nodes whose removal fragments a network into small, disconnected components [2]. The key idea of GND is that the network is assumed to possess a community structure and is recursively split into two groups, with the most effective nodes for disconnecting these groups identified and removed at each step. The order in which nodes are removed can be interpreted as a form of node centrality, reflecting each node’s importance in maintaining network connectivity.
The GND method proceeds iteratively on the largest connected component of the network as follows:


  1. Cost-weighted Laplacian construction: construct the cost-weighted Laplacian matrix \[ L_w = D_B - B, \] where \(B = AW + WA - A\) is the cost-weighted matrix, \(W = \mathrm{diag}(w_1, w_2, \dots, w_n)\) is a diagonal matrix of node removal costs \(w_i > 0\) (if \(W = I\), then \(B = A\)), and \(D_B\) is the degree diagonal matrix of \(B\).

  2. Spectral bipartition: compute the second smallest eigenvector \(\mathbf{v}^{(2)}\) of \(L_w\) and use the signs of its components to bipartition the network nodes into two subgraphs. Ren et al. [2] propose an approximation algorithm based on the power-iteration method.

  3. Weighted vertex cover refinement: identify edges crossing between the two subgraphs and apply a weighted vertex cover algorithm to determine the minimal-cost set of nodes whose removal covers all crossing edges, effectively disconnecting the subgraphs.

  4. Node removal and update: remove the selected nodes from the network, recompute connected components, and repeat the process on the largest remaining connected component.


The GND method has been applied to the network dismantling problem and tested on social, criminal, corruption and power infrastructure networks.

References

[1] Shvydun, S. (2025). Zoo of Centralities: Encyclopedia of Node Metrics in Complex Networks. arXiv: 2511.05122 https://doi.org/10.48550/arXiv.2511.05122
[2] Ren, X. L., Gleinig, N., Helbing, D., & Antulov-Fantulin, N. (2019). Generalized network dismantling. Proceedings of the national academy of sciences, 116(14), 6554-6559. doi: 10.1073/pnas.1806108116.