On network criticality in robustness analysis of a network structure

A. Bharali; Dimpee Baruah

doi:10.26637/MJM0702/0013

Abstract

Robustness of a network is the ability of the network to maintain its functionality when some vertices or edges are removed due to targeted attacks or random failures. This paper studies an interesting graph measure that we call the network criticality. The notion of network criticality is derived from the probabilistic definition of betweenness, which is defined based on random walks in a graph, as the main metric to quantify the survival value of a network with respect to changes in topology and dynamics. The objective of the paper is twofold. First, we discuss some known formulae of network criticality and derive its relation with some other graph measures. Second, we
propose a new measure of network functionality based on network criticality.

Keywords:

Robustness, Network criticality, Graph measures

Mathematics Subject Classification:

Mathematics

Authors Imprint References Funding Related Articles Downloads

A. Bharali Department of Mathematics, Dibrugarh University, Dibrugarh-786004, India. https://orcid.org/0000-0001-8642-3933
Dimpee Baruah Department of Mathematics, Dibrugarh University, Dibrugarh-786004, India.

Pages: 223-229
Date Published: 01-04-2019
Vol. 7 No. 02 (2019): Malaya Journal of Matematik (MJM)

Albert, R., Jeong, H., & Barabasi, A., Error and attack tolerance of complex networks. Nature, 406 (2000) 378382.

Berdica, K., An introduction to road vulnerability: what has been done, is done and should be done. Transport Policy, 9(2) (2002) 117-127.

Bernstein, Dennis S., Matrix Mathematics. Princeton University Press. 2005.

Bell, MGH, & Iida, Y., Transportation Network Analysis, Wiley, 1997.

Beygelzimer, A., Grinstein, G., Linsker, R., & Rish, I, Improving network robustness. Proceedings of the International Conference on Autonomic Computing (ICAC'04). IEEE Xplore, USA. 2004.

Biggs, N., Algebraic Graph theory. Cambridge Univ Press, USA. 1996.

Billington, R., & Allan, R., Reliability evaluation of engineering systems: Concepts & techniques. New York, USA: Plenum Press Publish. 1992.

Ellens, W., Spieksma, F. M., Mieghem, P. Van, Jamakovic, A., & Kooijb, R.E., Effective graph resistance. Linear Algebra and its Applications, 435 (2011) 24912506.

Freeman, L., Centrality in social networks conceptual classification, Social Networks, 1 (1978) 215-239.

Gribble, S., Robustness in complex systems. Proceedings Eighth Workshop on Hot Topics in Operating Systems, (2001) 22-26.

Iida, Y., Basic concepts and future directions of road network reliability analysis. Journal of Advanced Transportation, 33(2) (1999) 125-134.

Immers, B., & Jansen, B., Unreliable travel times: Cause and ways of improvement through adequate network design. In Symposium of the reliability of traveling and the robustness of transport systems. Delft, The Netherlands. 2005.

Jeong, H., Tombor, B., Albert, R., Oltvai, Z., & Barabasi, A., The large-scale organization of metabolic networks. Nature, 407 (2000) 651-654.

Klein, D. J., & Randić. M., Resistance distance. Journal of Mathematical Chemistry, 12 (1993) 81-95.

Koulakezian, A., Soliman, H. M., Tang, T., & LeonGarcia, A., Robust Traffic Assignment in Transportation Networks Using Network Criticality. IEEE Vehicular Technology Conference, (2012) 1-5.

Shargel, B., Sayama, H., Epstein, I., & Bar-Yam, Y., Optimization of robustness and connectivity in complex networks. Physical Review Letters, 90(6):068701 (2003).

Tizghadam, A., & Leon-Garcia, A., On robust traffic engineering in Core networks. Global Telecommunications Conference, IEEE GLOBECOM, (2008) 1-6.

Tizghadam, A., & Leon-Garcia, A., Autonomic Traffic Engineering for Network Robustness. IEEE Journal on Selected Areas in Communications, 28(1) (2010) 39-50.

Tu, Y., How robust is the internet? Nature, 406 (2000) 353-354.

Wang, X., Pournaras, E., Kooij, R. E., & Mieghem, P. Van, Improving robustness of complex networks via effective graph resistance. The European Physical Journal B, $87: 221(2014)$.