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 performed LS to collect candidate nodes for labelling as lighthouses for shortest distance estimation, then created the coordinates of all sampled lighthouses via CC based on their structural information, and finally estimated 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 $E_{\mathrm{m}\mathrm{a}\mathrm{x}}$ and LC algorithm returns an estimated shortest distance of two nodes $⩽E_{\mathrm{m}\mathrm{a}\mathrm{x}}$. We theoretically analyzed that the estimated shortest distance is upper bounded by $E_{\mathrm{m}\mathrm{a}\mathrm{x}}$. 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.