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

J 2019

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

VODÁK, Rostislav, Michal BÍL, Tomáš SVOBODA, Zuzana KŘIVÁNKOVÁ, Jan KUBEČEK et. al.

Základní údaje

Originální název

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

Autoři

VODÁK, Rostislav (203 Česká republika), Michal BÍL (203 Česká republika, garant), Tomáš SVOBODA (203 Česká republika, domácí), Zuzana KŘIVÁNKOVÁ (203 Česká republika), Jan KUBEČEK (203 Česká republika), Tomáš REBOK (203 Česká republika, domácí) a Petr HLINĚNÝ (203 Česká republika, domácí)

Vydání

PLOS ONE, United States, Public Library of Science, 2019, 1932-6203

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL URL

Impakt faktor

Impact factor: 2.740

Kód RIV

RIV/00216224:14610/19:00110256

Organizační jednotka

Ústav výpočetní techniky

DOI

http://dx.doi.org/10.1371/journal.pone.0219658

UT WoS

000482331900036

Klíčová slova anglicky

road networks; road network disruptions; road traffic collisions; transportation; graph algorithms

Štítky

J-Q1, rivok

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 23. 8. 2022 15:24, RNDr. Tomáš Rebok, Ph.D.

Anotace

V originále

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.

Návaznosti

CZ.1.05/3.2.00/08.0144, interní kód MU

Název: CERIT Scientific Cloud (Akronym: CERIT - SC)

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, CERIT Scientific Cloud, 3.2 Propagace a informovanost

LM2015085, projekt VaV

Název: CERIT Scientific Cloud (Akronym: CERIT-SC)

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, CERIT Scientific Cloud

Citovat

VODÁK, Rostislav, Michal BÍL, Tomáš SVOBODA, Zuzana KŘIVÁNKOVÁ, Jan KUBEČEK, Tomáš REBOK a Petr HLINĚNÝ. A deterministic approach for rapid identification of the critical links in networks. PLOS ONE. United States: Public Library of Science, 2019, roč. 14, č. 7, s. 1-18. ISSN 1932-6203. Dostupné z: https://dx.doi.org/10.1371/journal.pone.0219658.

@article{1546976,
   author = {Vodák, Rostislav and Bíl, Michal and Svoboda, Tomáš and Křivánková, Zuzana and Kubeček, Jan and Rebok, Tomáš and Hliněný, Petr},
   article_location = {United States},
   article_number = {7},
   doi = {http://dx.doi.org/10.1371/journal.pone.0219658},
   keywords = {road networks; road network disruptions; road traffic collisions; transportation; graph algorithms},
   language = {eng},
   issn = {1932-6203},
   journal = {PLOS ONE},
   title = {A deterministic approach for rapid identification of the critical links in networks},
   url = {https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0219658},
   volume = {14},
   year = {2019}
}

TY  - JOUR
ID  - 1546976
AU  - Vodák, Rostislav - Bíl, Michal - Svoboda, Tomáš - Křivánková, Zuzana - Kubeček, Jan - Rebok, Tomáš - Hliněný, Petr
PY  - 2019
TI  - A deterministic approach for rapid identification of the critical links in networks
JF  - PLOS ONE
VL  - 14
IS  - 7
SP  - 1-18
EP  - 1-18
PB  - Public Library of Science
SN  - 19326203
KW  - road networks
KW  - road network disruptions
KW  - road traffic collisions
KW  - transportation
KW  - graph algorithms
UR  - https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0219658
N2  - 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.
ER  -

VODÁK, Rostislav, Michal BÍL, Tomáš SVOBODA, Zuzana KŘIVÁNKOVÁ, Jan KUBEČEK, Tomáš REBOK a Petr HLINĚNÝ. A deterministic approach for rapid identification of the critical links in networks. \textit{PLOS ONE}. United States: Public Library of Science, 2019, roč.~14, č.~7, s.~1-18. ISSN~1932-6203. Dostupné z: https://dx.doi.org/10.1371/journal.pone.0219658.

Podrobný výpis o publikaci