A Simple Genetic Algorithm for the Critical Node Detection Problem | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Simple Genetic Algorithm for the Critical Node Detection Problem

  • Conference paper
  • First Online:
Hybrid Artificial Intelligent Systems (HAIS 2021)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 12886))

Included in the following conference series:

Abstract

The critical node detection problem describes a class of graph problems that involves identifying sets of nodes that influence a given graph metric. One variant of this problem is to find the nodes that - when removed from the graph - maximize the number of connected components in the remaining graph. This is an example of a practical problem with multiple real-world applications in epidemic control, immunization strategies, social networks, biology, etc. This paper proposes the use of a simple GA to identify the set of the critical nodes of the problem without designing special problem specific variation operators. Problem specific information is used only in the fitness function and the constraint handling technique. We show that this simple approach performs as well as state-of-art methods.

This work was supported by a grant of the Romanian National Authority for Scientific Research and Innovation, CNCS - UEFISCDI, project number PN-III-P1-1.1-TE-2019-1633.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 13727
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 17159
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    downloaded from http://individual.utoronto.ca/mventresca/cnd.html, last accessed 05.09.2020.

References

  1. Aringhieri, R., Grosso, A., Hosteins, P., Scatamacchia, R.: A general evolutionary framework for different classes of critical node problems. Eng. Appl. Artif. Intell. 55, 128–145 (2016)

    Article  Google Scholar 

  2. Boginski, V., Commander, C.W.: Identifying critical nodes in protein-protein interaction networks. In: Clustering Challenges in Biological Networks, pp. 153–167. World Scientific (2009)

    Google Scholar 

  3. Borgatti, S.P.: Identifying sets of key players in a social network. Comput. Math. Organ. Theory 12(1), 21–34 (2006). https://doi.org/10.1007/s10588-006-7084-x

    Article  MATH  Google Scholar 

  4. Cacchiani, V., Caprara, A., Toth, P.: Scheduling extra freight trains on railway networks. Transp. Res. Part B: Methodol. 44(2), 215–231 (2010)

    Article  Google Scholar 

  5. Chen, W., Jiang, M., Jiang, C., Zhang, J.: Critical node detection problem for complex network in undirected weighted networks. Phys. A: Stat. Mech. Appl. 538 (2020). https://doi.org/10.1016/j.physa.2019.122862

  6. Cohen, R., Erez, K., Ben-Avraham, D., Havlin, S.: Resilience of the internet to random breakdowns. Phys. Rev. Lett. 85(21), 4626 (2000)

    Article  Google Scholar 

  7. Dagdeviren, O., Akram, V.: An energy-efficient distributed cut vertex detection algorithm for wireless sensor networks. Comput. J. 57(12), 1852–1869 (2013). https://doi.org/10.1093/comjnl/bxt128

    Article  Google Scholar 

  8. Dagdeviren, O., Akram, V., Tavli, B., Yildiz, H., Atilgan, C.: Distributed detection of critical nodes in wireless sensor networks using connected dominating set (2017). https://doi.org/10.1109/ICSENS.2016.7808815

  9. Furini, F., Ljubić, I., Malaguti, E., Paronuzzi, P.: On integer and bilevel formulations for the k-vertex cut problem. Math. Program. Comput. 12(2), 133–164 (2019). https://doi.org/10.1007/s12532-019-00167-1

    Article  MathSciNet  MATH  Google Scholar 

  10. Goh, K.I., Cusick, M.E., Valle, D., Childs, B., Vidal, M., Barabási, A.L.: The human disease network. Proc. Natl. Acad. Sci. 104(21), 8685–8690 (2007)

    Article  Google Scholar 

  11. Iyer, S., Killingback, T., Sundaram, B., Wang, Z.: Attack robustness and centrality of complex networks. PloS One 8(4), e59613 (2013)

    Article  Google Scholar 

  12. Lalou, M., Tahraoui, M., Kheddouci, H.: Component-cardinality-constrained critical node problem in graphs. Discrete Appl. Math. 210, 150–163 (2016). https://doi.org/10.1016/j.dam.2015.01.043

    Article  MathSciNet  MATH  Google Scholar 

  13. Lalou, M., Tahraoui, M., Kheddouci, H.: The critical node detection problem in networks: a survey. Comput. Sci. Rev. 28, 92–117 (2018). https://doi.org/10.1016/j.cosrev.2018.02.002

    Article  MathSciNet  MATH  Google Scholar 

  14. Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219–230 (1980)

    Article  MathSciNet  Google Scholar 

  15. Lobo, F., Lima, C.F., Michalewicz, Z.: Parameter Setting in Evolutionary Algorithms, vol. 54. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-69432-8

    Book  MATH  Google Scholar 

  16. Lozano, M., García-Martínez, C., Rodriguez, F.J., Trujillo, H.M.: Optimizing network attacks by artificial bee colony. Inf. Sci. 377, 30–50 (2017)

    Article  Google Scholar 

  17. Milo, R., et al.: Superfamilies of evolved and designed networks. Science 303(5663), 1538–1542 (2004)

    Article  Google Scholar 

  18. Min, S., Jiandong, L., Yan, S.: Critical nodes detection in mobile ad hoc network, vol. 2, pp. 336–340 (2006). https://doi.org/10.1109/AINA.2006.136

  19. Paudel, N., Georgiadis, L., Italiano, G.: Computing critical nodes in directed graphs. ACM J. Exp. Algorithmics 23 (2018). https://doi.org/10.1145/3228332

  20. Reimand, J., Tooming, L., Peterson, H., Adler, P., Vilo, J.: GraphWeb: mining heterogeneous biological networks for gene modules with functional significance. Nucleic Acids Res. 36, 452–459 (2008)

    Article  Google Scholar 

  21. Rezaei, J., Zare-Mirakabad, F., MirHassani, S., Marashi, S.A.: EIA-CNDP: an exact iterative algorithm for critical node detection problem. Comput. Oper. Res. 127 (2021). https://doi.org/10.1016/j.cor.2020.105138

  22. Shapley, L.S.: 17. A Value for n-Person Games, pp. 307–317. Princeton University Press (1953). DOIurl10.1515/9781400881970-018

    Google Scholar 

  23. Shen, S., Smith, J.C.: Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs. Networks 60(2), 103–119 (2012)

    Article  MathSciNet  Google Scholar 

  24. Shen, S., Smith, J.C., Goli, R.: Exact interdiction models and algorithms for disconnecting networks via node deletions. Discrete Optim. 9(3), 172–188 (2012)

    Article  MathSciNet  Google Scholar 

  25. Ventresca, M., Harrison, K., Ombuki-Berman, B.: The bi-objective critical node detection problem. Eur. J. Oper. Res. 265(3), 895–908 (2018). https://doi.org/10.1016/j.ejor.2017.08.053

    Article  MathSciNet  MATH  Google Scholar 

  26. Ventresca, M.: Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem. Comput. Oper. Res. 39(11), 2763–2775 (2012)

    Article  MathSciNet  Google Scholar 

  27. Veremyev, A., Prokopyev, O.A., Pasiliao, E.L.: An integer programming framework for critical elements detection in graphs. J. Comb. Optim. 28(1), 233–273 (2014). https://doi.org/10.1007/s10878-014-9730-4

    Article  MathSciNet  MATH  Google Scholar 

  28. Yang, R., Huang, L., Lai, Y.C.: Selectivity-based spreading dynamics on complex networks. Phys. Rev. e 78(2), 026111 (2008)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Centre for the Study of Complexity, Babeş-Bolyai University, Cluj-Napoca, Romania

    Mihai-Alexandru Suciu, Noémi Gaskó, Tamás Képes & Rodica Ioana Lung

Authors
  1. Mihai-Alexandru Suciu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Noémi Gaskó
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tamás Képes
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Rodica Ioana Lung
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rodica Ioana Lung .

Editor information

Editors and Affiliations

  1. University of Deusto, Bilbao, Spain

    Hugo Sanjurjo González

  2. University of Deusto, Bilbao, Spain

    Iker Pastor López

  3. University of Deusto, Bilbao, Spain

    Pablo García Bringas

  4. University of A Coruña, A Coruña, Spain

    Héctor Quintián

  5. University of Salamanca, Salamanca, Spain

    Emilio Corchado

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Suciu, MA., Gaskó, N., Képes, T., Lung, R.I. (2021). A Simple Genetic Algorithm for the Critical Node Detection Problem. In: Sanjurjo González, H., Pastor López, I., García Bringas, P., Quintián, H., Corchado, E. (eds) Hybrid Artificial Intelligent Systems. HAIS 2021. Lecture Notes in Computer Science(), vol 12886. Springer, Cham. https://doi.org/10.1007/978-3-030-86271-8_11

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-86271-8_11

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-86270-1

  • Online ISBN: 978-3-030-86271-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation