Robustness of solutions to critical node detection problems with imperfect data: a computational study

References

• R. Albert, H. Jeong, and A. Barabási, Error and attack tolerance of complex networks, Nature 406(6794) (2000), pp. 378–382. doi: 10.1038/35019019
   PubMed Web of Science ®Google Scholar
• A. Arulselvan, C.W. Commander, L. Elefteriadou, and P.M. Pardalos, Detecting critical nodes in sparse graphs, Comput. Oper. Res. 36(7) (2009), pp. 2193–2200. doi: 10.1016/j.cor.2008.08.016
   Web of Science ®Google Scholar
• A. Arulselvan, C.W. Commander, P.M. Pardalos, and O. Shylo, Cardinality-Constrained critical node detection problem, in Performance models and risk management in communications systems, N. Gülpınar, P. Harrison, and B. Rustem, eds., Springer, New York, 2010, pp. 79–92.
   Google Scholar
• B. Balasundaram, S. Butenko, and S. Trukhanov, Novel approaches for analyzing biological networks, J. Comb. Optim. 10 (2005), pp. 23–39. doi: 10.1007/s10878-005-1857-x
   Web of Science ®Google Scholar
• A. Barabási and R. Albert, Emergence of scaling in random networks, Science 286(5439) (1999), pp. 509–512. doi: 10.1126/science.286.5439.509
   PubMed Web of Science ®Google Scholar
• V. Batagelj and A. Mrvar, Pajek, 2006. Available at http://mrvar.f.uni-lj.si/pub/networks/data/ (accessed 8 May 2015).
   Google Scholar
• S.P. Borgatti, Identifying sets of key players in a social network, Comput. Math. Organ. Theory 12(1) (2006), pp. 21–34. doi: 10.1007/s10588-006-7084-x
   Google Scholar
• S.P. Borgatti, K.M. Carley, and D. Krackhardt, On the robustness of centrality measures under conditions of imperfect data, Soc. Netw. 28(2) (2006), pp. 124–136. doi: 10.1016/j.socnet.2005.05.001
   Web of Science ®Google Scholar
• S.P. Borgatti and M.G. Everett, A graph-theoretic perspective on centrality, Soc. Netw. 28(4) (2006), pp. 466–484. doi: 10.1016/j.socnet.2005.11.005
   Web of Science ®Google Scholar
• U. Brandes and T. Erlebach, Network Analysis: Methodological Foundations, LNCS 3418, Springer-Verlag, Berlin Heidelberg, 2005.
   Google Scholar
• G. Brown, M. Carlyle, J. Salmerón, and K. Wood, Defending critical infrastructure, Interfaces 36(6) (2006), pp. 530–544. doi: 10.1287/inte.1060.0252
   Web of Science ®Google Scholar
• COLOR02/03/04, Graph coloring and its generalizations. Available at http://mat.gsia.cmu.edu/COLOR03 (accessed 8 May 2015).
   Google Scholar
• E. Costenbader and T.W. Valente, The stability of centrality measures when networks are sampled, Soc. Netw. 25(4) (2003), pp. 283–307. doi: 10.1016/S0378-8733(03)00012-1
   Web of Science ®Google Scholar
• C. Dangalchev, Residual closeness in networks, Phys. A 365(2) (2006), pp. 556–564. doi: 10.1016/j.physa.2005.12.020
   Web of Science ®Google Scholar
• T. Davis and Y. Hu, The university of Florida sparse matrix collection, ACM Trans. Math. Softw. 38(1) (2011), pp. 1–25.
   Web of Science ®Google Scholar
• 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. Netw. 20(2) (2012), pp. 609–619. doi: 10.1109/TNET.2011.2170849
   Web of Science ®Google Scholar
• T.N. Dinh, H. Zhang, D.T. Nguyen, and M.T. Thai, Cost-effective viral marketing for time-critical campaigns in large-scale social networks, IEEE/ACM Trans. Netw. 22(6) (2014), pp. 2001–2011. doi: 10.1109/TNET.2013.2290714
   Web of Science ®Google Scholar
• 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), pp. 649–680. doi: 10.1007/s10589-012-9458-y
   Web of Science ®Google Scholar
• P. Erdös and A. Rényi, On random graphs, Publ. Math. Debrecen 6 (1959), pp. 290–297.
   Google Scholar
• T.L. Frantz, M. Cataldo, and K.M. Carley, Robustness of centrality measures under uncertainty: Examining the role of network topology, Comput. Math. Organ. Theory 15(4) (2009), pp. 303–328. doi: 10.1007/s10588-009-9063-5
   Web of Science ®Google Scholar
• M. Girvan and M.E.J. Newman, Community structure in social and biological networks, Proc. Natl. Acad. Sci. 99(12) (2002), pp. 7821–7826. doi: 10.1073/pnas.122653799
   PubMed Web of Science ®Google Scholar
• M.S. Granovetter, The strength of weak ties, AJS 78 (1973), pp. 1360–1380.
   Web of Science ®Google Scholar
