A deterministic approach for rapid identification of the critical links in networks

We introduce a rapid deterministic algorithm for identification of the most critical links which are capable of causing network disruptions. The algorithm is based on searching for the shortest cycles in the network and provides a significant time improvement compared with a common brute-force algor...

Full description

Saved in:
Bibliographic Details
Published in:PloS one 2019-07, Vol.14 (7), p.e0219658-e0219658
Main Authors: Vodák, Rostislav, Bíl, Michal, Svoboda, Tomáš, Křivánková, Zuzana, Kubeček, Jan, Rebok, Tomáš, Hliněný, Petr
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Computer and Information Sciences
Czech Republic
Data Collection
Deterministic models
Engineering and Technology
Humans
Identification
Links
Medicine and Health Sciences
Modern culture
Monte Carlo simulation
Nodes
Physical Sciences
Probability
Records
Research and Analysis Methods
Social Sciences
Software
Statistical analysis
Statistical analysis of data
Time
Transportation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce a rapid deterministic algorithm for identification of the most critical links which are capable of causing network disruptions. The algorithm is based on searching for the shortest cycles in the network and provides a significant time improvement compared with a common brute-force algorithm which scans the entire network. We used a simple measure, based on standard deviation, as a vulnerability measure. It takes into account the importance of nodes in particular network components. We demonstrate this approach on a real network with 734 nodes and 990 links. We found the worst scenarios for the cases with and without people living in the nodes. The evaluation of all network breakups can provide transportation planners and administrators with plenty of data for further statistical analyses. The presented approach provides an alternative approach to the recent research assessing the impacts of simultaneous interruptions of multiple links.
ISSN:1932-6203
1932-6203
DOI:10.1371/journal.pone.0219658