Hongyuan Ding1, Jiaqi Li1, Man Li2, Weichao Ding1
1Department of Computer Science and Engineering, East China University of Science and Technology, Shanghai, China
2Songjiang Power Supply Company, State Grid Shanghai Municipal Electric Power Company, Shanghai, China
The critical node detection problems (CNDPs) have important applications in network security, smart grid, epidemic control, drug design, and risk assessment. The critical node problem (CNP) is one of well-known CNDPs, which is NP-hard. In this work, we combine frequent pattern mining with evolutionary algorithm for solving CNP, where pattern mined from high-quality solutions are used to guide the construction of offspring solution. More specifically, based on the memetic algorithm (Memetic Algorithm for CNP, MACNP), frequent pattern mining was integrated into the memetic algorithm framework. The frequent patterns mined were used to construct the offspring solution, instead of crossover operator in MACNP. In the research, the nodes in frequent items set were directly fixed as part of the offspring solution. So the offspring solution inherited excellent properties from more parent solutions, thus forming the algorithm called Frequent Pattern Based Search for CNP (FPBS-CNP). This strategy improved the algorithm efficiency. Experiments were conducted on synthetic and real-world benchmark. We experimentally compare FPBS-CNP with MACNP. The experiment results show that FPBS-CNP performs well on small instances and has potential in solving large instances.
Critical node detection problem; Frequent pattern mining; Evolutionary algorithm; Memetic algorithm
Hongyuan Ding, Jiaqi Li, Man Li, Weichao Ding. Research on Combining Pattern Mining and Evolutionary Algorithm for Critical Node Detection Problems. International Journal of Frontiers in Engineering Technology (2022), Vol. 4, Issue 4: 41-52. https://doi.org/10.25236/IJFET.2022.040406.
 S. Boccaletti, V. Latora, Y. Moreno, et al. Complex networks: Structure and dynamics. Physics Reports, 2006, 424:175-308.
 S. P. Borgatti. Identifying sets of key players in a social network. Computational and Mathematical Organization Theory, 2006, 12:21-34.
 Arulselvan A, Commander C W, Elefteriadou L, et al. Detecting critical nodes in sparse graphs. Computer & Operations Research, 2009, 36(7):2193-2200.
 Summa M D, Grosso A, Locatelli M. Branch and cut algorithm for detecting critical nodes in undirected graphs. Computational Optimization and Applications, 2012, 53(3):649-680.
 Veremyev A, Boginski V, Pasiliao E L. Exact identification of critical nodes in sparse networks via new compact formulations. Optimization Letter, 2014, 8(4):1245-1259.
 Purevsuren D, Cui G, Qu M, et al. Hybridization of GRASP with exterior path relinking for identifying critical nodes in graphs. IAENG International Journal of Computer Science, 2017, 44(2):1-9.
 Aringhieri R, Grosso A, Hosteins P, et al. A general evolutionary framework for different classes of critical node problems.Engineering Applications of Artificial Intelligence, 2016, 55:128-145.
 Wu Z, Research on the Critical Node Detection Problem based on the Local Characteristic of Network[D]. Shanxi University, 2019.
 Cao J, Min H, Liu S, et al. Mixed heuristic and greedy strategies based algorithm for influence maximization in social networks. Journal of Southeast University(Natural Science Edition) , 2016, 46(05):950-956.
 Zhou Y, Hao J, Glover F. Memetic search for identifying critical nodes in sparse graphs. IEEE Transactions on Cybernetics, 2019, 49(10): 3699-3712.
 Zhou Y, Hao J, Fu Z, et al. Variable population memetic search: A case study on the critical node problem. IEEE Transactions on Evolutionary Computation, 2021, 25(1):187-200.
 Han J, Jian P, Yin Y, et al. Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining & Knowledge Discovery, 2004, 8(1):53-87.
 Grahne G, Zhu J. High performance mining of maximal frequent itemsets[A]. In: Proceedings of the 3rd IEEE International Conference on Data Mining[C]. Melbourne, 2003.
 Grahne G, Zhu J. Efficiently using prefix-trees in mining frequent itemsets[A]. In: Proceedings of the ICDM 2003 Workshop on Frequent Itemset Mining Implementations[C]. Frequent Itemset Mining Implementations. Melbourne, 2003.
 Zhou Y, Hao J, Duval B. Frequent pattern-based search: A case study on the quadratic assignment problem. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2020, 1-13.
 Aiex R M, Resende M, Ribeiro C C. TTT plots: A perl program to create time-to-target plots. Optimization Letters, 2007, 1(4):355-366.