nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.07.2014

An integer programming framework for critical elements detection in graphs

verfasst von: Alexander Veremyev, Oleg A. Prokopyev, Eduardo L. Pasiliao

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This study presents an integer programming framework for minimizing the connectivity and cohesiveness properties of a given graph by removing nodes and edges subject to a joint budgetary constraint. The connectivity and cohesiveness metrics are assumed to be general functions of sizes of the remaining connected components and node degrees, respectively. We demonstrate that our approach encompasses, as special cases (possibly, under some mild conditions), several other models existing in the literature, including minimization of the total number of connected node pairs, minimization of the largest connected component size, and maximization of the number of connected components. We discuss computational complexity issues, derive linear mixed integer programming (MIP) formulations, and describe additional modeling enhancements aimed at improving the performance of MIP solvers. We also conduct extensive computational experiments with real-life and randomly generated network instances under various settings that reveal interesting insights and demonstrate advantages and limitations of the proposed framework.

Vorheriger Artikel Value-at-risk support vector machine: stability to outliers

Nächster Artikel Minimum number of disjoint linear forests covering a planar graph

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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–2360CrossRefMATHMathSciNet

Arulselvan A, Commander CW, Elefteriadou L, Pardalos PM (2009) Detecting critical nodes in sparse graphs. Computers & Operations Research 36(7):2193–2200CrossRefMATHMathSciNet

Arulselvan A, Commander CW, Pardalos PM, Shylo O (2007) Managing network risk via critical node identification, Risk Management in Telecommunication Networks. Springer, Heidelberg

Arulselvan A, Commander CW, Shylo O, Pardalos PM (2011) Cardinality-constrained critical node detection problem. In: Gulpinar N, Harrison P, Rustem B (eds) Performance Models and Risk Management in Communications Systems, Springer Optimization and Its Applications, vol 46. Springer, New York, pp 79–91

Bodlaender HL, Hendriks A, Grigoriev A, Grigorieva NV (2010) The valve location problem in simple network topologies. INFORMS Journal on Computing 22(3):433–442CrossRefMATHMathSciNet

Borgatti SP (2006) Identifying sets of key players in a social network. Computational & Mathematical Organization Theory 12(1):21–34CrossRefMATH

Chung F, Lu L (2002) Connected components in random graphs with given expected degree sequences. Annals of Combinatorics 6(2):125–145CrossRefMATHMathSciNet

Chung F, Lu L (2006) The volume of the giant component of a random graph with given expected degrees. SIAM Journal on Discrete Mathematics 20(2):395–411CrossRefMATHMathSciNet

COLOR02/03/04: Graph Coloring and its Generalizations. http://mat.gsia.cmu.edu/COLOR03/. Last accessed September 9, 2013

Davis TA, Hu Y (2011) The university of florida sparse matrix collection. ACM Transactions on Mathematical Software 38(1):1–25MathSciNet

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–680CrossRefMATHMathSciNet

DIMACS. 10th DIMACS Implementation Challenge. Available at http://www.cc.gatech.edu/dimacs10/index.shtml, last accessed September 9, 2013, 2011

Dinh TN, Xuan Y, Thai MT, Pardalos PM, Znati T (2012) On new approaches of assessing network vulnerability: hardness and approximation. IEEE/ACM Transactions on Networking 20(2):609–619CrossRef

Dinh T.N., Xuan Y., Thai M.T., Park E.K., Znati T. On approximation of new optimization methods for assessing network vulnerability. In INFOCOM, 2010 Proceedings IEEE, pages 1–9, March 2010.

Erdős P, Rényi A (1959) On random graphs. Publicationes Mathematicae Debrecen 6:290–297MathSciNet

Faloutsos M., Faloutsos P., Faloutsos C. (1999 ) On power-law relationships of the internet topology. In Proceedings of the ACM-SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer, Communication, pp. 251–262

FICO™ Xpress Optimization Suite 7.5. http://www.fico.com Last accessed September 9, 2013

Garey M, Johnson D (1979) Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman and Co., New YorkMATH

Hewett R. (2011) Toward identification of key breakers in social cyber-physical networks. In Systems, Man, and Cybernetics (SMC), 2011 IEEE International Conference on, pages 2731–2736,

Houck DJ, Kim E, O’Reilly GP, Picklesimer DD, Uzunalioglu H (2004) A network survivability model for critical national infrastructures. Bell Labs Technical Journal 8(4):153–172CrossRef

