Fast Shortest Distance Estimation via Lighthouse-Based Label on Graph

Shortest distances estimation plays a crucial role in fields such as social network analysis, bioinformatics, and navigation systems. While the traditional Breadth First Search (BFS) algorithm is effective, it often incurs high computational costs when handling large datasets. Therefore, researches of labeling-based shortest distance estimation have been emerged, but there are still issues with insufficient accuracy and difficulty in controlling estimation errors. This paper introduces a method for constructing node coordinates based on peripheral node information called the Lighthouse-Coordinate (LC) Algorithm, which includes three components, Lighthouse Sampling (LS), Coordination Construction (CC), and Coordinate Distance Calculation (CDC).We first perform LS to collect candidate nodes for labelling as lighthouses for shortest distance estimation, then create the coordinates of all sampled lighthouses via CC based on their structural information, and finally estimate the approximate shortest distance by CDC using the constructed coordinates. It is worth mentioning that LC algorithm is an error controllable method, where users pre-define a maximum distance error <em>E</em>_max and LC algorithm returns an estimated shortest distance of two nodes ≤ <em>E</em>_max. We theoretically analyzed the estimated shortest distance is upper bounded by <em>E</em>_max. We conducted experiments on five real-world datasets and demonstrated an acceleration effect of one to three orders of magnitude, while also achieving controllable errors given the user-specific error bound.