Sub-graph Sharing for Faster Betweenness Centrality Computation on Road Networks

Abstract

Betweennesss Centrality (BC) is a widely used vertex importance indicator in road networks as its shortest path number-based definition can reflect the influence of network quality on the actual traffic condition. Besides, as the traffic condition changes over time, its BC also involves correspondingly. However, all the existing methods rely on the Brandes algorithm, which is slow to run due to its searching nature. Therefore, we improve the BC computation by modifying Brandes’ behavior. Firstly, we analyze Brandes theoretically and identify three key elements. After that, we propose a new query-based scheme to avoid graph searching. Thirdly, we propose a novel shortest path sub-graph-sharing to reduce repeated computation and finally propose the hybrid BC computation framework that combines shared search and query-based scheme. Experiments on real-life road networks validate the effectiveness of our new BC computation scheme. Show more