<abstract xmlns="http://www.w3.org/1999/xhtml">

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.
</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 Θ(n3) and Θ (n4) on unweighted networks, respectively, where n is the number of nodes.

Computational complexity of network vulnerability analysis

Faculty of Science, Department of Computer Science

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

{"article-title":"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...

Computational complexity of network vulnerability analysis

Online veröffentlicht: 04. Feb. 2023

Seitenbereich: 199 - 207

Eingereicht: 05. Okt. 2022

Akzeptiert: 13. Nov. 2022

DOI: https://doi.org/10.2478/ausi-2022-0012

Schlüsselwörter
Vulnerability, complex networks, design of algorithms, graph algorithms

© 2022 Murat Erşen Berberler, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Computational complexity of network vulnerability analysis

Online veröffentlicht: 04. Feb. 2023

Seitenbereich: 199 - 207

Eingereicht: 05. Okt. 2022

Akzeptiert: 13. Nov. 2022

DOI: https://doi.org/10.2478/ausi-2022-0012

SchlüsselwörterVulnerability, complex networks, design of algorithms, graph algorithms

© 2022 Murat Erşen Berberler, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Schlüsselwörter
Vulnerability, complex networks, design of algorithms, graph algorithms