A heuristic approach for the distance-based critical node detection problem in complex networks

References

• Addis, B., Di Summa, M., & Grosso, A. (2013). Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth. Discrete Applied Mathematics, 161(16–17), 2349–2360. https://doi.org/https://doi.org/10.1016/j.dam.2013.03.021
   Web of Science ®Google Scholar
• Aickelin, U., & Clark, A. (2011). Heuristic optimisation. Journal of the Operational Research Society, 62(2), 251–252. https://doi.org/https://doi.org/10.1057/jors.2010.160
   Web of Science ®Google Scholar
• Alozie, G. U., Arulselvan, A., Akartunali K., & Pasiliao, E. (2021). Efficient methods for the distance-based critical node detection problem in complex networks. Computers & Operations Research, 131, 105254. https://doi.org/https://doi.org/10.1016/j.cor.2021.105254
   Google Scholar
• Aringhieri, R., Grosso, A., Hosteins, P., & Scatamacchia, R. (2016a). A general evolutionary framework for different classes of critical node problems. Engineering Applications of Artificial Intelligence, 55, 128–145. https://doi.org/https://doi.org/10.1016/j.engappai.2016.06.010
   Web of Science ®Google Scholar
• Aringhieri, R., Grosso, A., Hosteins, P., & Scatamacchia, R. (2016b). Local search metaheuristics for the critical node problem. Networks, 67(3), 209–221. https://doi.org/https://doi.org/10.1016/j.engappai.2016.06.010
   Web of Science ®Google Scholar
• Aringhieri, R., Grosso, A., Hosteins, P., & Scatamacchia, R. (2016c). A preliminary analysis of the distance based critical node problem. Electronic Notes in Discrete Mathematics, 55, 25–28. https://doi.org/https://doi.org/10.1016/j.endm.2016.10.007
   Google Scholar
• Aringhieri, R., Grosso, A., Hosteins, P., & Scatamacchia, R. (2019). Polynomial and pseudo-polynomial time algorithms for different classes of the distance critical node problem. Discrete Applied Mathematics, 253, 103–121. https://doi.org/https://doi.org/10.1016/j.dam.2017.12.035
   Web of Science ®Google Scholar
• Arulselvan, A., Commander, C. W., Elefteriadou, L., & Pardalos, P. M. (2009). Detecting critical nodes in sparse graphs. Computers & Operations Research, 36(7), 2193–2200. https://doi.org/https://doi.org/10.1016/j.cor.2008.08.016
   Web of Science ®Google Scholar
• Arulselvan, A., Commander, C. W., Pardalos, P. M., & Shylo, O. (2007). Managing network risk via critical node identification. In Risk management in telecommunication networks. Springer.
   Google Scholar
• Arulselvan, A., Commander, C. W., Shylo, O., & Pardalos, P. M. (2011). Cardinality-constrained critical node detection problem. In Performance models and risk management in communications systems (pp. 79–91). Springer.
   Google Scholar
• Batagelj, V., & Mrvar, A. (2006). Pajek datasets. http://vlado.fmf.uni-lj.si/pub/networks/data/
   Google Scholar
• Boginski, V., & Commander, C. W. (2009). Identifying critical nodes in protein-protein interaction networks. In Clustering challenges in biological networks (pp. 153–167). World Scientific.
   Google Scholar
• Borgatti, S. P. (2006). Identifying sets of key players in a social network. Computational & Mathematical Organization Theory, 12(1), 21–34. https://doi.org/https://doi.org/10.1007/s10588-006-7084-x
   Google Scholar
• Di Summa, M., Grosso, A., & Locatelli, M. (2012). Branch and cut algorithms for detecting critical nodes in undirected graphs. Computational Optimization and Applications, 53(3), 649–680. https://doi.org/https://doi.org/10.1007/s10589-012-9458-y
   Web of Science ®Google Scholar
• Gurobi Optimization, I. (2016). Gurobi optimizer reference manual. http://www.gurobi.com
   Google Scholar
• Hagberg, A., Swart, P., & Chult, D. S. (2008). Exploring network structure, dynamics, and function using NetworkX (Tech. Rep.). Los Alamos National Lab (LANL).
   Google Scholar
• Hooshmand, F., Mirarabrazi, F., & MirHassani, S. (2020). Efficient benders decomposition for distance-based critical node detection problem. Omega, 93, 102037. https://doi.org/https://doi.org/10.1016/j.omega.2019.02.006
   Web of Science ®Google Scholar
• Hosteins, P., & Scatamacchia, R. (2020). The stochastic critical node problem over trees. Networks, 76(3), 321–426. https://doi.org/https://doi.org/10.1002/net.21948
   Web of Science ®Google Scholar
• Lalou, M., & Kheddouci, H. (2019). A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs. Optimization Letters, 13(6), 1345–1364. https://doi.org/https://doi.org/10.1007/s11590-018-1371-6
   Web of Science ®Google Scholar
• Lalou, M., Tahraoui, M. A., & Kheddouci, H. (2016). Component-cardinality-constrained critical node problem in graphs. Discrete Applied Mathematics, 210, 150–163. https://doi.org/https://doi.org/10.1016/j.dam.2015.01.043
   Web of Science ®Google Scholar
• Li, J., Pardalos, P. M., Xin, B., & Chen, J. (2019). The bi-objective critical node detection problem with minimum pairwise connectivity and cost: Theory and algorithms. Soft Computing, 23(23), 12729–12744. https://doi.org/https://doi.org/10.1007/s00500-019-03824-8
   Web of Science ®Google Scholar
