This paper presents two heuristic algorithms for the distance-based critical node problem (DCNP) that finds k nodes whose removal minimizes the pairwise connection within D hops in the remaining network. The structural properties of the complex networks have not yet been extensively addressed in the literature. Specifically, the community structure of complex networks needs to be considered more in the literature. In this study, we propose a network destruction strategy by extracting the community structure, one of the main structural properties of complex networks. The proposed strategy enables us to develop a scalable greedy algorithm for the DCNP. In addition, a simple evolutionary algorithm with a novel gene representation obtained by the proposed destruction strategy is investigated for the problem. We tested our algorithms on well-known complex networks and compared them with two recently proposed other algorithms for performance evaluation. The proposed greedy algorithm works orders of magnitude faster than other methods and provides comparable solution quality. Our evolutionary algorithm finds the optimal values on most tests.
Article
View Scalable heuristic algorithm for identifying critical nodes in networks