  The Critical Node Problem (CNP) is concerned with identifying the critical
nodes in a complex network. These nodes play a significant role in maintaining
the connectivity of the network, and removing them can negatively impact
network performance. CNP has been studied extensively due to its numerous
real-world applications. Among the different versions of CNP, CNP-1a has gained
the most popularity. The primary objective of CNP-1a is to minimize the
pair-wise connectivity in the remaining network after deleting a limited number
of nodes from a network. Due to the NP-hard nature of CNP-1a, many
heuristic/metaheuristic algorithms have been proposed to solve this problem.
However, most existing algorithms start with a random initialization, leading
to a high cost of obtaining an optimal solution. To improve the efficiency of
solving CNP-1a, a knowledge-guided genetic algorithm named K2GA has been
proposed. Unlike the standard genetic algorithm framework, K2GA has two main
components: a pretrained neural network to obtain prior knowledge on possible
critical nodes, and a hybrid genetic algorithm with local search for finding an
optimal set of critical nodes based on the knowledge given by the trained
neural network. The local search process utilizes a cut node-based greedy
strategy. The effectiveness of the proposed knowledgeguided genetic algorithm
is verified by experiments on 26 realworld instances of complex networks.
Experimental results show that K2GA outperforms the state-of-the-art algorithms
regarding the best, median, and average objective values, and improves the best
upper bounds on the best objective values for eight realworld instances.
