The Critical Node Detection Problem in networks: A survey

Kempe, 2005, Influential nodes in a diffusion model for social networks, 1127 Corley, 1982, Most vital links and nodes in weighted networks, Oper. Res. Lett., 1, 157, 10.1016/0167-6377(82)90020-7 Li, 2011, Finding influential mediators in social networks, 75 Borgatti, 2006, Identifying sets of key players in a social network, Comput. Math. Org. Theory, 12, 21, 10.1007/s10588-006-7084-x Hellwig, 2008, Maximally edge-connected and vertex-connected graphs and digraphs: A survey, Discrete Math., 308, 3265, 10.1016/j.disc.2007.06.035 Fjällström, 1998 Pothen, 1997, Graph partitioning algorithms with applications to scientific computing, 323 Buluç, 2016, Recent advances in graph partitioning, 117 Goldschmidt, 1994, A polynomial algorithm for the k-cut problem for fixed k, Math. Oper. Res., 19, 24, 10.1287/moor.19.1.24 He, 1991, An improved algorithm for the planar 3-cut problem, J. Algorithms, 12, 23, 10.1016/0196-6774(91)90021-P Costa, 2005, Minimal multicut and maximal integer multiflow: A survey, European J. Oper. Res., 162, 55, 10.1016/j.ejor.2003.10.037 Garg, 1997, Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica, 18, 3, 10.1007/BF02523685 Guo, 2005, Fixed-parameter tractability and data reduction for multicut in trees, Networks, 46, 124, 10.1002/net.20081 Chopra, 1991, On the multiway cut polyhedron, Networks, 21, 51, 10.1002/net.3230210106 Dahlhaus, 1994, The complexity of multiterminal cuts, SIAM J. Comput., 23, 864, 10.1137/S0097539792225297 Chopra, 1996, Extended formulations for the A-cut problem, Math. Program., 73, 7, 10.1007/BF02592096 Avidor, 2007, The multi-multiway cut problem, Theoret. Comput. Sci., 377, 35, 10.1016/j.tcs.2007.02.026 Bui, 1992, Finding good approximate vertex and edge partitions is NP-hard, Inform. Process. Lett., 42, 153, 10.1016/0020-0190(92)90140-Q Lipton, 1979, A separator theorem for planar graphs, SIAM J. Appl. Math., 36, 177, 10.1137/0136016 Fukuyama, 2006, NP-completeness of the planar separator problems, J. Graph Algorithms Appl., 10, 317, 10.7155/jgaa.00130 de Souza, 2005, The vertex separator problem: algorithms and computations, Math. Program., 103, 609, 10.1007/s10107-005-0573-8 Biha, 2011, An exact algorithm for solving the vertex separator problem, J. Global Optim., 49, 425, 10.1007/s10898-010-9568-y U. Benlic, J.-K. Hao, Breakout local search for the vertex separator problem, in: IJCAI, 2013, pp. 461–467. Chen, 2009, An improved parameterized algorithm for the minimum node multiway cut problem, Algorithmica, 55, 1, 10.1007/s00453-007-9130-6 Guillemot, 2008, Fpt algorithms for path-transversals and cycle-transversals problems in graphs, 129 Călinescu, 2003, Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width, J. Algorithms, 48, 333, 10.1016/S0196-6774(03)00073-7 Papadopoulos, 2012, Restricted vertex multicut on permutation graphs, Discrete Appl. Math., 160, 1791, 10.1016/j.dam.2012.03.021 Guo, 2008, Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs, European J. Oper. Res., 186, 542, 10.1016/j.ejor.2007.02.014 Marx, 2006, Parameterized graph separation problems, Theoret. Comput. Sci., 351, 394, 10.1016/j.tcs.2005.10.007 Michael, 1979 Lewis, 1980, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci., 20, 219, 10.1016/0022-0000(80)90060-4 Yannakakis, 1981, Node-deletion problems on bipartite graphs, SIAM J. Comput., 10, 310, 10.1137/0210022 Arulselvan, 2009, Detecting critical nodes in sparse graphs, Comput. Oper. Res., 36, 2193, 10.1016/j.cor.2008.08.016 Boginski, 2009, Identifying critical nodes in protein–protein interaction networks, Clustering Challenges Biol. Netw., 153, 10.1142/9789812771667_0007 Tomaino, 2012, Studying connectivity properties in human protein–protein interaction network in cancer pathway, 187 Dinh, 2011, Precise structural vulnerability assessment via mathematical programming, 1351 Shen, 2013, On the discovery of critical links and nodes for assessing network vulnerability, IEEE/ACM Trans. Netw., 21, 963, 10.1109/TNET.2012.2215882 Shen, 2012, Adaptive algorithms for detecting critical links and nodes in dynamic networks, 1 Nguyen, 2013, Detecting critical nodes in interdependent power networks for vulnerability assessment, Smart Grid, IEEE Trans., 4, 151, 10.1109/TSG.2012.2229398 He, 2011, Controlling infection by blocking nodes and links simultaneously, 206 Aspnes, 2005, Inoculation strategies for victims of viruses and the sum-of-squares partition problem, 43 Bondy, 1976 Golumbic, 2004 Jungck, 1982, Computer-assisted sequencing, interval graphs, and molecular evolution, Biosystems, 15, 259, 10.1016/0303-2647(82)90010-7 Pal, 2009, Interval tree and its applications, Adv. Model. Optim., 11, 211 Shen, 2012, Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs, Networks, 60, 103, 10.1002/net.20464 Robertson, 1986, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7, 309, 10.1016/0196-6774(86)90023-4 Bodlaender, 1986 Bodlaender, 1994, A tourist guide through treewidth, Acta Cybernet., 11, 1 Bodlaender, 2006, Treewidth: characterizations, applications, and computations, WG, 4271, 1 Downey, 2012 Flum, 2006 Cohen, 2000, Resilience of the internet to random breakdowns, Phys. Rev. Lett., 85, 4626, 10.1103/PhysRevLett.85.4626 Albert, 2000, Error and attack tolerance of complex networks, Nature, 406, 378, 10.1038/35019019 Faramondi, 2017, Performance analysis of single and multi-objective approaches for the critical node detection problem, 315 Festa, 1999, Feedback set problems, 209 Schieber, 1995, The Complexity of Finding Most Vital Arcs and Nodes Khachiyan, 2008, On short paths interdiction problems: total and node-wise limited interdiction, Theory Comput. Syst., 43, 204, 10.1007/s00224-007-9025-6 Choi, 1989, Graph bipartization and via minimization, SIAM J. Discrete Math., 2, 38, 10.1137/0402004 Marx, 2010, Chordal deletion is fixed-parameter tractable, Algorithmica, 57, 747, 10.1007/s00453-008-9233-8 Marx, 2012, Obtaining a planar graph by vertex deletion, Algorithmica, 62, 807, 10.1007/s00453-010-9484-z Arulselvan, 2011, Cardinality- constrained critical node detection problem, 79 Dinh, 2010, On approximation of new optimization methods for assessing network vulnerability, 1 Shen, 2012, Exact interdiction models and algorithms for disconnecting networks via node deletions, Discrete Optim., 9, 172, 10.1016/j.disopt.2012.07.001 Addis, 2013, Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth, Discrete Appl. Math., 161, 2349, 10.1016/j.dam.2013.03.021 Berger, 2014, Complexity and approximability of the k-way vertex cut, Networks, 63, 170, 10.1002/net.21534 Di Summa, 2011, Complexity of the critical node problem over trees, Comput. Oper. Res., 38, 1766, 10.1016/j.cor.2011.02.016 Lalou, 2016, Component-cardinality-constrained critical node problem in graphs, Discrete Appl. Math., 210, 150, 10.1016/j.dam.2015.01.043 Freeman, 1979, Centrality in social networks conceptual clarification, Soc. Netw., 1, 215, 10.1016/0378-8733(78)90021-7 Chartrand, 2006 Bader, 2007, Approximating betweenness centrality, 124 Brandes, 2001, A faster algorithm for betweenness centrality, J. Math. Sociol., 25, 163, 10.1080/0022250X.2001.9990249 Di Summa, 2012, Branch and cut algorithms for detecting critical nodes in undirected graphs, Comput. Optim. Appl., 53, 649, 10.1007/s10589-012-9458-y Oosten, 2007, Disconnecting graphs by removing vertices: a polyhedral approach, Stat. Neerl., 61, 35, 10.1111/j.1467-9574.2007.00350.x Arulselvan, 2007, Managing network risk via critical node identification Ventresca, 2014, A fast greedy algorithm for the critical node detection problem, 603 Dinh, 2015, Assessing attack vulnerability in networks with uncertainty Ventresca, 2014, A derandomized approximation algorithm for the critical node detection problem, Comput. Oper. Res., 43, 261, 10.1016/j.cor.2013.09.012 Ventresca, 2014, A region growing algorithm for detecting critical nodes, 593 Ventresca, 2014, A randomized algorithm with local search for containment of pandemic disease spread, Comput. Oper. Res., 48, 11, 10.1016/j.cor.2014.02.003 Ventresca, 2012, Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem, Comput. Oper. Res., 39, 2763, 10.1016/j.cor.2012.02.008 Veremyev, 2014, An integer programming framework for critical elements detection in graphs, J. Combin. Optim., 28, 233, 10.1007/s10878-014-9730-4 Aringhieri, 2016, A general evolutionary framework for different classes of critical node problems, Eng. Appl. Artif. Intell., 55, 128, 10.1016/j.engappai.2016.06.010 Hermelin, 2016, Parameterized complexity of critical node cuts, Theoret. Comput. Sci., 651, 62, 10.1016/j.tcs.2016.08.018 Veremyev, 2014, Exact identification of critical nodes in sparse networks via new compact formulations, Optim. Lett., 8, 1245, 10.1007/s11590-013-0666-x Aringhieri, 2015, VNS solutions for the critical node problem, Electron. Notes Discrete Math., 47, 37, 10.1016/j.endm.2014.11.006 Addis, 2016, Hybrid constructive heuristics for the critical node problem, Ann. Oper. Res., 238, 637, 10.1007/s10479-016-2110-y Aringhieri, 2016, Local search metaheuristics for the critical node problem, Networks, 67, 209, 10.1002/net.21671 Pullan, 2015, Heuristic identification of critical nodes in sparse real-world graphs, J. Heuristics, 21, 577, 10.1007/s10732-015-9290-5 Purevsuren, 2016, Heuristic algorithm for identifying critical nodes in graphs, Adv. Comput. Sci.: Int. J., 5, 1 Y. Shen, M.T. Thai, Network vulnerability assessment under cascading failures, in: 2013 IEEE Global Communications Conference, GLOBECOM 2013, Atlanta, GA, USA, December 9-13, 2013, 2013, pp. 1526–1531. Ventresca, 2015, An experimental evaluation of multi-objective evolutionary algorithms for detecting critical nodes in complex networks, 164 Balas, 2005, The vertex separator problem: a polyhedral investigation, Math. Program., 103, 583, 10.1007/s10107-005-0574-7 Dinh, 2015, Network under joint node and link attacks: Vulnerability assessment methods and analysis, IEEE/ACM Trans. Netw., 23, 1001, 10.1109/TNET.2014.2317486 Cormen, 2009 Ventresca, 2018, The bi-objective critical node detection problem, European J. Oper. Res., 265, 895, 10.1016/j.ejor.2017.08.053 Wood, 1993, Deterministic network interdiction, Math. Comput. Modelling, 17, 1, 10.1016/0895-7177(93)90236-R Garey, 1974, Some simplified NP-complete problems, 47 Dinur, 2005, On the hardness of approximating minimum vertex cover, Ann. of Math., 439, 10.4007/annals.2005.162.439 Håstad, 1996, Clique is hard to approximate within n1−ϵ, 627 Myung, 2004, A cutting plane algorithm for computing k-edge survivability of a network, European J. Oper. Res., 156, 579, 10.1016/S0377-2217(03)00135-8 Raghavan, 1987, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, 7, 365, 10.1007/BF02579324 Hansen, 2010, Variable neighbourhood search: methods and applications, Ann. Oper. Res., 175, 367, 10.1007/s10479-009-0657-6 Lourenço, 2010, Iterated local search: Framework and applications, 363 Resendel, 2005, Grasp with path-relinking: recent advances and applications, 29 Purevsuren, 2017, Hybridization of GRASP with exterior path relinking for identifying critical nodes in graphs, IAENG Int. J. Comput. Sci., 44 Glover, 2014, Exterior path relinking for zero-one optimization, Int. J. Appl. Metaheuristic Comput., 5, 1, 10.4018/ijamc.2014070101 Y. Zhou, J.-K. Hao, F. Glover, Memetic search for identifying critical nodes in sparse graphs, 2017. ArXiv Preprint arXiv:1705.04119. Moscato, 2002, Memetic algorithms, Handb. Appl. Optim., 157, 168 Zhou, 2017, A fast heuristic algorithm for the critical node problem, 121 Zhou, 2011, Multiobjective evolutionary algorithms: A survey of the state of the art, Swarm Evol. Comput., 1, 32, 10.1016/j.swevo.2011.03.001 Veremyev, 2015, Critical nodes for distance-based connectivity and related problems in graphs, Networks, 66, 170, 10.1002/net.21622 Aringhieri, 2016, A preliminary analysis of the distance based critical node problem, Electron. Notes Discrete Math., 55, 25, 10.1016/j.endm.2016.10.007 Aringhieri, 2018, Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem, Discrete Appl. Math., 10.1016/j.dam.2017.12.035 Paudel, 2017, Computing critical nodes in directed graphs, 43 Khot, 2006, Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique, SIAM J. Comput., 36, 1025, 10.1137/S0097539705447037 Barefoot, 1987, Vulnerability in graphs -a comparative survey, J. Combin. Math. Combin. Comput., 1, 13 Bagga, 1992, A survey of integrity, Discrete Appl. Math., 37, 13, 10.1016/0166-218X(92)90122-Q Drange, 2014, On the computational complexity of vertex integrity and component order connectivity, 285 Yannakakis, 1978, Node-and edge-deletion NP-complete problems, 253 Krishnamoorthy, 1979, Node-deletion NP-complete problems, SIAM J. Comput., 8, 619, 10.1137/0208049 Alimonti, 1997, Hardness of approximating problems on cubic graphs, 288 Balas, 1989, On graphs with polynomially solvable maximum-weight clique problem, Networks, 19, 247, 10.1002/net.3230190206 Gavril, 2000, Maximum weight independent sets and cliques in intersection graphs of filaments, Inform. Process. Lett., 73, 181, 10.1016/S0020-0190(00)00025-9 Hayward, 1985, Weakly triangulated graphs, J. Combin. Theory Ser. B, 39, 200, 10.1016/0095-8956(85)90050-4 Lozano, 2017, Optimizing network attacks by artificial bee colony, Inform. Sci., 377, 30, 10.1016/j.ins.2016.10.014 Faramondi, 2016, Critical node detection based on attacker preferences, 773 Faramondi, 2017, Performance analysis of single and multi-objective approaches for the critical node detection problem, 315 Karaboga, 2007, A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm, J. Global Optim., 39, 459, 10.1007/s10898-007-9149-x Faramondi, 2017, Finding critical nodes in infrastructure networks, Int. J. Crit. Infrastruct. Prot. Davis, 2011, The university of florida sparse matrix collection, ACM Trans. Math. Softw., 38, 1 Xiao, 2010, Simple and improved parameterized algorithms for multiterminal cuts, Theory Comput. Syst., 46, 723, 10.1007/s00224-009-9215-5 Schaeffer, 2007, Graph clustering, Comput. Sci. Rev., 1, 27, 10.1016/j.cosrev.2007.05.001 Fan, 2010, Robust optimization of graph partitioning and critical node detection in analyzing networks, 170 Leskovec, 2007, Cost-effective outbreak detection in networks, 420 Kuhlman, 2010, Finding critical nodes for inhibiting diffusion of complex contagions in social networks, 111 Arulselvan, 2009 Callahan, 2012, Shaping operations to attack robust terror networks, 13 Commander, 2007, The wireless network jamming problem, J. Combin. Optim., 14, 481, 10.1007/s10878-007-9071-7 Pawson, 2000, Protein–protein interactions define specificity in signal transduction, Genes Dev., 14, 1027, 10.1101/gad.14.9.1027 Prieto, 2006, APID: agile protein interaction DataAnalyzer, Nucleic Acids Res., 34, W298, 10.1093/nar/gkl128 Westermarck, 2013, Identification of protein interactions involved in cellular signaling, Mol. Cell. Proteomics, 12, 1752, 10.1074/mcp.R113.027771 Yan, 2008, Characterization of protein–protein interfaces, Protein J., 27, 59, 10.1007/s10930-007-9108-x Jhoti, 2007 Liljefors, 2002 Grubesic, 2008, Comparative approaches for assessing network vulnerability, Int. Reg. Sci. Rev., 31, 88, 10.1177/0160017607308679 Clark, 1990, Unit disk graphs, Discrete Math., 86, 165, 10.1016/0012-365X(90)90358-O Kleinberg, 2000, The small-world phenomenon: An algorithmic perspective, 163 Gao, 2012, Networks formed from interdependent networks, Nature Phys., 8, 40, 10.1038/nphys2180 Huang, 2011, Robustness of interdependent networks under targeted attack, Phys. Rev. E, 83, 065101, 10.1103/PhysRevE.83.065101 Parshani, 2010, Interdependent networks: Reducing the coupling strength leads to a change from a first to second order percolation transition, Phys. Rev. Lett., 105, 048701, 10.1103/PhysRevLett.105.048701 Fan, 2011, Economic analysis of the N- k power grid contingency selection and evaluation by graph algorithms and interdiction methods, Energy Syst., 2, 313, 10.1007/s12667-011-0038-5 Ovelgonne, 2012, Covertness centrality in networks, 863 Petersen, 2011, Node removal in criminal networks, 360 Krebs, 2002, Uncloaking terrorist networks, First Monday, 7, 10.5210/fm.v7i4.941 Christakis, 2010, Social network sensors for early detection of contagious outbreaks, PLoS One, 5, e12948, 10.1371/journal.pone.0012948 Krause, 2008, Efficient sensor placement optimization for securing large water distribution networks, J. Water Resour. Plan. Manage., 134, 516, 10.1061/(ASCE)0733-9496(2008)134:6(516) Pinto, 2012, Locating the source of diffusion in large-scale networks, Phys. Rev. Lett., 109, 068702, 10.1103/PhysRevLett.109.068702 Pastor-Satorras, 2002, Immunization of complex networks, Phys. Rev. E, 65, 036104, 10.1103/PhysRevE.65.036104 Kuhlman, 2013, Blocking simple and complex contagion by edge removal, 399 Lokhov, 2014, Inferring the origin of an epidemic with a dynamic message-passing algorithm, Phys. Rev. E, 90, 012801, 10.1103/PhysRevE.90.012801 Shah, 2011, Rumors in a network: Who’s the culprit?, IEEE Trans. Inform. Theory, 57, 5163, 10.1109/TIT.2011.2158885 Cohen, 2003, Efficient immunization strategies for computer networks and populations, Phys. Rev. Lett., 91, 247901, 10.1103/PhysRevLett.91.247901 Tao, 2006, Epidemic dynamics on complex networks, Prog. Natural Sci., 16, 452, 10.1080/10020070612330019 Centola, 2007, Complex contagions and the weakness of long ties1, Amer. J. Sociol., 113, 702, 10.1086/521848 Lalou, 2016, Least squares method for diffusion source localization in complex networks, 473 Bovy, 2002, Modelling for transportation systems planning Vitoriano, 2011, A multi-criteria optimization model for humanitarian aid distribution, J. Global Optim., 51, 189, 10.1007/s10898-010-9603-z