Saturday , June 23 2018

Revisiting Models of Vulnerabilities of the Networks

Horia-Nicolai L. TEODORESCU1,2 
1 Romanian Academy, Iasi Branch,
Bd. Carol I nr. 8, Iasi, Romania
2 “Gheorghe Asachi” Technical University of Iasi Romania,
Str. D. Mangeron 64, Iasi, Romania

Abstract: The study critically revisits the models of ‘vulnerability’ of various types of networks and shows several limits of the current state of the art, including the ambiguous definitions of vulnerability and robustness concepts, the arbitrary use of various connectivity indexes on graphs for assessing the ‘vulnerability’ of real-world networks to real-world attacks, the lack of any evidence for the proposed models, and the lack of significant statistical approaches. Next, the study shows the limits of using the world ‘measure’ and ‘metric’ in relation with connectivity characteristics on graphs. Then, a general cause-effect chain for attacks on networks, especially computer and transportation networks is laid down as a basis for probabilistic model building. Evidence is provided on the relation between graph features and the probabilities of events under an attack and model examples are discussed. An annex on the caution of making public detailed knowledge on such models ends the paper.

Keywords: networks, attacks, risk, connectivity indexes, network vulnerability, probabilistic model, evidence.

>>Full text
Horia-Nicolai L. TEODORESCU,
Revisiting Models of Vulnerabilities of the Networks, Studies in Informatics and Control, ISSN 1220-1766, vol. 25(4), pp. 469-478, 2016.


For more than four decades, the issues of the reliability and vulnerability to attacks were studied for computer and communication networks (CCN), mainly using graph models and tools [4], [5], [25], [29]. More recently, similar tools have been applied to transportation systems in relation with several infamous attacks in various countries [8], [19]. A large number of studies have been recently devoted to the vulnerability of transportation networks [19], especially of subways [7], [9-11], [32], [33] due to several attacks on them. Many of these studies focused on the vulnerability of nodes and edges of the networks, in relation with the network topology, and proposed indexes of vulnerability, sometimes weighted by flows; in this way, the models for computer networks were directly transposed to transportation ones, without discussing the foundation of the model extension from one type of networks to another. These studies have no evidence support and remain largely disconnected from the real life situations; moreover, many of these studies use intuitive yet qualitative and vague meanings for features such as vulnerability, robustness, and resilience.

We critically revisit some of the concepts and issues related to ‘vulnerability’ and concerning specifically transportation networks; new network indexes are proposed that have the potential of being more suitable (Section 4). Next, probabilistic models are suggested for the attacks and for computing the outcome in probabilistic terms for attacks, depending on the node properties (Sections 3-5).

The first set of contributions of this study is theoretical; in obtaining them, the method applied is based on graph analysis and probabilistic approach; tentative speculative models are proposed (Sections 3-5). A second core contribution consists in binging evidence for the derivation of models for key probabilities involved in the analysis; examples are presented and references to actual transportation networks are made in Section 6. The remaining part of this introductory section is devoted to the terminology related to graph features and to the general concept of vulnerability.

