Exact identification of critical nodes in sparse networks via new compact formulations

详细信息    查看全文

• 作者：Alexander Veremyev (1)
  Vladimir Boginski (2)
  Eduardo L. Pasiliao (1)
  
• 关键词：Combinatorial optimization ; Networks ; Graphs ; Critical nodes ; Node interdiction ; Linear 0- formulations
• 刊名：Optimization Letters
• 出版年：2014
• 出版时间：April 2014
• 年：2014
• 卷：8
• 期：4
• 页码：1245-1259
• 全文大小：521 KB
• 参考文献：1. Sun, F., Shayman, M.A.: On pairwise connectivity of wireless multihop networks. Int. J. Secur. Netw. 2(1/2), 37-9 (2007) CrossRef
  2. Jorgi?, M., Stojmenovi?, I., Hauspie, M., Simplot-Ryl, D.: Localized algorithms for detection of critical nodes and links for connectivity in ad hoc networks. In: Proceeding of the third annual IFIP mediterranean ad hoc networking workshop, Med-Hoc-Net (2004)
  3. Borgatti, S.P.: Identifying sets of key players in a social network. Comput. Math. Organ. Theory 12(1), 21-4 (2006) CrossRef
  4. Krebs, V.: Uncloaking terrorist networks, first monday. http://www.firstmonday.org/issues/issue7_4/krebs/ (2002)
  5. Taniguchi, C.M., Emanuelli, B., Kahn, R.C.: Critical nodes in signalling pathways: insights into insulin action. Nat. Rev. Mol. Cell. Biol. 7(2), 85-6 (2006) CrossRef
  6. Boginski, V., Commander, C.W.: Identifying critical nodes in protein–protein interaction networks. In: Butenko, S., Chaovalitwongse, P., Pardalos, P. (eds.) Clustering Challenges in Biological Networks, pp. 153-67. World Scientific, London (2009) CrossRef
  7. Medlock, J., Galvani, A.P.: Optimizing influenza vaccine distribution. Science 325(5948), 1705-708 (2009) CrossRef
  8. Longini, I.M., Halloran, M.E.: Strategy for distribution of influenza vaccine to high-risk groups and children. Am. J. Epidemiol. 161(4), 303-06 (2005) CrossRef
  9. Cohen, R., Havlin, S., ben Avraham, D.: Efficient immunization strategies for computer networks and populations. Phys. Rev. Lett. 91, 247901 (2003) CrossRef
  10. Nian, F., Wang, X.: Efficient immunization strategies on complex networks. J. Theor. Biol. 264(1), 77-3 (2010) CrossRef
  11. Arulselvan, A., Commander, C.W., Elefteriadou, L., Pardalos, P.M.: Detecting critical nodes in sparse graphs. Comput. Oper. Res. 36(7), 2193-200 (2009) CrossRef
  12. Arulselvan, A., Commander, C., Shylo, O., Pardalos, P.: Cardinality-constrained critical node detection problem. In: Gulpinar, N., Harrison, P., Rustem, B. (eds.) Performance Models and Risk Management in Communications Systems, Vol. 46 of Springer Optimization and its Applications, pp. 79-1. Springer, New York (2011)
  13. Dinh, T., Xuan, Y., Thai, M., Park, E., Znati, T.: On approximation of new optimization methods for assessing network vulnerability, In: INFOCOM, 2000 Proceedings of the IEEE, 1- (2010)
  14. 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 Trans. Netw. 20(2), 609-19 (2012) CrossRef
  15. Fan, N., Pardalos, P.M.: Robust optimization of graph partitioning and critical node detection in analyzing networks. In: Proceedings of the 4th international conference on combinatorial optimization and applications, volume part 1, COCOA-0, Springer-Verlag, Berlin, 170-83 (2010)
  16. Shen, Y., Nguyen, N.P., Xuan, Y., Thai, M.T.: On the discovery of critical links and nodes for assessing network vulnerability. IEEE Trans. Netw (2012, to appear)
  17. Ventresca, M.: Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem. Comput. Oper. Res. 39(11), 2763-775 (2012) CrossRef
  18. 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-19 (2012)
  19. Di Summa, M., Grosso, A., Locatelli, M.: Branch and cut algorithms for detecting critical nodes in undirected graphs. Comput. Optim. Appl. 53(3), 649-80 (2012) CrossRef
  20. Fico $^{\rm TM}$ XPress optimization suite 7.4. http://www.fico.com (2012)
  21. Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38(1), 1-5 (2011)
  22. Pajek version 1.26. http://vlado.fmf.uni-lj.si/pub/networks/pajek/ (2010)
  
• 作者单位：Alexander Veremyev (1)
  Vladimir Boginski (2)
  Eduardo L. Pasiliao (1)
  
  1. Munitions Directorate, Air Force Research Laboratory, 101 W. Eglin Blvd, Eglin AFB, FL, ?32542, USA
  2. Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, Gainesville, FL, 32611, USA
  
• ISSN：1862-4480

文摘

Critical node detection problems aim to optimally delete a subset of nodes in order to optimize or restrict a certain metric of network fragmentation. In this paper, we consider two network disruption metrics which have recently received substantial attention in the literature: the size of the remaining connected components and the total number of node pairs connected by a path. Exact solution methods known to date are based on linear 0- formulations with at least $\varTheta (n^3)$ entities and allow one to solve these problems to optimality only in small sparse networks with up to 150 nodes. In this work, we develop more compact linear 0- formulations for the considered types of problems with $\varTheta (n^2)$ entities. We also provide reformulations and valid inequalities that improve the performance of the developed models. Computational experiments show that the proposed formulations allow finding exact solutions to the considered problems for real-world sparse networks up to 10 times larger and with CPU time up to 1,000 times faster compared to previous studies.