Efficient processing of coverage centrality queries on road networks

作者：Yehong Xu, Mengxuan Zhang, Ruizhong Wu, Lei Li, Xiaofang Zhou · 发表于：World Wide Web · 年份：2024 · DOI：10.1007/s11280-024-01248-5 · 被引用次数：4 · 研究领域：Data Management and Algorithms、Complex Network Analysis Techniques、Transportation Planning and Optimization

Abstract Coverage Centrality is an important metric to evaluate vertex importance in road networks. However, current solutions have to compute the coverage centrality of all the vertices together, which is resource-wasting, especially when only some vertices centrality is required. In addition, they have poor adaption to the dynamic scenario because of the computation inefficiency. In this paper, we focus on the coverage centrality query problem and propose a method that efficiently computes the centrality of single vertices without relying on the underlying graph being static by employing the intra-region pruning, inter-region pruning, and top-down search. We further propose the bottom-up search and mixed search to improve efficiency. Experiments validate the efficiency and effectiveness of our algorithms compared with the state-of-the-art method.