{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T23:14:25Z","timestamp":1722899665186},"reference-count":30,"publisher":"PeerJ","license":[{"start":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T00:00:00Z","timestamp":1634774400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"Determining the critical nodes in a complex network is an essential computation problem. Several variants of this problem have emerged due to its wide applicability in network analysis. In this article we study the bi-objective critical node detection problem (BOCNDP), which is a new variant of the well-known critical node detection problem, optimizing two objectives at the same time: maximizing the number of connected components and minimizing the variance of their cardinalities. Evolutionary multi-objective algorithms (EMOA) are a straightforward choice to solve this type of problem. We propose three different smart initialization strategies which can be incorporated into any EMOA. These initialization strategies take into account the basic properties of the networks. They are based on the highest degree, random walk (RW) and depth-first search. Numerical experiments were conducted on synthetic and real-world network data. The three different initialization types significantly improve the performance of the EMOA.<\/jats:p>","DOI":"10.7717\/peerj-cs.750","type":"journal-article","created":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T09:04:40Z","timestamp":1634807080000},"page":"e750","source":"Crossref","is-referenced-by-count":7,"title":["Approaching the bi-objective critical node detection problem with a smart initialization-based evolutionary algorithm"],"prefix":"10.7717","volume":"7","author":[{"given":"Eli\u00e9zer","family":"B\u00e9czi","sequence":"first","affiliation":[{"name":"Babe\u015f-Bolyai University of Cluj-Napoca, Cluj-Napoca, Romania"}]},{"given":"No\u00e9mi","family":"Gask\u00f3","sequence":"additional","affiliation":[{"name":"Babe\u015f-Bolyai University of Cluj-Napoca, Cluj-Napoca, Romania"}]}],"member":"4443","published-online":{"date-parts":[[2021,10,21]]},"reference":[{"issue":"16\u201317","key":"10.7717\/peerj-cs.750\/ref-1","doi-asserted-by":"publisher","first-page":"2349","DOI":"10.1016\/j.dam.2013.03.021","article-title":"Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth","volume":"161","author":"Addis","year":"2013","journal-title":"Discrete Applied Mathematics"},{"issue":"7","key":"10.7717\/peerj-cs.750\/ref-2","doi-asserted-by":"publisher","first-page":"2193","DOI":"10.1016\/j.cor.2008.08.016","article-title":"Detecting critical nodes in sparse graphs","volume":"36","author":"Arulselvan","year":"2009","journal-title":"Computers & Operations Research"},{"key":"10.7717\/peerj-cs.750\/ref-3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-0534-5_4","article-title":"Cardinality-constrained critical node detection problem","volume-title":"Performance models and risk management in communications systems. Springer Optimization and Its Applications","volume":"vol. 46","author":"Arulselvan","year":"2011"},{"issue":"2","key":"10.7717\/peerj-cs.750\/ref-4","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.trb.2009.07.007","article-title":"Scheduling extra freight trains on railway networks","volume":"44","author":"Cacchiani","year":"2010","journal-title":"Transportation Research Part B: Methodological"},{"key":"10.7717\/peerj-cs.750\/ref-5","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1109\/4235.996017","article-title":"A fast and elitist multiobjective genetic algorithm: NSGA-ii","volume":"6","author":"Deb","year":"2002","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"10.7717\/peerj-cs.750\/ref-6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17458-2_15","article-title":"Robust optimization of graph partitioning and critical node detection in analyzing networks","volume-title":"Combinatorial Optimization and Applications. COCOA 2010. Lecture Notes in Computer Science","volume":"vol. 6508","author":"Fan","year":"2010"},{"key":"10.7717\/peerj-cs.750\/ref-7","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","article-title":"Community detection in graphs","volume":"486","author":"Fortunato","year":"2010","journal-title":"Physics Reports"},{"issue":"21","key":"10.7717\/peerj-cs.750\/ref-8","doi-asserted-by":"publisher","first-page":"8685","DOI":"10.1073\/pnas.0701361104","article-title":"The human disease network","volume":"104","author":"Goh","year":"2007","journal-title":"Proceedings of the National Academy of Sciences of the United States of America"},{"key":"10.7717\/peerj-cs.750\/ref-9","first-page":"2585","article-title":"A review of population initialization techniques for evolutionary algorithms","author":"Kazimipour","year":"2014"},{"key":"10.7717\/peerj-cs.750\/ref-10","first-page":"137","article-title":"Maximizing the spread of influence through a social network","author":"Kempe","year":"2003"},{"key":"10.7717\/peerj-cs.750\/ref-11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15883-4_8","article-title":"Finding critical nodes for inhibiting diffusion of complex contagions in social networks","volume-title":"Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2010. Lecture Notes in Computer Science","volume":"vol. 6322","author":"Kuhlman","year":"2010"},{"key":"10.7717\/peerj-cs.750\/ref-12","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/j.dam.2015.01.043","article-title":"Component-cardinality-constrained critical node problem in graphs","volume":"210","author":"Lalou","year":"2016","journal-title":"Discrete Applied Mathematics"},{"key":"10.7717\/peerj-cs.750\/ref-13","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.cosrev.2018.02.002","article-title":"The critical node detection problem in networks: a survey","volume":"28","author":"Lalou","year":"2018","journal-title":"Computer Science Review"},{"key":"10.7717\/peerj-cs.750\/ref-14","article-title":"Snap datasets: Stanford large network dataset collection","author":"Leskovec","year":"2014"},{"issue":"23","key":"10.7717\/peerj-cs.750\/ref-15","doi-asserted-by":"publisher","first-page":"12729","DOI":"10.1007\/s00500-019-03824-8","article-title":"The bi-objective critical node detection problem with minimum pairwise connectivity and cost: theory and algorithms","volume":"23","author":"Li","year":"2019","journal-title":"Soft Computing"},{"issue":"7","key":"10.7717\/peerj-cs.750\/ref-16","doi-asserted-by":"publisher","first-page":"1019","DOI":"10.1002\/asi.20591","article-title":"The link-prediction problem for social networks","volume":"58","author":"Liben-Nowell","year":"2007","journal-title":"Journal of the American Society for Information Science and Technology"},{"issue":"2","key":"10.7717\/peerj-cs.750\/ref-17","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1093\/bib\/bbz011","article-title":"Computational methods for identifying the critical nodes in biological networks","volume":"21","author":"Liu","year":"2020","journal-title":"Briefings in Bioinformatics"},{"issue":"3","key":"10.7717\/peerj-cs.750\/ref-18","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/s10898-006-9056-6","article-title":"On initial populations of a genetic algorithm for continuous optimization problems","volume":"37","author":"Maaranen","year":"2007","journal-title":"Journal of Global Optimization"},{"issue":"5663","key":"10.7717\/peerj-cs.750\/ref-19","doi-asserted-by":"publisher","first-page":"1538","DOI":"10.1126\/science.1089167","article-title":"Superfamilies of evolved and designed networks","volume":"303","author":"Milo","year":"2004","journal-title":"Science"},{"key":"10.7717\/peerj-cs.750\/ref-20","article-title":"Why anchorage is not (that) important: Binary ties and sample selection. online]","author":"Opsahl","year":"2011"},{"issue":"2","key":"10.7717\/peerj-cs.750\/ref-21","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.socnet.2009.02.002","article-title":"Clustering in weighted networks","volume":"31","author":"Opsahl","year":"2009","journal-title":"Social Networks"},{"key":"10.7717\/peerj-cs.750\/ref-22","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1093\/nar\/gkn230","article-title":"Graphweb: mining heterogeneous biological networks for gene modules with functional significance","volume":"36","author":"Reimand","year":"2008","journal-title":"Nucleic Acids Research"},{"key":"10.7717\/peerj-cs.750\/ref-23","doi-asserted-by":"crossref","DOI":"10.1609\/aaai.v29i1.9277","article-title":"The network data repository with interactive graph analytics and visualization","volume-title":"Twenty-Ninth AAAI Conference on Artificial Intelligence","author":"Rossi","year":"2015"},{"issue":"3","key":"10.7717\/peerj-cs.750\/ref-24","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1007\/s10589-012-9458-y","article-title":"Branch and cut algorithms for detecting critical nodes in undirected graphs","volume":"53","author":"Summa","year":"2012","journal-title":"Computational Optimization and Applications"},{"issue":"5","key":"10.7717\/peerj-cs.750\/ref-25","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1080\/10020070612330019","article-title":"Epidemic dynamics on complex networks","volume":"16","author":"Tao","year":"2006","journal-title":"Progress in Natural Science"},{"issue":"11","key":"10.7717\/peerj-cs.750\/ref-26","doi-asserted-by":"publisher","first-page":"2763","DOI":"10.1016\/j.cor.2012.02.008","article-title":"Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem","volume":"39","author":"Ventresca","year":"2012","journal-title":"Computers & Operations Research"},{"issue":"3","key":"10.7717\/peerj-cs.750\/ref-27","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1016\/j.ejor.2017.08.053","article-title":"The bi-objective critical node detection problem","volume":"265","author":"Ventresca","year":"2018","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"10.7717\/peerj-cs.750\/ref-28","doi-asserted-by":"publisher","first-page":"026111","DOI":"10.1103\/PhysRevE.78.026111","article-title":"Selectivity-based spreading dynamics on complex networks","volume":"78","author":"Yang","year":"2008","journal-title":"Physical Review E"},{"key":"10.7717\/peerj-cs.750\/ref-29","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0056872","article-title":"Multiobjective optimization using evolutionary algorithms\u2014a comparative case study","volume-title":"Parallel Problem Solving from Nature \u2013 PPSN V. PPSN 1998. Lecture Notes in Computer Science","volume":"vol. 1498","author":"Zitzler","year":"1998"},{"issue":"4","key":"10.7717\/peerj-cs.750\/ref-30","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1109\/4235.797969","article-title":"Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach","volume":"3","author":"Zitzler","year":"1999","journal-title":"IEEE Transactions on Evolutionary Computation"}],"container-title":["PeerJ Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/peerj.com\/articles\/cs-750.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/peerj.com\/articles\/cs-750.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/peerj.com\/articles\/cs-750.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/peerj.com\/articles\/cs-750.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T03:53:48Z","timestamp":1673582028000},"score":1,"resource":{"primary":{"URL":"https:\/\/peerj.com\/articles\/cs-750"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,21]]},"references-count":30,"alternative-id":["10.7717\/peerj-cs.750"],"URL":"https:\/\/doi.org\/10.7717\/peerj-cs.750","archive":["CLOCKSS","LOCKSS","Portico"],"relation":{},"ISSN":["2376-5992"],"issn-type":[{"value":"2376-5992","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,21]]},"article-number":"e750"}}