Finding critical regions in a network

Finding critical regions in a network

Trajanovski, S.
Kuipers, F. A.
Van Mieghem, P.

Electrical Engineering, Mathematics and Computer Science

Intelligent Systems

2013-04-19

It is important that our vital networks (e.g., infrastructures) are robust to more than single-link failures. Failures might for instance affect a part of the network that resides in a certain geographical region. In this paper, considering networks embedded in a two-dimensional plane, we study the problem of finding a critical region - that is, a part of the network that can be enclosed by a given elementary figure (a circle, ellipse, rectangle, square, or equilateral triangle) with a predetermined size - whose removal would lead to the highest network disruption. We determine that there is a polynomial number of non-trivial positions for such a figure that need to be considered and, subsequently, we propose a polynomial-time algorithm for the problem. Simulations on realistic networks illustrate that different figures with equal area result in different critical regions in a network.

geographical failures
critical regions
network robustness
computational geometry

http://resolver.tudelft.nl/uuid:0e9209fa-8798-4698-8315-81cf20686263

IEEE

978-1-4673-5944-3

Proceedings of IEEE INFOCOM 2013, Turin, Italy, 14-19 April 2013; pre-print version, presented at the 5th International NetSciCom

https://doi.org/10.1109/INFCOM.2013.6567167

Institutional Repository

conference paper

(c) 2013 IEEE