The organization of the paper is largely linear; Section 2 reviews some graph models related to vulnerability of networks, while Section 3 and 4 clarify aspects related to chains of effects and the related probabilities. Section 5 details the role of nodes and edges in the attack probability of networks. A model based on seemingly natural assumption is built in Section 6 and its predictions are contrasted in Section 7 with the evidence-based models for attack probability. The last section contains conclusions.


  1. AHMAD, N., S. DERRIBLE, T. EASON, H. CABEZAS, Using Fisher Information in Big Data. (Oct. 5, 2016)
  2. ANTHONY, K. R. N., J. M. DAMBACHER, R. BEEDEN, A Framework for Understanding Cumulative Impacts, Supporting Environmental Decisions and Informing Resilience-­Based Management of the Great Barrier Reef World Heritage Area. Commonwealth of Australia 2013. Publisher Great Barrier Reef Marine Park Authority 2013. resources/2910cf7e-30fc-
    0.pdf. (Oct. 5, 2016)
  3. BORGATTI, S. P., Centrality and Network Flow. Social Networks vol. 27 (2005), pp. 55-71.
  4. BOESCH, F., R. THOMAS, On Graphs of Invulnerable Communication Nets. IEEE Transactions on Circuit Theory, 1970, Vol. 17, 2, pp. 183-192.
  5. BOESCH, F. T., A Survey and Introduction to Network Reliability Theory. ICC ’88, IEEE Int. Conf. Digital Technology – Spanning the Universe, 1988, vol. 2, pp. 678 – 682.
  6. BOESCH F., A. FELZER, On the Minimum m Degree Vulnerability Criterion. IEEE Trans. Circuit Theory, 1971, Vol., 18, 2, pp. 224 – 228.
  7. CHOPRA S. S., T. DILLON, M. M. BILEC, V. KHANNA, A Network-Based Framework for Assessing Infrastructure Resilience: A Case Study of the London Metro System. The Royal Society Interface, Vol. 13, 118, 2016 (p.20160113) Doi 10.1098/rsif.2016.0113, (accessed Oct. 5, 2016).
  8. DEHMER, M., M. S. NISTOR, W. SCHMITZ, K. A. NEUBECKER, Aspects of Quantitative Analysis of Transportation Networks. Future Security 2015, Berlin, Sep. 15-17, 2015, pp. 239-244.
  9. DERRIBLE, S (2012) Network Centrality of Metro Systems. PLoS ONE vol. 7, 7: e40575. doi:10.1371/journal.pone.0040575, (accessed Oct. 5, 2016).
  10. DERRIBLE S, AHMAD N. (2015), Network-Based and Binless Frequency Analyses. PLoS ONE 10(11): e0142108. doi:10.1371/journal.pone.0142108. (accessed Oct. 5, 2016).
  11. DERRIBLE S, C. KENNEDY, The Complexity and Robustness of Metro Networks. Physica A: Statistical Mechanics and its Applications, Vol. 389, 17, 1 Sep 2010, pp. 3678–3691.
  1. DONNINGER, C., The Distribution of Centrality in Social Networks. Social Networks, vol. 8 (1986), pp. 191-203.
  2. DUCRUET, C.,  J.-P. RODRIGUE, Graph Theory: Measures and Indices. (accessed 5, 2016).
  3. ESTRADA E., D. J. HIGHAM, N. HATANO, Communicability Between-ness in Complex Networks. https:// (accessed Oct. 5, 2016).
  4. EZELL, B. C., S. P. BENNETT, D. VON WINTERFELDT, J. SOKOLOWSKI, A. J. COLLINS, Probabilistic Risk Analysis and Terrorism Risk. Risk Analysis, Vol. 30, No. 4, 2010.
  5. FREEMAN, L. C., Centrality in Social Networks Conceptual Clarification. Social Networks, vol. 1, 3, (1978), pp. 215-239.
  6. HABIB M., F. DE MONTGOLFIER, C. PAUL, A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension. In T. Hagerup, J. Katajainen (Eds.) 9th Scandinavian Workshop on Algorithm Theory, 2004, Humlebaek, Denmark. Springer, pp.187-198, 2004, LNCS vol. 3111.
  7. HERNANDEZ, J. M., P. van MIEGHEM, Classification of Graph Metrics. (accessed Oct. 5, 2016).
  8. KERMANSHAH, A., S. DERRIBLE, A Geographical and Multi-Criteria Vulnerability Assessment of Transpor-tation Networks against Extreme Earth-quakes. Reliability Engineering & System Safety, Vol. 153, Sep 2016, pp. 39–49.
  9. KLINKE, A., O. RENN, A New Approach to Risk Evaluation and Management: Risk-Based, Precaution-Based, and Discourse-Based Strategies. Risk Analysis, Vol. 22, No. 6, 2002.
  10. LI, C., Q. LI, P. Van MIEGHEM, H. E. STANLEY, H. WANG, Correlation between Centrality Metrics and their Application to the Opinion Model. 2014. (accessed Oct. 2, 2016).
  11. LINKOV, I., et al., Changing the Resilience Paradigm. Nature Climate Change, 4, pp. 407–409 (2014).
  12. PIRAVEENAN, M, M. PROKOPENKO, L. HOSSAIN, Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks. PLoS ONE, vol. 8, 1 (2013): e53095. doi:10.1371/journal.pone.0053095 (accessed Oct. 1, 2016).
  13. SAREWITZ D., R. PIELKE, JR., M. KEYKHAH, Vulnerability and Risk: Some Thoughts from a Political and Policy Perspective. Risk Analysis, Vol. 23, No. 4, 2003.
  14. SOI, I. M., K. K. AGGARWAL, Reliability Indices for Topological Design of Computer Communication Networks. IEEE Trans. Reliability, Vol. R-30, 5, Dec. 1981, pp. 438-443.
  15. TEODORESCU H.-N., Defining Resilience using Probabilistic Event Trees, Environment Systems and Decisions, 2015, Vol. 35, 2, pp. 279–290.
  16. TEODORESCU H.-N. L., S. W. PICKL, Properties and Use of a Resilience Index in Disaster Preparation and Response. 2016 IEEE Int. Symp. Technologies for Homeland Security, May 10-12 Waltham, MA USA.
  17. TEODORESCU H.-N., S. W. PICKL, Computing and Optimizing the Index of Resilience of Networks and Information Systems. Romanian J. Information Science and Technology Vol. 19, 1-2, 2016, pp. 116–126.
  18. TEODORESCU H.-N., A. KIRSCHENBAUM, S. COJOCARU, C. BRUDERLEIN (Eds.), Improving Disaster Resilience and Mitigation- IT Means and Tools. NATO Science for Peace and Security Series – C: Environmental Security, no. 1874-6519, 2014, Springer, New York, Ch. 1.
  19. TIZGHADAM A., A. LEON-GARCIA, Betweenness Centrality and Resistance Distance in Communication Networks. IEEE Network, Nov/Dec 2010, pp. 10-16.
  20. WANG, H., J. M. HERNANDEZ, P. Van MIEGHEM, Betweenness Centrality in a Weighted Network. Physical Review E 77, 046105 2008.
  21. ZENIL, H., S. DERRIBLE, World Metro Networks, Wolfram Demonstration Project http://demonstrations. (accessed Oct. 2, 2016), Published: Jan 29, 2014
  22. YIN, H., B. HAN, D. LI, Y. WANG, Evaluating Disruption in Rail Transit Network: A Case Study of Beijing Subway. Procedia Engineering, Vol. 137, 2016, pp. 49-58.
  23. *** ResumeNet, European Union Research Framework Programme 7, FP – 224619] (accessed Oct. 5, 2016).
  24. *** incidents_in_2010 (accessed Oct. 5, 2016).