Fast Computation of Betweenness Centrality to Locate Vulnerabilities in Very Large Road Networks

The ability to detect critical spots in transportation networks is fundamental to improve traffic operations and road-network resilience. Real-time monitoring of these networks, especially in very large metropolitan areas, is a compelling challenge due to the complexity of computing robustness metrics. This paper presents a study of vulnerability in a real-world, very-large road network by adopting graph-based modeling and analysis, and big-data techniques for processing the related datasets. The authors first analyze the correlation between global efficiency and betweenness centrality, proving that nodes with higher betweenness centrality influence network vulnerability the most. Then, the authors present an algorithm for fast computation of approximated betweenness centrality that significantly reduces execution time. The evaluation shows that the approximation error does not significantly affect the most critical nodes, thus making the algorithm well-suited for on-line operational monitoring of road networks vulnerability

• Supplemental Notes:
  • This paper was sponsored by TRB committee ABJ30 Standing Committee on Urban Transportation Data and Information Systems.
• Authors:
  • Furno, Angelo
  • El Faouzi, Nour-Eddin
  • Sharma, Rajesh
  • Zimeo, Eugenio
• Conference:
  • Transportation Research Board 97th Annual Meeting
  • Location: Washington DC, United States
  • Date: 2018-1-7 to 2018-1-11
• Date: 2018

Language

• English

Media Info

• Media Type: Digital/other
• Features: Figures; Maps; References;
• Pagination: 17p

Subject/Index Terms

• TRT Terms: Algorithms; Data analysis; Disaster resilience; Highways; Metropolitan areas; Network analysis (Planning); Network nodes; Risk assessment
• Subject Areas: Data and Information Technology; Highways; Planning and Forecasting; Security and Emergencies;

Filing Info

• Accession Number: 01658670
• Record Type: Publication
• Report/Paper Numbers: 18-04089
• Files: TRIS, TRB, ATRI
• Created Date: Jan 31 2018 4:58PM