An optimal approach for the critical node problem using semidefinite programming

Detecting critical nodes in complex networks (CNP) has great theoretical and practical significance in many disciplines. The existing formulations for CNP are mostly, as we know, based on the integer linear programming model. However, we observed that, these formulations only considered the sizes but neglected the cohesiveness properties of the connected components in the induced network. To solve the problem and improve the performance of CNP solutions, we construct a novel nonconvex quadratically constrained quadratic programming (QCQP) model and derive its approximation solutions via semidefinite programming (SDP) technique and heuristic algorithms. Various types of synthesized and real-world networks, in the context of different connectivity patterns, are used to validate and verify the effectiveness of the proposed model and algorithm. Experimental results show that our method improved the state of the art of the CNP.