Köppe Matthias, Louveaux Quentin, Weismantel Robert (2008) Intermediate integer programming representations using value disjunctions. Discrete Optimization 5(2):293–313CrossRefMATHMathSciNet

Krebs V. . Uncloaking terrorist networks. First Monday, 7(4), 2002. Available at http://journals.uic.edu/ojs/index.php/fm/article/view/941, last accessed September 9, 2013

Lusseau D, Schneider K, Boisseau OJ, Haase P, Slooten E, Dawson SM (2003) The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology 54(4):396–405CrossRef

Matisziw TC, Murray AT (2009) Modeling \(s-t\) path availability to support disaster vulnerability assessment of network infrastructure. Computers & Operations Research 36(1):16–26CrossRefMATH

Myung Y-S, Kim H-J (2004) A cutting plane algorithm for computing k-edge survivability of a network. European Journal of Operational Research 156(3):579–589CrossRefMATHMathSciNet

Newman MEJ (2003) The structure and function of complex networks. SIAM Review 45:167–256CrossRefMATHMathSciNet

Oosten M, Rutten JHGC, Spieksma FCR (2007) Disconnecting graphs by removing vertices: a polyhedral approach. Statistica Neerlandica 61(1):35–60CrossRefMATHMathSciNet

Ortiz-Arroyo D., Hussain D.M. (2008) An information theory approach to identify sets of key players. In Proceedings of the 1st European Conference on Intelligence and Security Informatics, EuroISI ’08, pages 15–26, Berlin, Heidelberg, Springer-Verlag.

Power Systems Test Case Archive, 118 Bus Power Flow Test Case. Available at http://www.ee.washington.edu/research/pstca/pf118/pg_tca118bus.htm, last accessed September 9, 2013

Reka A, Barabási A-L (2002) Statistical mechanics of complex networks. Reviews of Modern Physics 74:47–97CrossRefMathSciNet

Resende MGC, Pardalos PM (eds) (2006) Handbook of optimization in telecommunications. Springer,

Shen S, Smith JC (2012) Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs. Networks 60(2):103–119MATHMathSciNet

Shen S, Smith JC, Goli R (2012a) Exact interdiction models and algorithms for disconnecting networks via node deletions. Discrete Optimization 9(3):172–188

Shen Y., Nguyen N.P., Xuan Y., Thai M.T. (2012b) On the Discovery of Critical Links and Nodes for Assessing Network Vulnerability. IEEE Transactions on Networking, to appear,

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–2775CrossRefMATHMathSciNet

Ventresca M, Aleman D (2014) A derandomized approximation algorithm for the critical node detection problem. Computers & Operations Research 43:261–270CrossRefMathSciNet

Veremyev A., Boginski V., Pasiliao E.L. (2013) Exact identification of critical nodes in sparse networks via new compact formulations. Optimization Letters, pages 1–15

Walteros JL, Pardalos PM (2012) Selected topics in critical element detection. In: Daras Nicholas J (ed) Applications of Mathematics and Informatics in Military Science, Springer Optimization and Its Applications, vol 71. Springer, New York, pp 9–26CrossRef

Yannakakis M. Node-and edge-deletion np-complete problems. In Proceedings of the tenth annual ACM symposium on Theory of computing, STOC ’78, pages 253–264, New York, NY, USA, 1978. ACM.

Zachary WW (1977) An information flow model for conflict and fission in small groups. Journal of Anthropological Research 33:452–473

Zwaan R, Berger A, Grigoriev A (2011) How to cut a graph into many pieces. In: Ogihara Mitsunori, Tarui Jun (eds) Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol 6648. Springer, Berlin Heidelberg, pp 184–194CrossRef

Titel: An integer programming framework for critical elements detection in graphs
verfasst von: Alexander Veremyev
Oleg A. Prokopyev
Eduardo L. Pasiliao
Publikationsdatum: 01.07.2014
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2014
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-014-9730-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2014

Recognition of overlap graphs

A greedy algorithm for the fault-tolerant connected dominating set in a general graph

Bound and exact methods for assessing link vulnerability in complex networks

Multi-depot vessel routing problem in a direction dependent wavefield

Characteristics of the maximal independent set ZDD

An exact algorithm for the maximum probabilistic clique problem

Premium Partner