• B. Husslage, P. Borm, T. Burg, H. Hamers, and R. Lindelauf, Ranking terrorists in networks: A sensitivity analysis of Al Qaeda's 9/11 attack, Soc. Netw. 42 (2015), pp. 1–7. doi: 10.1016/j.socnet.2015.02.003
   Web of Science ®Google Scholar
• IBM, ILOG CPLEX Optimizer v. 12.4, Jan 2012. Available at http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/.
   Google Scholar
• E. Israeli and R.J. Wood, Shortest-path network interdiction, Networks 40(2) (2002), pp. 97–111. doi: 10.1002/net.10039
   Web of Science ®Google Scholar
• S. Iyer, T. Killingback, B. Sundaram, and Z. Wang, Attack robustness and centrality of complex networks, PLoS One 8(4) (2013), pp. e59613. doi: 10.1371/journal.pone.0059613
   PubMed Web of Science ®Google Scholar
• D. Kempe, J. Kleinberg, and É. Tardos, Maximizing the spread of influence through a social network. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM 2003, pp. 137–146.
   Google Scholar
• J.P. Kesan, C.M. Hayes, and M.N. Bashir, A comprehensive empirical study of data privacy, trust, and consumer autonomy, Indiana Law J. 91 (2015), pp. 267–352.
   Web of Science ®Google Scholar
• V. E. Krebs, Uncloaking terrorist networks, First Monday 7(4) (2002). doi: 10.5210/fm.v7i4.941
   Google Scholar
• V.E. Krebs, Mapping networks of terrorist cells, Connections 24(3) (2002), pp. 43–52.
   Google Scholar
• J. Leskovec and R. Sosič, SNAP: A general purpose network analysis and graph mining library in C++, June 2014. Available at http://snap.stanford.edu/snap.
   Google Scholar
• P.V. Marsden, Network data and measurement, Ann. Rev. Sociol. 16 (1990), pp. 435–463. doi: 10.1146/annurev.so.16.080190.002251
   Web of Science ®Google Scholar
• P.V. Marsden, The reliability of network density and composition measures, Soc. Netw. 15(4) (1993), pp. 399–421. doi: 10.1016/0378-8733(93)90014-C
   Web of Science ®Google Scholar
• D.T. Nguyen, Y. Shen, and M.T. Thai, Detecting critical nodes in interdependent power networks for vulnerability assessment, IEEE Trans. Smart Grid 4(1) (2013), pp. 151–159. doi: 10.1109/TSG.2012.2229398
   Web of Science ®Google Scholar
• W. Pullan, Heuristic identification of critical nodes in sparse real-world graphs, J. Heuristics 21(4) (2015), pp. 1–22.
   Google Scholar
• S. Shen and J.C. Smith, Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs, Networks 60(2) (2012), pp. 103–119.
   Web of Science ®Google Scholar
• S. Shen, J.C. Smith, and R. Goli, Exact interdiction models and algorithms for disconnecting networks via node deletions, Discrete Optim. 9(3) (2012), pp. 172–188. doi: 10.1016/j.disopt.2012.07.001
   Web of Science ®Google Scholar
• M.T. Thai and P.M. Pardalos, Handbook of Optimization in Complex Networks: Theory and Applications, Vol. 57, Springer-Verlag, New York, 2011.
   Google Scholar
• M.T. Thai and P.M. Pardalos, Handbook of Optimization in Complex Networks: Communication and Social Networks, Vol. 58, Springer-Verlag, New York, 2011.
   Google Scholar
• A. Veremyev, V. Boginski, and E.L. Pasiliao, Exact identification of critical nodes in sparse networks via new compact formulations, Optim. Lett. 8(4) (2014), pp. 1245–1259. doi: 10.1007/s11590-013-0666-x
   Web of Science ®Google Scholar
• 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), pp. 233–273. doi: 10.1007/s10878-014-9730-4
   Web of Science ®Google Scholar
• A. Veremyev, O.A. Prokopyev, and E.L. Pasiliao, Critical nodes for distance-based connectivity and related problems in graphs, Networks 66(3) (2015), pp. 170–195. doi: 10.1002/net.21622
   Web of Science ®Google Scholar
• J.L. Walteros and P.M. Pardalos, Selected topics in critical element detection, in Applications of Mathematics and Informatics in Military Science, Nicholas Daras, ed., Springer-Verlag, New York, 2012, pp. 9–26.
   Google Scholar
• D.J. Wang, X. Shi, D.A. McFarland, and J. Leskovec, Measurement error in network data: A re-classification, Soc. Netw. 34(4) (2012), pp. 396–409. doi: 10.1016/j.socnet.2012.01.003
   Web of Science ®Google Scholar
• D.J. Watts and S.H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature 393(6684) (1998), pp. 440–442. doi: 10.1038/30918
   PubMed Web of Science ®Google Scholar
• K. Xu and K.C. Das, On Harary index of graphs, Discrete Appl. Math. 159(15) (2011), pp. 1631–1640. doi: 10.1016/j.dam.2011.06.003
   Web of Science ®Google Scholar