• Matisziw, T. C., & Murray, A. T. (2009). Modeling s–t path availability to support disaster vulnerability assessment of network infrastructure. Computers & Operations Research, 36(1), 16–26.
   Web of Science ®Google Scholar
• Nandi, A. K., & Medal, H. R. (2016). Methods for removing links in a network to minimize the spread of infections. Computers & Operations Research, 69, 10–24. https://doi.org/https://doi.org/10.1016/j.cor.2015.11.001
   Web of Science ®Google Scholar
• Naoum-Sawaya, J., & Buchheim, C. (2016). Robust critical node selection by benders decomposition. INFORMS Journal on Computing, 28(1), 162–174. https://doi.org/https://doi.org/10.1287/ijoc.2015.0671
   Web of Science ®Google Scholar
• Paton, M., Akartunali, K., & Higham, D. J. (2017). Centrality analysis for modified lattices. SIAM Journal on Matrix Analysis and Applications, 38(3), 1055–1073. https://doi.org/https://doi.org/10.1137/17M1114247
   Web of Science ®Google Scholar
• Purevsuren, D., Cui, G., Win, N. N. H., & Wang, X. (2016). Heuristic algorithm for identifying critical nodes in graphs. Advances in Computer Science: An International Journal, 5(3), 1–4.
   Google Scholar
• Schieber, T. A., Carpi, L., Frery, A. C., Rosso, O. A., Pardalos, P. M., & Ravetti, M. G. (2016). Information theory perspective on network robustness. Physics Letters A, 380(3), 359–364. https://doi.org/https://doi.org/10.1016/j.physleta.2015.10.055
   Web of Science ®Google Scholar
• Shen, S., & Smith, J. C. (2012). Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs. Networks, 60(2), 103–119. https://doi.org/https://doi.org/10.1002/net.20464
   Web of Science ®Google Scholar
• Shen, S., Smith, J. C., & Goli, R. (2012). Exact interdiction models and algorithms for disconnecting networks via node deletions. Discrete Optimization, 9(3), 172–188. https://doi.org/https://doi.org/10.1016/j.disopt.2012.07.001
   Web of Science ®Google Scholar
• Silver, E. A. (2004). An overview of heuristic solution methods. Journal of the Operational Research Society, 55(9), 936–956. https://doi.org/https://doi.org/10.1057/palgrave.jors.2601758
   Web of Science ®Google Scholar
• UCINET Software Datasets. (n.d.). https://sites.google.com/site/ucinetsoftware/datasets/
   Google Scholar
• Ventresca, M. (2012). Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem. Computers & Operations Research, 39(11), 2763–2775. https://doi.org/https://doi.org/10.1016/j.cor.2012.02.008
   Web of Science ®Google Scholar
• Ventresca, M., & Aleman, D. (2015). Efficiently identifying critical nodes in large complex networks. Computational Social Networks, 2(1), 6. https://doi.org/https://doi.org/10.1186/s40649-015-0010-y
   Google Scholar
• Ventresca, M., Harrison, K. R., & Ombuki-Berman, B. M. (2018). The bi-objective critical node detection problem. European Journal of Operational Research, 265(3), 895–908. https://doi.org/https://doi.org/10.1016/j.ejor.2017.08.053
   Web of Science ®Google Scholar
• Veremyev, A., Boginski, V., & Pasiliao, E. L. (2014). Exact identification of critical nodes in sparse networks via new compact formulations. Optimization Letters, 8(4), 1245–1259. https://doi.org/https://doi.org/10.1007/s11590-013-0666-x
   Web of Science ®Google Scholar
• Veremyev, A., Prokopyev, O. A., & Pasiliao, E. L. (2014). An integer programming framework for critical elements detection in graphs. Journal of Combinatorial Optimization, 28(1), 233–273. https://doi.org/https://doi.org/10.1007/s10878-014-9730-4
   Web of Science ®Google Scholar
• Veremyev, A., Prokopyev, O. A., & Pasiliao, E. L. (2015). Critical nodes for distance-based connectivity and related problems in graphs. Networks, 66(3), 170–195. https://doi.org/https://doi.org/10.1002/net.21622
   Web of Science ®Google Scholar
• Walteros, J. L., Veremyev, A., Pardalos, P. M., & Pasiliao, E. L. (2019). Detecting critical node structures on graphs: A mathematical programming approach. Networks, 73(1), 48–88. https://doi.org/https://doi.org/10.1002/net.21834
   Web of Science ®Google Scholar
• Wang, S., Gong, M., Liu, W., & Wu, Y. (2020). Preventing epidemic spreading in networks by community detection and memetic algorithm. Applied Soft Computing, 89, 106–118. https://doi.org/https://doi.org/10.1016/j.asoc.2020.106118
   Web of Science ®Google Scholar
• Yadegari, E., Alem-Tabriz, A., & Zandieh, M. (2019). A memetic algorithm with a novel neighborhood search and modified solution representation for closed-loop supply chain network design. Computers & Industrial Engineering, 128, 418–436. https://doi.org/https://doi.org/10.1016/j.cie.2018.12.054
   Web of Science ®Google Scholar
• Zhang, L., Xia, J., Cheng, F., Qiu, J., & Zhang, X. (2020). Multiobjective optimization of critical node detection based on cascade model in complex networks. IEEE Transactions on Network Science and Engineering, 7(3), 2052–2066. https://doi.org/https://doi.org/10.1109/tnse.2020.2972980
   Google Scholar
• Zhou, Y., Hao, J.-K., & Glover, F. (2018). Memetic search for identifying critical nodes in sparse graphs. IEEE Transactions on Cybernetics, 49(10), 3699–3712. https://doi.org/https://doi.org/10.1109/TCYB.2018.2848116
   PubMed Web of Science ®Google Scholar