Computational complexity of network vulnerability analysis
ACTA UNIVERSITATIS SAPIENTIAE INFORMATICA, cilt.14, sa.2, ss.199-207, 2022 (ESCI)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 14 Sayı: 2
- Basım Tarihi: 2022
- Dergi Adı: ACTA UNIVERSITATIS SAPIENTIAE INFORMATICA
- Derginin Tarandığı İndeksler: Emerging Sources Citation Index (ESCI)
- Sayfa Sayıları: ss.199-207
- Dokuz Eylül Üniversitesi Adresli: Evet
Özet
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^3) and Θ(n^4) on unweighted networks,
respectively, where n is the number of nodes.