Dismantling network by removing weak vertices

The network dismantling problem focuses on finding and removing the minimum set of vertices to decrease network's connectivity significantly. Spectral-based methods have attracted considerable attention. However, these methods tend to divide the network into many communities, thereby ignoring the vertices that do not belong to any of these communities. These vertices are typically weak in terms of robustness. This paper proposes a new spectral-based method that divides the network into communities and a set of weak vertices. The proposed method employs the second smallest eigenvector of the Laplacian matrix to detect weak vertices, then removes the identified vertices greedily until the size of the largest connected components of the remaining network reaches the target level. The experimental results of real networks demonstrate that the proposed method performs better than state-of-the-art methods.