Scalable Heuristic Algorithm for Identifying Critical Nodes in Networks

This paper presents two heuristic algorithms for the distance-based critical node problem (DCNP) that finds k nodes whose removalminimizes the pairwise connection within D hops in the remaining network. The structural properties of complex networks havenot yet been extensively addressed in the literature. Specifically, the community structure of networks needs to be considered inmore detail. In this study, we propose a critical region (CR) detection method by extracting the community structure, one of themain structural properties of networks. The proposed CR detection method enables us to develop a scalable greedy heuristic forthe DCNP. In addition, a simple evolutionary algorithm with a novel representation obtained by the proposed method is investigated.We tested our algorithms on well-known networks and compared them with two recently proposed other algorithms. Theproposed greedy heuristic works orders of magnitude faster than the other methods and provides comparable solution quality. Ourevolutionary algorithm finds the optimal values on most tests