×

Detecting critical node structures on graphs: a mathematical programming approach. (English) Zbl 1407.90093

Summary: We consider the problem of detecting a collection of critical node structures of a graph whose deletion results in the maximum deterioration of the graph’s connectivity. The proposed approach is aimed to generalize other existing models whose scope is restricted to removing individual and unrelated nodes. We consider two common metrics to quantify the connectivity of the residual graph: the total number of connected node pairs and the size of the largest connected component. We first discuss the computational complexity of the problem and then introduce a general mixed-integer linear formulation, which depending on the kind of node structures, may have an exponentially large number of variables and constraints. To solve this potentially large model, we develop a branch-price-and-cut framework, along with some valid inequalities and preprocessing algorithms to strengthen the formulation and reduce the overall execution time. We use the proposed approach to solve the problem for the cases, where the node structures form cliques or stars and provide further directions on how to extend the framework for detecting other kinds of critical structures as well. Finally, we test the quality of our approach by solving a collection of real-life and randomly generated instances with various configurations, analyze the benefits of our model, and propose further enhancements.

MSC:

90B18 Communication networks in operations research
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C05 Linear programming
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B. Addis, M.D. Summa, and A. Grosso, Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth, Discrete Appl. Math.161(16-17) (2013), 2349-2360. · Zbl 1285.05042
[2] Y. Agarwal, K. Mathur, and H.M. Salkin, A set‐partitioning‐based exact algorithm for the vehicle routing problem, Networks19(7) (1989), 731-749. · Zbl 0682.90050
[3] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows Theory, Algorithms, and Applications, Prentice Hall, New Jersey, 1993. · Zbl 1201.90001
[4] R. Albert and A.‐L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys.74(1) (2002), 47-97.
[5] R. Albert, H. Jeong, and A.‐L. Barabasi, Error and attack tolerance of complex networks, Nature406(6794) (2000), 378-382.
[6] A. Arulselvan, C.W. Commander, L. Elefteriadou, and P.M. Pardalos, Detecting critical nodes in sparse graphs, Comput. Oper. Res.36(7) (2009), 2193-2200. · Zbl 1158.90411
[7] C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, and P.H. Vance, Branch‐and‐price: Column generation for solving huge integer programs, Oper. Res.46(3) (1998), 316-329. · Zbl 0979.90092
[8] V. Batagelj and A. Mrvar, Pajek datasets, 2006. http://vlado.fmf.uni-lj.si/pub/networks/data/ (Accessed August, 2017). · Zbl 1054.68564
[9] C. Bazgan, S. Toubaline, and Z. Tuza, The most vital nodes with respect to independent set and vertex cover, Discrete Appl. Math.159(17) (2011), 1933-1946. · Zbl 1236.05141
[10] C. Bazgan, S. Toubaline, and D. Vanderpooten, “Complexity of determining the most vital elements for the 1‐median and 1‐center location problems,” Combinatorial Optimization and Applications, vol. 6508, W. Wu and O. Daescu (eds), Springer, Berlin, Heidelberg, 2010, pp. 237-251. · Zbl 1311.90062
[11] T. Berthold, G. Gamrath, A.M. Gleixner, S. Heinz, T. Koch, and Y. Shinano, Solving mixed integer linear and nonlinear problems using the SCIP optimization suite. ZIB‐Report 12-17, Zuse Institute Berlin, 2012.
[12] R.E. Bixby, J.W. Gregory, I.J. Lustig, R.E. Marsten, and D.F. Shanno, Very large‐scale linear programming: A case study in combining interior point and simplex methods, Oper. Res.40(5) (1992), 885-897. · Zbl 0758.90056
[13] H. Bodlaender, A. Grigoriev, N.V. Grigorieva, and A. Hendriks, “The valve location problem in simple network topologies,” Graph‐Theoretic Concepts in Computer Science, vol. 5344, H. Broersma, T. Erlebach, T. Friedetzky, and D. Paulusma (eds), Springer, Berlin, Heidelberg, 2008, pp. 55-65. · Zbl 1202.90260
[14] S.P. Borgatti, Identifying sets of key players in a social network, Comput. Math. Org. Theory12 (2006), 21-34. · Zbl 1198.91180
[15] J.‐M. Bourjolly, G. Laporte, and G. Pesant, An exact algorithm for the maximum k‐club problem in an undirected graph, Eur. J. Oper. Res.138(1) (2002), 21-28. · Zbl 1008.90048
[16] T. Christof, A. Löbel, and M. Stoer (1997) PORTA: A POlyhedron representation transformation algorithm. http://porta.zib.de/ (Accessed August, 2017).
[17] R.L. Church, M.P. Scaparra, and R.S. Middleton, Identifying critical infrastructure: The median and covering facility interdiction problems, Ann. Assoc. Amer. Geo.94(3) (2004), 491-502.
[18] COLOR 2004. Graph coloring and its generalizations. http://mat.gsia.cmu.edu/COLOR03/ (Accessed August, 2017).
[19] H.W. Corley and D.Y. Sha, Most vital links and nodes in weighted networks, Oper. Res. Lett.1(4) (1982), 157-160. · Zbl 0488.90069
[20] T.A. Davis and Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Softw.38(1) (2011), 1-25. · Zbl 1365.65123
[21] M. Di Summa, A. Grosso, and M. Locatelli, Complexity of the critical node problem over trees, Comput. Oper. Res.38(12) (2011), 1766-1774. · Zbl 1215.90016
[22] M. Di Summa, A. Grosso, and M. Locatelli, Branch and cut algorithms for detecting critical nodes in undirected graphs, Comput. Optim. Appl.53(3) (2012), 649-680. · Zbl 1264.90170
[23] T.N. Dinh, Y. Xuan, M.T. Thai, P.M. Pardalos, and T. Znati, On new approaches of assessing network vulnerability: Hardness and approximation, IEEE/ACM Trans. Network20(2) (2012), 609-619.
[24] O. du Merle, D. Villeneuve, J. Desrosiers, and P. Hansen, Stabilized column generation, Discrete Math.194(1-3) (1999), 229-237. · Zbl 0949.90063
[25] P. Erdös and A. Rényi, On random graphs, I, Pub. Math. (Debrecen)6 (1959), 290-297.
[26] M.G. Everett and S.P. Borgatti, The centrality of groups and classes, J. Math. Soc.23(3) (1999), 181-201. · Zbl 0949.91036
[27] D. Feillet, A tutorial on column generation and branch‐and‐price for vehicle routing problems, 4OR8(4) (2010), 407-424. · Zbl 1208.90016
[28] G.N. Frederickson and R. Solis‐Oba, Increasing the weight of minimum spanning trees, J. Algorithm33(2) (1999), 244-266. · Zbl 0956.68113
[29] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP‐Completeness, W. H. Freeman & Co., New York, 1979. · Zbl 0411.68039
[30] D. Granata, G. Steeger, and S. Rebennack, Network interdiction via a critical disruption path: Branch‐and‐price algorithms, Comput. Oper. Res.40(11) (2013), 2689-2702. · Zbl 1348.90596
[31] M. Grötschel and Y. Wakabayashi, Facets of the clique partitioning polytope, Math. Program.47(1-3) (1990), 367-387. · Zbl 0715.90092
[32] T.H. Grubesic, T.C. Matisziw, A.T. Murray, and D. Snediker, Comparative approaches for assessing network vulnerability, Int. Reg. Sci. Rev.31(1) (2008), 88-112.
[33] T.H. Grubesic and A.T. Murray, Vital nodes, interconnected infrastructures, and the geographies of network survivability, Ann. Assoc. Amer. Geo.96(1) (2006), 64-83.
[34] P. Hansen and B. Jaumard, Cluster analysis and mathematical programming, Math. Program.79(1-3) (1997), 191-215. · Zbl 0887.90182
[35] R. Hewett, Toward identification of key breakers in social cyber‐physical networks, 2011 IEEE International Conference on Systems, Man, and Cybernetics (SMC), 2011, pp. 2731-2736.
[36] J. Hopcroft and R. Tarjan, Algorithm 447: Efficient algorithms for graph manipulation, Commun. ACM16 (1973), 372-378.
[37] D.J. Houck, E. Kim, G.P. O’Reilly, D.D. Picklesimer, and H. Uzunalioglu, A network survivability model for critical national infrastructures, Bell Labs Tech. J.8(4) (2004), 153-172.
[38] E. Israeli and R.K. Wood, Shortest‐path network interdiction, Networks40(2) (2002), 97-111. · Zbl 1027.90106
[39] E. Jenelius, T. Petersen, and L.‐G. Mattsson, Importance and exposure in road network vulnerability analysis, Transport. Res. Part A: Policy Practice40(7) (2006), 537-560.
[40] J. Kaminski, M. Schober, R. Albaladejo, O. Zastupailo, and C. Hidalgo, 2012 Moviegalaxies ‐ social networks in movies. http://moviegalaxies.com/ (Accessed August, 2017).
[41] K.T. Kennedy, R.F. Deckro, J.T. Moore, and K.M. Hopkinson, Nodal interdiction, Math. Comput. Model.54(11-12) (2011), 3116-3125. · Zbl 1235.90031
[42] M. Lalou, M.A. Tahraoui, and H. Kheddouci, The critical node detection problem in networks: A survey, Comput. Sci. Rev.28 (2018), 92-117. · Zbl 1387.68186
[43] J.M. Lewis and M. Yannakakis, The node‐deletion problem for hereditary properties is NP‐complete, J. Comput. Syst. Sci.20(2) (1980), 219-230. · Zbl 0436.68029
[44] C. Lim and J.C. Smith, Algorithms for discrete and continuous multicommodity flow network interdiction problems, IIE Trans.39(1) (2007), 15-26.
[45] M.E. Lübbecke and J. Desrosiers, Selected topics in column generation, Oper. Res.53(6) (2005), 1007-1023. · Zbl 1165.90578
[46] F. Mahdavi Pajouh, V. Boginski, and E.L. Pasiliao, Minimum vertex blocker clique problem, Networks64(1) (2014), 48-64. · Zbl 1390.90183
[47] F. Mahdavi Pajouh, J.L. Walteros, V. Boginski, and E.L. Pasiliao, Minimum edge blocker dominating set problem, Eur. J. Oper. Res.247(1) (2015), 16-26. · Zbl 1346.90788
[48] R.E. Marsten, W.W. Hogan, and J.W. Blankenship, The boxstep method for large‐scale optimization, Oper. Res.23(3) (1975), 389-405. · Zbl 0372.90078
[49] T.C. Matisziw and A.T. Murray, Modeling s‐t path availability to support disaster vulnerability assessment of network infrastructure, Comput. Oper. Res.36 (2009), 16-26. · Zbl 1163.90441
[50] R. Milo, S. Shen‐Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, Network motifs: Simple building blocks of complex networks, Science298(5594) (2002), 824-827.
[51] Y.‐S. Myung and H.‐J. Kim, A cutting plane algorithm for computing k‐edge survivability of a network, Eur. J. Oper. Res.156(3) (2004), 579-589. · Zbl 1056.90015
[52] J. Naoum‐Sawaya and C. Buchheim, Robust critical node selection by Benders decomposition, INFORMS J. Comput.28(1) (2016), 162-174. · Zbl 1337.90073
[53] G.L. Nemhauser and W.B. Widhelm, A modified linear program for columnar methods in mathematical programming, Oper. Res.19(4) (1971), 1051-1060. · Zbl 0223.90018
[54] G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, Wiley‐Interscience, New York, 1988. · Zbl 0652.90067
[55] M. Oosten, J.H.G.C. Rutten, and F.C.R. Spieksma, Disconnecting graphs by removing vertices: A polyhedral approach, Stat. Neerlandica61(1) (2007), 35-60. · Zbl 1122.90088
[56] D. Ortiz‐Arroyo and D.M. Hussain, An information theory approach to identify sets of key players, Proceedings of the 1st European Conference on Intelligence and Security Informatics, 2008, pp. 15-26.
[57] P.R.J. Östergård, A new algorithm for the maximum‐weight clique problem, Nordic. J. Comput.8(4) (2001), 424-436. · Zbl 1003.68117
[58] R.A. Rossi and N.K. Ahmed, The network data repository with interactive graph analytics and visualization, Proceedings of the Twenty‐Ninth AAAI Conference on Artificial Intelligence, 2015, pp. 4292-4293. http://networkrepository.com (Accessed August, 2017).
[59] L.M. Rousseau, M. Gendreau, and D. Feillet, Interior point stabilization for column generation, Oper. Res. Lett.35(5) (2007), 660-668. · Zbl 1149.90099
[60] D.M. Ryan and B.A. Foster, “An integer programming approach to scheduling,” Computer scheduling of public transport: Urban passenger vehicle and crew scheduling, A. Wren (ed.), North‐Holland, Amsterdam, 1981, pp. 269-280.
[61] J. Salmeron, K.R. Wood, and R. Baldick, Analysis of electric grid security under terrorist threat, IEEE Trans. Power. Syst.19(2) (2004), 905-912.
[62] D.F. Shanno and R.L. Weil, Technical note—“linear” programming with absolute‐value functionals, Oper. Res.19(1) (1971), 120-124. · Zbl 0217.27201
[63] S. Shen and J.C. Smith, Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs, Networks60(2) (2012), 103-119. · Zbl 1251.90376
[64] S. Shen, J.C. Smith, and R. Goli, Exact interdiction models and algorithms for disconnecting networks via node deletions, Discrete Optim.9(3) (2012), 172-188. · Zbl 1254.90280
[65] Y. Shen, N.P. Nguyen, Y. Xuan, and M.T. Thai, On the discovery of critical links and nodes for assessing network vulnerability, IEEE/ACM Trans. Netw.21(3) (2013), 963-973.
[66] V. Spirin and L.A. Mirny, Protein complexes and functional modules in molecular networks, Proc. Natl. Acad. Sci.100(21) (2003), 12123-12128.
[67] Z. Tao, F. Zhongqian, and W. Binghong, Epidemic dynamics on complex networks, Prog. Nat. Sci.16(5) (2005), 452-457. · Zbl 1121.92063
[68] R. van der Zwaan, A. Berger, and A. Grigoriev, “How to cut a graph into many pieces,” Theory and Applications of Models of Computation, Volume 6648 of Lecture Notes in Computer Science, M. Ogihara and J. Tarui (eds), Springer, Berlin, Heidelberg, 2011, pp. 184-194. · Zbl 1331.68117
[69] M. Ventresca, Global search algorithms using a combinatorial unranking‐based problem representation for the critical node detection problem, Comput. Oper. Res.39(11) (2012), 2763-2775. · Zbl 1251.90342
[70] M. Ventresca and D. Aleman, A derandomized approximation algorithm for the critical node detection problem, Comput. Oper. Res.43 (2014), 261-270. · Zbl 1348.90609
[71] A. Veremyev and V. Boginski, Identifying large robust network clusters via new compact formulations of maximum k‐club problems, Eur. J. Oper. Res.218(2) (2012), 316-326. · Zbl 1244.90201
[72] A. Veremyev, V. Boginski, and E.L. Pasiliao, Exact identification of critical nodes in sparse networks via new compact formulations, Opt. Lett.8(4) (2014), 1245-1259. · Zbl 1292.90260
[73] A. Veremyev, O.A. Prokopyev, and E.L. Pasiliao, An integer programming framework for critical elements detection in graphs, J. Comb. Optim.28(1) (2014), 233-273. · Zbl 1303.90120
[74] A. Veremyev, O.A. Prokopyev, and E.L. Pasiliao, Critical nodes for distance‐based connectivity and related problems in graphs, Networks66(3) (2015), 170-195.
[75] J.L. Walteros and P.M. Pardalos, “A decomposition approach for solving critical clique detection problems,” Experimental Algorithms, Volume 7276 of Lecture Notes in Computer Science, R. Klasing (ed.), Springer, Berlin, Heidelberg, 2012, pp. 393-404.
[76] J.L. Walteros, C. Vogiatzis, E.L. Pasiliao, and P.M. Pardalos, Integer programming models for the multidimensional assignment problem with star costs, Eur. J. Oper. Res.235(3) (2014), 553-568. · Zbl 1305.90263
[77] D.J. Watts and S.H. Strogatz, Collective dynamics of small‐world networks, Nature393(6684) (1998), 440-442. · Zbl 1368.05139
[78] R. Wollmer, Removing arcs from a network, Oper. Res.12(6) (1964), 934-940. · Zbl 0204.20102
[79] R.K. Wood, Deterministic network interdiction, Math. Comput. Model.17(2) (1993), 1-18. · Zbl 0800.90772
[80] R. Zenklusen, Matching interdiction, Disc. Appl. Math.158(15) (2010), 1676-1690. · Zbl 1208.05120
[81] R. Zenklusen, B. Ries, C. Picouleau, D. de Werra, M.‐C. Costa, and C. Bentz, Blockers and transversals, Discrete Math.309(13) (2009), 4306-4314.
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.