Computational complexity of network vulnerability analysis
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-grow...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Sciendo
2022-12-01
|
| Series: | Acta Universitatis Sapientiae: Informatica |
| Subjects: | |
| Online Access: | https://doi.org/10.2478/ausi-2022-0012 |
| _version_ | 1811159173947195392 |
|---|---|
| author | Berberler Murat Erşen |
| author_facet | Berberler Murat Erşen |
| author_sort | Berberler Murat Erşen |
| collection | DOAJ |
| description | 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 Θ(n3) and Θ (n4) on unweighted networks, respectively, where n is the number of nodes. |
| first_indexed | 2024-04-10T05:37:45Z |
| format | Article |
| id | doaj.art-58e4cec3b475437ea396b7749b5aacb1 |
| institution | Directory Open Access Journal |
| issn | 2066-7760 |
| language | English |
| last_indexed | 2024-04-10T05:37:45Z |
| publishDate | 2022-12-01 |
| publisher | Sciendo |
| record_format | Article |
| series | Acta Universitatis Sapientiae: Informatica |
| spelling | doaj.art-58e4cec3b475437ea396b7749b5aacb12023-03-06T17:00:03ZengSciendoActa Universitatis Sapientiae: Informatica2066-77602022-12-0114219920710.2478/ausi-2022-0012Computational complexity of network vulnerability analysisBerberler Murat Erşen0Faculty of Science, Department of Computer Science, Dokuz Eylül University, 35160, Izmir, TürkiyeResidual 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 Θ(n3) and Θ (n4) on unweighted networks, respectively, where n is the number of nodes.https://doi.org/10.2478/ausi-2022-0012vulnerabilitycomplex networksdesign of algorithmsgraph algorithms05c4068m1068r10 |
| spellingShingle | Berberler Murat Erşen Computational complexity of network vulnerability analysis Acta Universitatis Sapientiae: Informatica vulnerability complex networks design of algorithms graph algorithms 05c40 68m10 68r10 |
| title | Computational complexity of network vulnerability analysis |
| title_full | Computational complexity of network vulnerability analysis |
| title_fullStr | Computational complexity of network vulnerability analysis |
| title_full_unstemmed | Computational complexity of network vulnerability analysis |
| title_short | Computational complexity of network vulnerability analysis |
| title_sort | computational complexity of network vulnerability analysis |
| topic | vulnerability complex networks design of algorithms graph algorithms 05c40 68m10 68r10 |
| url | https://doi.org/10.2478/ausi-2022-0012 |
| work_keys_str_mv | AT berberlermuratersen computationalcomplexityofnetworkvulnerabilityanalysis |