Computational complexity of network vulnerability analysis

Murat Erşen Berberler

doi:10.2478/ausi-2022-0012

Abstract

Residual closeness is recently proposed as a vulnerability measure to characterize the stability of complex networks. Residual closeness is essential in the analysis of complex networks, but costly to compute. Currently, the fastest known algorithms run in polynomial time. Motivated by the fast-growing need to compute vulnerability measures on complex networks, new algorithms for computing node and edge residual closeness are introduced in this paper. Those proposed algorithms reduce the running times to Θ(n³) and Θ (n⁴) on unweighted networks, respectively, where n is the number of nodes.

References

[1] A. Aytaç, Z. N. Berberler, Residual closeness for helm and sunflower graphs, TWMS J. App. Eng. Math. 7, 2 (2017) 209–220. ⇒200
Search in Google Scholar Back to article
[2] A. Aytaç, Z. N. Berberler, Robustness of regular caterpillars, Int. J. Found. Comp. Sci. 28, 7 (2017) 835–841. ⇒20010.1142/S0129054117500277
Search in Google Scholar Back to article
[3] A. Aytaç, Z. N. Odaba Berberler, Network robustness and residual closeness, RAIRO Oper. Res. 52, 3 (2018) 839–847. ⇒20010.1051/ro/2016071
Search in Google Scholar Back to article
[4] B. L. Piazza, F. S. Robertst, S. K. Stueckle, Edge-tenacious networks, Networks 25 (1995) 7–17. ⇒20010.1002/net.3230250103
Search in Google Scholar Back to article
[5] C. A. Barefoot, R. Entringer, H. Swart, Vulnerability in graphs—a comparative survey, J. Combin. Math. Combin. Comput. 1 (1987) 13–22. ⇒200
Search in Google Scholar Back to article
[6] C. Dangalchev, Residual Closeness in Networks, Physica A 365 (2006) 556–564. ⇒200, 20110.1016/j.physa.2005.12.020
Search in Google Scholar Back to article
[7] D. Bauer, S. L. Hakimi, E. Schmeichel, Recognizing tough graphs is NP-hard, Discrete Applied Mathematics 28 (1990) 191-195. ⇒20010.1016/0166-218X(90)90001-S
Search in Google Scholar Back to article
[8] D. E. Mann, The tenacity of trees, Ph.D. Thesis, Northeastern University (1993). ⇒200
Search in Google Scholar Back to article
[9] D. Gusfield, Connectivity and edge disjoint spanning trees, Inform. Process. Lett. 16 (1983) 87-89. ⇒20010.1016/0020-0190(83)90031-5
Search in Google Scholar Back to article
[10] D. Kratsch, T. Kloks, H. Müller, Measuring the vulnerability for classes of intersection graphs, Discrete Applied Mathematics 77 (1997) 259–270. ⇒20010.1016/S0166-218X(96)00133-3
Search in Google Scholar Back to article
[11] D. Moazzami, An Algorithm for the Computation of Edge Integrity, International Journal of Contemporary Mathematical Sciences 6, 11 (2011) 507-516. ⇒200
Search in Google Scholar Back to article
[12] E. Yiğit, Z. N. Berberler, A Note on the Link Residual Closeness of Graphs Under Join Operation, International Journal of Foundations of Computer Science 30, 3 (2019) 417-424. ⇒20010.1142/S0129054119500126
Search in Google Scholar Back to article
[13] E. Yiğit, Z. N. Berberler, Link failure in wheel type networks, International Journal of Modern Physics C 30, 9 (2019) 1950072. ⇒20010.1142/S0129183119500724
Search in Google Scholar Back to article
[14] F. Li, Q. Ye, X. Li, Tenacity and Rupture Degree of Permutation Graphs of Complete Bipartite Graphs, Bulletin of the Malaysian Mathematical Sciences Society 34, 3 (2011) 423-434. ⇒200
Search in Google Scholar Back to article
[15] H. A. Jung, On a class of posets and the corresponding comparability graphs, Journal of Combinatorial Theory, Series B 24, 2 (1978) 125–133. ⇒20010.1016/0095-8956(78)90013-8
Search in Google Scholar Back to article
[16] H. Frank, I. T. Frisch, Analysis and design of survivable networks, IEEE Transactions on Communications Technology COM-18 567 (1970). ⇒20010.1109/TCOM.1970.1090419
Search in Google Scholar Back to article
[17] M. Cozzens, D. Moazzami, S. Stueckle, The tenacity of a graph, Seventh International Conference on the Theory and Applications of Graphs, Wiley, New York, 1995, pp. 1111–1122. ⇒200
Search in Google Scholar Back to article
[18] M. E. J. Newman, The structure and function of complex networks, SIAM Review 45, 2 (2003) 167-256. ⇒19910.1137/S003614450342480
Search in Google Scholar Back to article
[19] M. R. Fellows, S. Stueckle, The immersion order, forbidden subgraphs and the complexity of network integrity, J. Combin. Math. Combin. Comput. 6 (1989) 23-32. ⇒200
Search in Google Scholar Back to article
[20] R. W. Floyd, Algorithm 97: Shortest path, Communications of the ACM 5,6 (1962) 345. ⇒20110.1145/367766.368168
Search in Google Scholar Back to article
[21] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D. U. Hwanga, Complex networks: structure and dynamics, Physics Reports 424 (2006) 175-308. ⇒19910.1016/j.physrep.2005.10.009
Search in Google Scholar Back to article
[22] S. Zhang, X. Li, X. Han, Computing the scattering number of graphs, International Journal of Computer Mathematics 79, 2 (2002) 179-187. ⇒20010.1080/00207160211919
Search in Google Scholar Back to article
[23] T. H. Cormen, C. Stein, R. L. Rivest, C. E. Leiserson, Introduction to Algorithms (2nd Edition), McGraw-Hill Higher Education, 2001. ⇒202
Search in Google Scholar Back to article
[24] T. Turacı, Computing the closeness centralities of a type of the probabilistic neural networks, Romanian Journal of Mathematics and Computer Science 11, 2 (2021) 1-12. ⇒200
Search in Google Scholar Back to article
[25] T. Turacı,M.Ökten, Vulnerability of Mycielski Graphs via Residual Closeness, Ars Combinatoria 118 (2015) 419-427. ⇒200
Search in Google Scholar Back to article
[26] T. Turacı,V.Aytaç, Residual Closeness of Splitting Networks, Ars Combinatoria 130 (2017) 17-27. ⇒200
Search in Google Scholar Back to article
[27] V. Aytaç, T. Turacı, Closeness Centrality in Some Splitting Networks, Computer Science Journal of Moldova 26, 3 78 (2018) 251-269. ⇒200
Search in Google Scholar Back to article
[28] V. Chvàtal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228. ⇒20010.1016/0012-365X(73)90138-6
Search in Google Scholar Back to article
[29] Y. K. Li, On reliability parameters of graphs, MA Thesis, Northwestern Polytechnical University, 2003. ⇒200
Search in Google Scholar Back to article
[30] Y. K. Li, S. G. Zhang, X. L. Li, Rupture degree of graphs, Int. J. Comput. Math. 82, 7 (2005) 793-803. ⇒20010.1080/00207160412331336062
Search in Google Scholar Back to article
[31] Z. N. Berberler, E. Yiğit, Computing the link vulnerability of networks in polynomial time, I. International University Industry Cooperation, R&D and Innovation Congress, 2017. ⇒200, 202
Search in Google Scholar Back to article
[32] Z. N. Berberler, E. Yiğit, Link vulnerability in networks, International Journal of Foundations of Computer Science 29, 3 (2018) 447-456. ⇒20010.1142/S0129054118500144
Search in Google Scholar Back to article
[33] Z. N. Berberler, Residual closeness in communication networks, Ph.D. Thesis, Ege University, Turkey, 2014. ⇒200, 202
Search in Google Scholar Back to article

Computational complexity of network vulnerability analysis

Abstract

Paradigm

My account