Finding Critical Links for Closeness Centrality

References

• Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications (Prentice Hall, Upper Saddle River, NJ).Google Scholar
• Alderson DL, Brown GG, Carlyle WM, Cox LA (2013) Sometimes there is no “most-vital” arc: Assessing and improving the operational resilience of systems. Military Oper. Res. 18(1):21–37.Crossref, Google Scholar
• Alderson DL, Brown GG, Carlyle WM, Wood RK (2018) Assessing and improving the operational resilience of a large highway infrastructure system to worst-case losses. Transportation Sci. 52(4):1012–1034.Link, Google Scholar
• Alon N (1986) Eigenvalues and expanders. Combinatorica 6(2):83–96.Crossref, Google Scholar
• Arulselvan A, Commander CW, Elefteriadou L, Pardalos PM (2009) Detecting critical nodes in sparse graphs. Comput. Oper. Res. 36(7):2193–2200.Crossref, Google Scholar
• Audet C, Hansen P, Jaumard B, Savard G (1997) Links between linear bilevel and mixed 0–1 programming problems. J. Optim. Theory Appl. 93(2):273–300.Crossref, Google Scholar
• Batagelj V, Mrvar A (2006) Pajek datasets. Accessed April 6, 2018, http://vlado.fmf.uni-lj.si/pub/networks/data/.Google Scholar
• Blum M, Karp RM, Vornberger O, Papadimitriu CH, Yannakakis M (1981) The complexity of testing whether a graph is a superconcentrator. Inform. Processing Lett. 13(4–5):164–167.Crossref, Google Scholar
• Boldi P, Vigna S (2014) Axioms for centrality. Internet Math. 10(3–4):222–262.Crossref, Google Scholar
• Borgatti SP (2006) Identifying sets of key players in a social network. Comput. Math. Organ. Theory 12(1):21–34.Crossref, Google Scholar
• Borgatti SP, Everett MG (2006) A graph-theoretic perspective on centrality. Soc. Networks 28(4):466–484.Crossref, Google Scholar
• Borgatti SP, Everett MG, Johnson JC (2013) Analyzing Social Networks (SAGE Publications, Thousand Oaks, CA).Google Scholar
• Brandes U (2001) A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2):163–177.Crossref, Google Scholar
• Brandes U (2008) On variants of shortest-path betweenness centrality and their generic computation. Soc. Networks 30(2):136–145.Crossref, Google Scholar
• Brandes U, Borgatti SP, Freeman LC (2016) Maintaining the duality of closeness and betweenness centrality. Soc. Networks 44:153–159.Crossref, Google Scholar
• Brown GG, Carlyle WM, Salmerón J, Wood K (2014) Analyzing the vulnerability of critical infrastructure to attack and planning defenses. Smith JC, ed. Emerging Theory, Methods, and Applications, INFORMS TutORials in Operations Research (INFORMS, Catonsville, MD), 102–123.Google Scholar
• COLOR02/03/04 (2004) Graph coloring and its generalizations. Accessed September 9, 2013, http://mat.gsia.cmu.edu/COLOR03/.Google Scholar
• Colson B, Marcotte P, Savard G (2007) An overview of bilevel optimization. Ann. Oper. Res. 153(1):235–256.Crossref, Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming Models (Springer, New York).Crossref, Google Scholar
• Crucitti P, Latora V, Marchiori M, Rapisarda A (2004) Error and attack tolerance of complex networks. Physica A: Statist. Mech. Appl. 340(1–3):388–394.Crossref, Google Scholar
• Dangalchev C (2006) Residual closeness in networks. Physica A: Statist. Mech. Appl. 365(2):556–564.Crossref, Google Scholar
• Davis TA, Hu Y (2011) The University of Florida Sparse Matrix Collection. ACM Trans. Math. Software 38(1):1–25.Crossref, Google Scholar
• Dinh TN, Xuan Y, Thai MT, Pardalos PM, Znati T (2012) On new approaches of assessing network vulnerability: Hardness and approximation. IEEE/ACM Trans. Networks 20(2):609–619.Crossref, Google Scholar
• Domingo-Ferrer J, Gonzalez-Nicolas U (2011) Decapitation of networks with and without weights and direction: The economics of iterated attack and defense. Comput. Networks 55(1):119–130.Crossref, Google Scholar
• Everett MG, Borgatti SP (1999) The centrality of groups and classes. J. Math. Soc. 23(3):181–201.Crossref, Google Scholar
• Everett MG, Borgatti SP (2005) Extending centrality. Carrington PJ, Scott J, Wasserman S, eds. Models and Methods in Social Network Analysis (Cambridge University Press, Cambridge, UK), 57–76.Crossref, Google Scholar
• Everton SS (2008) Tracking, destabilizing and disrupting dark networks with social networks analysis. Accessed April 6, 2018, https://calhoun.nps.edu/handle/10945/34415.Google Scholar
• Garey M, Johnson D (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman and Co., New York).Google Scholar
• Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99(12):7821–7826.Crossref, Google Scholar
• Hage P, Harary F (1995) Eccentricity and centrality in networks. Soc. Networks 17(1):57–63.Crossref, Google Scholar
• Hosoya H (1988) On some counting polynomials in chemistry. Discrete Appl. Math. 19(1-3):239–257.Crossref, Google Scholar
• Houck DJ, Kim E, O’Reilly GP, Picklesimer DD, Uzunalioglu H (2004) A network survivability model for critical national infrastructures. Bell Labs Tech. J. 8(4):153–172.Crossref, Google Scholar
• Israeli E, Wood RK (2002) Shortest-path network interdiction. Networks 40(2):97–111.Crossref, Google Scholar
• Jackson MO (2010) Social and Economic Networks (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Krebs V (2002) Uncloaking terrorist networks. First Monday 7. Accessed September 9, 2013, http://journals.uic.edu/ojs/index.php/fm/article/view/941.Google Scholar
• Lalou M, Tahraoui MA, Kheddouci H (2018) The critical node detection problem in networks: A survey. Comput. Sci. Rev. 28:92–117.Crossref, Google Scholar
• Lu LJ, Zhang M (2013) Edge betweenness centrality. Dubitzky W, Wolkenhauer O, Cho K-H, Yokota H, eds. Encyclopedia of Systems Biology (Springer, New York), 647–648.Crossref, Google Scholar
• Malik K, Mittal AK, Gupta SK (1989) The k most vital arcs in the shortest path problem. Oper. Res. Lett. 8(4):223–227.Crossref, Google Scholar
• Matisziw TC, Murray AT (2009) Modeling s-t path availability to support disaster vulnerability assessment of network infrastructure. Comput. Oper. Res. 36(1):16–26.Crossref, Google Scholar
• Newman MEJ (2010) Networks: An Introduction (Oxford University Press, New York).Crossref, Google Scholar
• Nguyen DT, Shen Y, Thai MT (2013) Detecting critical nodes in interdependent power networks for vulnerability assessment. IEEE Trans. Smart Grid 4(1):151–159.Crossref, Google Scholar
• Reka A, Barabási A-L (2002) Statistical mechanics of complex networks. Rev. Modern Phys. 74(1):47–97.Crossref, Google Scholar
• Rochat Y (2009) Closeness centrality extended to unconnected graphs: The harmonic centrality index. 5th Workshop Conf. Appl. Soc. Network Anal., Zurich, Switzerland. Available at https://infoscience.epfl.ch/record/200525?ln=en.Google Scholar
• 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–119.Crossref, Google Scholar
• Shen S, Smith JC, Goli R (2012) Exact interdiction models and algorithms for disconnecting networks via node deletions. Discrete Optim. 9(3):172–188.Crossref, Google Scholar
• Shen Y, Nguyen NP, Xuan Y, Thai MT (2013) On the discovery of critical links and nodes for assessing network vulnerability. IEEE/ACM Trans. Networks 21(3):963–973.Crossref, Google Scholar
• Smith JC, Prince M, Geunes J (2013) Modern network interdiction problems and algorithms. Pardalos PM, Du D-Z, Graham RL, eds. Handbook of Combinatorial Optimization (Springer, New York), 1949–1987.Crossref, Google Scholar
• Veremyev A, Boginski V, Pasiliao EL (2014a) Exact identification of critical nodes in sparse networks via new compact formulations. Optim. Lett. 8(4):1245–1259.Crossref, Google Scholar
• Veremyev A, Prokopyev OA, Pasiliao EL (2014b) An integer programming framework for critical elements detection in graphs. J. Combin. Optim. 28(1):233–273.Crossref, Google Scholar
• Veremyev A, Prokopyev OA, Pasiliao EL (2015) Critical nodes for distance-based connectivity and related problems in graphs. Networks 66(3):170–195.Crossref, Google Scholar
• Vogiatzis C, Veremyev A, Pasiliao EL, Pardalos PM (2014) An integer programming approach for finding the most and the least central cliques. Optim. Lett. 9(4):615–633.Crossref, Google Scholar
• Walteros JL, Pardalos PM (2012) Selected topics in critical element detection. Daras NJ, ed. Applications of Mathematics and Informatics in Military Science (Springer, New York), 9–26.Crossref, Google Scholar
• Watts DJ, Strogatz SH (1998) Collective dynamics of “small-world”networks. Nature 393(6684):440–442.Crossref, Google Scholar
• Xpress (2016) FICOtm Xpress optimization suite 7.5. Accessed May 12, 2016, http://www.fico.com/en/analytics/optimization.Google Scholar
• Zhou B, Cai X, Trinajstić N (2008) On Harary index. J. Math. Chemistry 44(2):611–618.Crossref, Google Scholar