×

The bi-objective critical node detection problem. (English) Zbl 1374.90085

Summary: Identifying critical nodes in complex networks has become an important task across a variety of application domains. The Critical Node Detection Problem (CNDP) is an optimization problem that aims to minimize pairwise connectivity in a graph by removing a subset of \(K\) nodes. Despite the CNDP being recognized as a bi-objective problem, until now only single-objective problem formulations have been proposed. In this paper, we propose a bi-objective version of the problem that aims to maximize the number of connected components in a graph while simultaneously minimizing the variance of their cardinalities by removing a subset of \(K\) nodes. We prove that our bi-objective formulation is distinct from the CNDP, despite their common motivation. Finally, we give a brief comparison of six common multi-objective evolutionary algorithms using sixteen common benchmark problem instances, including for the node-weighted CNDP. We find that of the examined algorithms, NSGAII generally produces the most desirable approximation fronts.

MSC:

90B10 Deterministic network models in operations research
90C29 Multi-objective and goal programming
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming

Software:

PAES
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Addis, B.; Aringhieri, R.; Grosso, A.; Hosteins, P., Hybrid constructive heuristics for the critical node problem, Annals of Operations Research, 238, 1, 637-649 (2016) · Zbl 1334.90185
[2] Addis, B.; Di Summa, M.; Grosso, A., 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 (2013) · Zbl 1285.05042
[3] Aringhieri, R.; Grosso, A.; Hosteins, P.; Scatamacchia, R., VNS solutions for the critical node problem, Electronic Notes in Discrete Mathematics, 47, 37-44 (2015) · Zbl 1362.68255
[4] Aringhieri, R.; Grosso, A.; Hosteins, P.; Scatamacchia, R., Local search metaheuristics for the critical node problem, Networks, 67, 3, 209-221 (2016)
[5] Arora, S.; Rao, S.; Vazirani, U., Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on theory of computing, 222-231 (2004) · Zbl 1192.68467
[6] Arulselvan, A.; Commander, C. W.; Elefteriadou, L.; Pardalos, P. M., Detecting critical nodes in sparse graphs, Computers and Operations Research, 36, 7, 2193-2200 (2009) · Zbl 1158.90411
[7] Aspnes, J.; Chang, K.; Yampolskiy, A., Inoculation strategies for victims of viruses and the sum-of-squares partition problem, Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms. Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA ’05, 43-52 (2005), Society for Industrial and Applied Mathematics · Zbl 1297.68258
[8] Berger, A.; Grigoriev, A.; van der Zwaan, R., Complexity and approximability of the k-way vertex cut, Networks, 63, 2, 170-171 (2013) · Zbl 1386.05148
[9] Boginski, V.; Commander, C., Identifying critical nodes in protein-protein interaction networks, Clustering challenges in biological networks, 153-166 (2009), Springer
[10] Chen, P.; David, M.; Kempe, D., Better vaccination strategies for better people, Proceedings of the eleventh ACM conference on electronic commerce, 179-188 (2010), ACM
[11] Collado, R. A.; Papp, D., Network interdiction - models, applications, unexplored directions, Technical Report (2010), Rutgers University
[12] Corne, D.; Jerram, N.; Knowles, J.; Oates, M., PESA-II: region-based selection in evolutionary multiobjective optimization, Proceedings of the genetic and evolutionary computation conference, 283-290 (2001)
[13] Deb, K.; Mohan, M.; Mishra, S., A fast multi-objective evolutionary algorithm for finding well-spread pareto-optimal solutions, Technical Report (2003), IIT-Kanpur
[14] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 6, 2, 182-197 (2002)
[15] Di Summa, M.; Grosso, A.; Locatelli, M., Complexity of the critical node problem over trees, Computers and Operations Research, 38, 12, 1766-1774 (2011) · Zbl 1215.90016
[16] Di Summa, M.; Grosso, A.; Locatelli, M., Branch and cut algorithms for detecting critical nodes in undirected graphs, Computational Optimization and Applications, 53, 3, 649-680 (2012) · Zbl 1264.90170
[17] Dinh, T. N.; Xuan, Y.; Thai, M. T.; Pardalos, P. M.; Znati, T., On new approaches of assessing network vulnerability: Hardness and approximation, IEEE/ACM Transactions on Networking, 20, 2, 609-619 (2012)
[18] Dinh, T. N.; Xuan, Y.; Thai, M. T.; Park, E. K.; Znati, T., On approximation of new optimization methods for assessing network vulnerability, Proceedings of the INFOCOM, 2678-2686 (2010)
[19] Engelberg, R.; Konemann, J.; Leonardi, S.; Naor, J., Cut problems in graphs with a budget constraint, Proceedings of the seventh Latin American theoretical informatics symposium, 262-279 (2006) · Zbl 1135.90419
[20] Fonseca, C. M.; Paquete, L.; López-Ibáñez, M., An improved dimension-sweep algorithm for the hypervolume indicator, Proceedings of the congress on evolutionary computation, 1157-1163 (2006), IEEE
[21] Garg, N.; Vazirani, V.; Yannakakis, M., Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica, 18, 3-20 (1997) · Zbl 0873.68075
[22] Ishibuchi, H.; Akedo, N.; Ohyanagi, H.; Nojima, Y., Behavior of EMO algorithms on many-objective optimization problems with correlated objectives, Proceedings of the IEEE congress on evolutionary computation (CEC), 1465-1472 (2011)
[23] Joyce, K. E.; Laurienti, P. J.; Burdette, J. H.; Hayasaka, S., A new measure of centrality for brain networks, PLoS ONE, 5, 8, e12200 (2010)
[24] Kempe, D.; Kleinberg, J.; Tardos, E., Maximizing the spread of influence in a social network, Proceedings of the ninth international conference on knowledge discovery and data mining, 137-146 (2003)
[25] Knowles, J.; Corne, D., The Pareto archived evolution strategy: a new baseline algorithm for Pareto multiobjective optimisation, Proceedings of the congress on evolutionary computation, 1, 98-105 (1999)
[26] Kollat, J.; Reed, P., Comparing state-of-the-art evolutionary multi-objective algorithms for long-term groundwater monitoring design, Advances in Water Resources, 29, 6, 792-807 (2006)
[27] Kumar, V. S.A.; Rajaraman, R.; Sun, Z.; Sundaram, R., Existence theorems and approximation algorithms for generalized network security games, Proceedings of the IEEE thirtieth international conference on distributed computing systems, 348-357 (2010)
[28] von Luxburg, U., A tutorial on spectral clustering, Statistics and Computing, 17, 4, 395-416 (2007)
[29] MOEA Framework, version 2.1, (2014). http://www.moeaframework.org; MOEA Framework, version 2.1, (2014). http://www.moeaframework.org
[30] Moritz, R. L.; Reich, E.; Bernt, M.; Middendorf, M., The influence of correlated objectives on different types of P-ACO algorithms, Evolutionary computation in combinatorial optimisation. Evolutionary computation in combinatorial optimisation, Lecture Notes in Computer Science, 8600, 230-241 (2014), Springer
[31] Nebro, A.; Alba, E.; Molina, G.; Chicano, F.; Luna, F.; Durillo, J., Optimal antenna placement using a new multi-objective CHC algorithm, Proceedings of the ninth annual conference on genetic and evolutionary computation, 876-883 (2007)
[32] Networks, Virtual issue - network interdiction applications and extensions (2014), Wiley
[33] Nguyen, D.; Shen, Y.; Thai, M., Detecting critical nodes in interdependent power networks for vulnerability assessment, IEEE Transactions on Smart Grid, 4, 1, 151-159 (2013)
[34] Pullan, W., Heuristic identification of critical nodes in sparse real-world graphs, Journal of Heuristics, 21, 5, 577-598 (2015)
[35] Rocco, C. M.; Salazar, D. E.; Ramirez-Marquez, J. E., Multi-objective network interdiction using evolutionary algorithms, Proceedings of the Reliability and maintainability symposium, 170-175 (2009)
[36] Salmeron, J., Deception tactics for network interdiction: A multiobjective approach, Networks, 60, 1, 45-58 (2012) · Zbl 1251.90071
[37] Saran, H.; Vazirani, V., Finding k-cuts within twice the optimal, SIAM Journal of Computing, 24, 101-108 (1995) · Zbl 0828.68082
[38] Schott, J. (1995). Fault tolerant design using single and multicriteria genetic algorithm optimization (Master’s thesis). Massachusetts Institute of Technology.; Schott, J. (1995). Fault tolerant design using single and multicriteria genetic algorithm optimization (Master’s thesis). Massachusetts Institute of Technology.
[39] Shen, S.; Smith, J. C.; Goli, R., Exact interdiction models and algorithms for disconnecting networks via node deletions, Discrete Optimization, 9, 3, 172-188 (2012) · Zbl 1254.90280
[40] S. P., B., Identifying sets of key players in a network, Computational and Mathematical Organization Theory, 12, 21-34 (2006) · Zbl 1198.91180
[41] Ventresca, M., Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem, Computers and Operations Research, 39, 11, 2763-2775 (2012) · Zbl 1251.90342
[42] Ventresca, M.; Aleman, D., Evaluation of strategies to mitigate contagion spread using social network characteristics, Social Networks, 35, 1, 75-88 (2013)
[43] Ventresca, M.; Aleman, D., A derandomized approximation algorithm for the critical node detection problem, Computers and Operations Research, 43, 261-270 (2014) · Zbl 1348.90609
[44] Ventresca, M.; Aleman, D., A fast greedy algorithm for the critical node detection problem, Combinatorial optimization and applications. Combinatorial optimization and applications, Lecture Notes in Computer Science, 8881, 603-612 (2014), Springer · Zbl 1433.05302
[45] Ventresca, M.; Aleman, D., A randomized algorithm with local search for containment of pandemic disease spread, Computers and Operations Research, 48, 11-19 (2014) · Zbl 1348.92011
[46] Ventresca, M.; Harrison, K. R.; Ombuki-Berman, B. M., An experimental evaluation of multi-objective evolutionary algorithms for detecting critical nodes in complex networks, Proceedings of the eighteenth European conference on applications of evolutionary computation, 164-176 (2015), Springer International Publishing: Springer International Publishing Copenhagen, Denmark
[47] Veremyev, A.; Boginski, V.; Pasiliao, E. L., Exact identification of critical nodes in sparse networks via new compact formulations, Optimization Letters, 8, 4, 1245-1259 (2014) · Zbl 1292.90260
[48] Veremyev, A.; Prokopyev, O. A.; Pasiliao, E. L., An integer programming framework for critical elements detection in graphs, Journal of Combinatorial Optimization, 28, 1, 233-273 (2014) · Zbl 1303.90120
[49] Walteros, J. L.; Pardalos, P. M., Selected topics in critical element detection, Applications of mathematics and informatics in military science. Applications of mathematics and informatics in military science, Springer Optimization and Its Applications, 71, 9-26 (2012), Springer New York · Zbl 1315.90060
[50] Weighted CNDP and BOCNDP benchmark network instances. http://engineering.purdue.edu/ mventresca/index.php?cnd; Weighted CNDP and BOCNDP benchmark network instances. http://engineering.purdue.edu/ mventresca/index.php?cnd
[51] Zitzler, E.; Thiele, L., Multiobjective optimization using evolutionary algorithms - a comparative case study, Parallel problem solving from nature. Parallel problem solving from nature, Lecture Notes in Computer Science, 1498, 292-301 (1998), Springer Berlin Heidelberg
[52] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C.; Da Fonseca, V., Performance assessment of multiobjective optimizers: An analysis and review, IEEE Transactions on Evolutionary Computation, 7, 2, 117-132 (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.