We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 39 Issue 6
December  2024
Turn off MathJax
Article Contents
Abstract
Conflict of Interest
References
Related Articles
Supplements
Chen ZH, Cai SW, Gao J et al. Heuristic search with cut point based strategy for critical node problem. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 39(6): 1328−1340 Nov. 2024. DOI: 10.1007/s11390-024-2850-0.
Citation: Chen ZH, Cai SW, Gao J et al. Heuristic search with cut point based strategy for critical node problem. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 39(6): 1328−1340 Nov. 2024. DOI: 10.1007/s11390-024-2850-0.
shu

Heuristic Search with Cut Point Based Strategy for Critical Node Problem

  • 1.

    School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing 101408, China

  • 2.

    Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China

  • 3.

    College of Information Science and Technology, Northeast Normal University, Changchun 130024, China

  • 4.

    School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China

  • 5.

    SeedMath Technology Limited, Beijing 100086, China

Funds: This work was supported by the Strategic Priority Research Program of the Chinese Academy of Sciences under Grant Nos. XDA0320000 and XDA0320300, and the National Natural Science Foundation of China under Grant No. 61972063.
More Information
  • Author Bio:

    Zhi-Han Chen received his B.S. degree in computer science and technology from Peking University, Beijing, in 2020. He is currently pursuing his Ph.D. degree with the School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing. His current research interests include constraint solving and electronic design automation

    Shao-Wei Cai received his Ph.D. degree in computer science from Peking University, Beijing, in 2012. He is currently a professor in Institute of Software, Chinese Academy of Sciences, Beijing. He has developed efficient SAT/SMT/MaxSAT solvers, which have received many awards in SAT/SMT/MaxSAT competitions (or evaluations). He has won the best paper award of SAT 2021 conference. His current research interests include constraint solving and electronic design automation

    Jian Gao received his Ph.D. degree in computer application technology from Dalian Maritime University, Dalian. He is currently a professor of computer science in Northeast Normal University, Changchun. His research interests include automated reasoning, constraint programming and heuristics

    Shi-Ke Ge received his B.E. degree in computer science and technology from Shenyang University of Technology, Shenyang, in 2021. He is currently a master degree candidate in computer science and technology from Dalian University of Technology, Dalian. His research interest includes constraint solving

    Chan-Juan Liu received her Ph.D. degree in computer software and theory from Peking University, Beijing, in 2016. She is currently an associate professor with School of Computer Science and Technology, Dalian University of Technology, Dalian. Her current research interests include game theory and multi-agent decision making

    Jin-Kun Lin received his Ph.D. degree in computer science and theory from Peking University, Beijing, in 2018. He is currently the chief technology officer with SeedMath Technology Limited, Beijing. His current research interests include software testing and heuristic search

  • Corresponding author:

    caisw@ios.ac.cn

  • Received Date: September 20, 2022
  • Accepted Date: July 02, 2024
    Abstract

  • The critical node problem (CNP) aims to deal with critical node identification in a graph, which has extensive applications in many fields. Solving CNP is a challenging task due to its computational complexity, and it attracts much attention from both academia and industry. In this paper, we propose a population-based heuristic search algorithm called CPHS (Cut Point Based Heuristic Search) to solve CNP, which integrates two main ideas. The first one is a cut point based greedy strategy in the local search, and the second one involves the functions used to update the solution pool of the algorithm. Besides, a mutation strategy is applied to solutions with probability based on the overall average similarity to maintain the diversity of the solution pool. Experiments are performed on a synthetic benchmark, a real-world benchmark, and a large-scale network benchmark to evaluate our algorithm. Compared with state-of-the-art algorithms, our algorithm has better performance in terms of both solution quality and run time on all the three benchmarks.

    • FullText(HTML)
    • References (33)
  • [1]
    Shen Y, Nguyen N P, Xuan Y, Thai M T. On the discovery of critical links and nodes for assessing network vulnerability. IEEE/ACM Trans. Networking, 2013, 21(3): 963–973. DOI: 10.1109/TNET.2012.2215882.
    [2]
    Boginski V, Commander C W. Identifying critical nodes in protein-protein interaction networks. In Clustering Challenges in Biological Networks, Butenko S, Chaovalitwongse W A, Pardalos P M (eds.), World Scientific, 2009, pp.153–167. DOI: 10.1142/9789812771667_0007.
    [3]
    Tomaino V, Arulselvan A, Veltri P, Pardalos P M. Studying connectivity properties in human protein–protein interaction network in cancer pathway. In Data Mining for Biomarker Discovery, Pardalos P M, Xanthopoulos P, Zervakis M (eds.), Springer-Verlag, 2012, pp.187–197. DOI: 10.1007/978-1-4614-2107-8_10.
    [4]
    Nguyen D T, Shen Y, Thai M T. Detecting critical nodes in interdependent power networks for vulnerability assessment. IEEE Trans. Smart Grid, 2013, 4(1): 151–159. DOI: 10.1109/TSG.2012.2229398.
    [5]
    Aspnes J, Chang K, Yampolskiy A. Inoculation strategies for victims of viruses and the sum-of-squares partition problem. Journal of Computer and System Sciences, 2006, 72(6): 1077–1093. DOI: 10.1016/j.jcss.2006.02.003.
    [6]
    Kempe D, Kleinberg J, Tardos É. Maximizing the spread of influence through a social network. In Proc. the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug. 2003, pp.137–146. DOI: 10.1145/956750.956769.
    [7]
    Borgatti S P. Identifying sets of key players in a social network. Computational & Mathematical Organization Theory, 2006, 12: 21–34. DOI: 10.1007/s10588-006-7084-x.
    [8]
    Arulselvan A, Commander C W, Elefteriadou L, Pardalos P M. Detecting critical nodes in sparse graphs. Computers & Operations Research, 2009, 36(7): 2193–2200. DOI: 10.1016/j.cor.2008.08.016.
    [9]
    Shen S, Smith J C. Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs. Networks, 2012, 60(2): 103–119. DOI: 10.1002/net.20464.
    [10]
    Lalou M, Tahraoui M A, Kheddouci H. The critical node detection problem in networks: A survey. Computer Science Review, 2018, 28: 92–117. DOI: 10.1016/j.cosrev.2018.02.002.
    [11]
    Di Summa M, Grosso A, Locatelli M. Branch and cut algorithms for detecting critical nodes in undirected graphs. Computational Optimization and Applications, 2012, 53(3): 649–680. DOI: 10.1007/s10589-012-9458-y.
    [12]
    Pavlikov K. Improved formulations for minimum connectivity network interdiction problems. Computers & Operations Research, 2018, 97: 48–57. DOI: 10.1016/j.cor.2018.04.012.
    [13]
    Dinh T N, Thai M T. Precise structural vulnerability assessment via mathematical programming. In Proc. the 2011 Military Communications Conference, Nov. 2011, pp.1351–1356. DOI: 10.1109/MILCOM.2011.6127492.
    [14]
    Walteros J L, Veremyev A, Pardalos P M, Pasiliao E L. Detecting critical node structures on graphs: A mathematical programming approach. Networks, 2019, 73(1): 48–88. DOI: 10.1002/net.21834.
    [15]
    Aringhieri R, Grosso A, Hosteins P, Scatamacchia R. VNS solutions for the critical node problem. Electronic Notes in Discrete Mathematics, 2015, 47: 37–44. DOI: 10.1016/j.endm.2014.11.006.
    [16]
    Ventresca M, Aleman D. A derandomized approximation algorithm for the critical node detection problem. Computers & Operations Research, 2014, 43: 261–270. DOI: 10.1016/j.cor.2013.09.012.
    [17]
    Ventresca M. Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem. Computers & Operations Research, 2012, 39(11): 2763–2775. DOI: 10.1016/j.cor.2012.02.008.
    [18]
    Ventresca M, Aleman D. A fast greedy algorithm for the critical node detection problem. In Proc. the 8th International Conference on Combinatorial Optimization and Applications, Dec. 2014, pp.603–612. DOI: 10.1007/978-3-319-12691-3_45.
    [19]
    Aringhieri R, Grosso A, Hosteins P, Scatamacchia R. Local search metaheuristics for the critical node problem. Networks, 2016, 67(3): 209–221. DOI: 10.1002/net.21671.
    [20]
    Pullan W. Heuristic identification of critical nodes in sparse real-world graphs. Journal of Heuristics, 2015, 21(5): 577–598. DOI: 10.1007/s10732-015-9290-5.
    [21]
    Zhou Y, Hao J K, Glover F. Memetic search for identifying critical nodes in sparse graphs. IEEE Trans. Cybernetics, 2019, 49(10): 3699–3712. DOI: 10.1109/TCYB.2018.2848116.
    [22]
    Addis B, Aringhieri R, Grosso A, Hosteins P. Hybrid constructive heuristics for the critical node problem. Annals of Operations Research, 2016, 238(1/2): 637–649. DOI: 10.1007/s10479-016-2110-y.
    [23]
    Aringhieri R, Grosso A, Hosteins P, Scatamacchia R. A general evolutionary framework for different classes of critical node problems. Engineering Applications of Artificial Intelligence, 2016, 55: 128–145. DOI: 10.1016/j.engappai.2016.06.010.
    [24]
    Zhou Y, Hao J K, Fu Z H, Wang Z, Lai X. Variable population memetic search: A case study on the critical node problem. IEEE Trans. Evolutionary Computation, 2021, 25(1): 187–200. DOI: 10.1109/TEVC.2020.3011959.
    [25]
    Zhou Y, Hao J K. A fast heuristic algorithm for the critical node problem. In Proc. the Genetic and Evolutionary Computation Conference Companion, Jul. 2017, pp.121–122. DOI: 10.1145/3067695.3075993.
    [26]
    Tarjan R. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1972, 1(2): 146–160. DOI: 10.1137/0201010.
    [27]
    Lü Z, Hao J K. A memetic algorithm for graph coloring. European Journal of Operational Research, 2010, 203(1): 241–250. DOI: 10.1016/j.ejor.2009.07.016.
    [28]
    Rossi R A, Ahmed N K. The network data repository with interactive graph analytics and visualization. In Proc. the 29th AAAI Conference on Artificial Intelligence, Jan. 2015, pp.4292–4293. DOI: 10.1609/aaai.v29i1.9277.
    [29]
    Rossi R A, Gleich D F, Gebremedhin A H, Patwary M M A. Fast maximum clique algorithms for large graphs. In Proc. the 23rd Int. Conf. World Wide Web, Apr. 2014, pp.365–366. DOI: 10.1145/2567948.2577283.
    [30]
    Lin J, Cai S, Luo C, Su K. A reduction based method for coloring very large graphs. In Proc. the 26th International Joint Conference on Artificial Intelligence, Aug. 2017, pp.517–523. DOI: 10.24963/ijcai.2017/73.
    [31]
    Cai S, Hou W, Wang Y, Luo C, Lin Q. Two-goal local search and inference rules for minimum dominating set. In Proc. the 29th International Joint Conference on Artificial Intelligence, Jul. 2020, pp.1467–1473. DOI: 10.24963/ijcai.2020/204.
    [32]
    Conover W J. Practical Nonparametric Statistics (3rd edition). John Wiley & Sons, 1999.
    [33]
    Luo C, Zhao Q, Cai S, Zhang H, Hu C. SamplingCA: Effective and efficient sampling-based pairwise testing for highly configurable software systems. In Proc. the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, Nov. 2022, pp.1185–1197. DOI: 10.1145/3540250.3549155.
    • Relative Articles

  • Related Articles

    [1]Nuo Qun, Hang Yan, Xi-Peng Qiu, Xuan-Jing Huang. Chinese Word Segmentation via BiLSTM+Semi-CRF with Relay Node[J]. Journal of Computer Science and Technology, 2020, 35(5): 1115-1126. DOI: 10.1007/s11390-020-9576-4
    [2]CHEN Yangjun. On the Arc Consistency Problem[J]. Journal of Computer Science and Technology, 1999, 14(4): 298-308.
    [3]GU Jun, GU Qianping, DU Dingzhu. On Optimizing the Satisfiability (SAT) Problem[J]. Journal of Computer Science and Technology, 1999, 14(1): 1-17.
    [4]Shuai Dianxun. Hyper-Distributed Hyper-Parallel Implementation of Heuristic Search of Implicit AND/OR Graph[J]. Journal of Computer Science and Technology, 1997, 12(6): 532-542.
    [5]Shuai Dianxun. New Heuristic Distributed Parallel Algorithms for Searching and Planning[J]. Journal of Computer Science and Technology, 1995, 10(4): 354-374.
    [6]Li Weidong, Wei Daozheng. Test Derivation Through Critical Path Transitions[J]. Journal of Computer Science and Technology, 1992, 7(1): 12-18.
    [7]Zhang Bo, Zhang Ling. Why SA Can Beat the Exponential Explosion in Heuristic Search[J]. Journal of Computer Science and Technology, 1990, 5(3): 259-265.
    [8]Zhang Bo, Zhang Ling. The Comparison between the Statistical Heuristic Search and A[J]. Journal of Computer Science and Technology, 1989, 4(2): 126-132.
    [9]Li Hao, Liu Qun. A Problem of Tree Graph[J]. Journal of Computer Science and Technology, 1989, 4(1): 61-66.
    [10]Zhang Bo, Zhang Ling. Statistical Heuristic Search[J]. Journal of Computer Science and Technology, 1987, 2(1): 1-11.
    • Supplements (3)

  • Others

Catalog

    Get Citation
    PDF
    XML
    Read Online
    Article views (89) PDF downloads (11) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return