Graph-based ahead monitoring of vulnerabilities in large dynamic transportation networks.
Betweenness Centrality (BC) has proven to be a fundamental metric in many domains to identify the components (nodes) of a system modelled as a graph that are mostly traversed by information flows thus being critical to the proper functioning of the system itself. In the transportation domain, the me...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2021-01-01
|
| Series: | PLoS ONE |
| Online Access: | https://doi.org/10.1371/journal.pone.0248764 |
| _version_ | 1819028575817302016 |
|---|---|
| author | Angelo Furno Nour-Eddin El Faouzi Rajesh Sharma Eugenio Zimeo |
| author_facet | Angelo Furno Nour-Eddin El Faouzi Rajesh Sharma Eugenio Zimeo |
| author_sort | Angelo Furno |
| collection | DOAJ |
| description | Betweenness Centrality (BC) has proven to be a fundamental metric in many domains to identify the components (nodes) of a system modelled as a graph that are mostly traversed by information flows thus being critical to the proper functioning of the system itself. In the transportation domain, the metric has been mainly adopted to discover topological bottlenecks of the physical infrastructure composed of roads or railways. The adoption of this metric to study the evolution of transportation networks that take into account also the dynamic conditions of traffic is in its infancy mainly due to the high computation time needed to compute BC in large dynamic graphs. This paper explores the adoption of dynamic BC, i.e., BC computed on dynamic large-scale graphs, modeling road networks and the related vehicular traffic, and proposes the adoption of a fast algorithm for ahead monitoring of transportation networks by computing approximated BC values under time constraints. The experimental analysis proves that, with a bounded and tolerable approximation, the algorithm computes BC on very large dynamically weighted graphs in a significantly shorter time if compared with exact computation. Moreover, since the proposed algorithm can be tuned for an ideal trade-off between performance and accuracy, our solution paves the way to quasi real-time monitoring of highly dynamic networks providing anticipated information about possible congested or vulnerable areas. Such knowledge can be exploited by travel assistance services or intelligent traffic control systems to perform informed re-routing and therefore enhance network resilience in smart cities. |
| first_indexed | 2024-12-21T06:00:33Z |
| format | Article |
| id | doaj.art-f0532c607f7b4107b8a722f2232445ff |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-12-21T06:00:33Z |
| publishDate | 2021-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-f0532c607f7b4107b8a722f2232445ff2022-12-21T19:13:46ZengPublic Library of Science (PLoS)PLoS ONE1932-62032021-01-01163e024876410.1371/journal.pone.0248764Graph-based ahead monitoring of vulnerabilities in large dynamic transportation networks.Angelo FurnoNour-Eddin El FaouziRajesh SharmaEugenio ZimeoBetweenness Centrality (BC) has proven to be a fundamental metric in many domains to identify the components (nodes) of a system modelled as a graph that are mostly traversed by information flows thus being critical to the proper functioning of the system itself. In the transportation domain, the metric has been mainly adopted to discover topological bottlenecks of the physical infrastructure composed of roads or railways. The adoption of this metric to study the evolution of transportation networks that take into account also the dynamic conditions of traffic is in its infancy mainly due to the high computation time needed to compute BC in large dynamic graphs. This paper explores the adoption of dynamic BC, i.e., BC computed on dynamic large-scale graphs, modeling road networks and the related vehicular traffic, and proposes the adoption of a fast algorithm for ahead monitoring of transportation networks by computing approximated BC values under time constraints. The experimental analysis proves that, with a bounded and tolerable approximation, the algorithm computes BC on very large dynamically weighted graphs in a significantly shorter time if compared with exact computation. Moreover, since the proposed algorithm can be tuned for an ideal trade-off between performance and accuracy, our solution paves the way to quasi real-time monitoring of highly dynamic networks providing anticipated information about possible congested or vulnerable areas. Such knowledge can be exploited by travel assistance services or intelligent traffic control systems to perform informed re-routing and therefore enhance network resilience in smart cities.https://doi.org/10.1371/journal.pone.0248764 |
| spellingShingle | Angelo Furno Nour-Eddin El Faouzi Rajesh Sharma Eugenio Zimeo Graph-based ahead monitoring of vulnerabilities in large dynamic transportation networks. PLoS ONE |
| title | Graph-based ahead monitoring of vulnerabilities in large dynamic transportation networks. |
| title_full | Graph-based ahead monitoring of vulnerabilities in large dynamic transportation networks. |
| title_fullStr | Graph-based ahead monitoring of vulnerabilities in large dynamic transportation networks. |
| title_full_unstemmed | Graph-based ahead monitoring of vulnerabilities in large dynamic transportation networks. |
| title_short | Graph-based ahead monitoring of vulnerabilities in large dynamic transportation networks. |
| title_sort | graph based ahead monitoring of vulnerabilities in large dynamic transportation networks |
| url | https://doi.org/10.1371/journal.pone.0248764 |
| work_keys_str_mv | AT angelofurno graphbasedaheadmonitoringofvulnerabilitiesinlargedynamictransportationnetworks AT noureddinelfaouzi graphbasedaheadmonitoringofvulnerabilitiesinlargedynamictransportationnetworks AT rajeshsharma graphbasedaheadmonitoringofvulnerabilitiesinlargedynamictransportationnetworks AT eugeniozimeo graphbasedaheadmonitoringofvulnerabilitiesinlargedynamictransportationnetworks |