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.

Given an undirected graph, a specific query, and an cohesiveness parameter, Community Search (CS) aims to identify a cohesive subgraph forming as a community from the undirected graph that includes the query. For users (ordinary or even expert users) with less information of graph structures, setting an suitable cohesiveness parameter is difficult. Even with a large cohesiveness parameter, the resulting size of community size is often too large. Compared with the whole community, key-members are more valuable than others in practice. Therefore, our research focuses on a new problem Community Key-members Search (CKS), shifting our interest to identify key-members from a community, rather than the community as a whole. To address CKS, we first develop an exact method grounded in truss decomposition as a benchmark. Then, we propose four algorithms leveraging random walks to balance efficiency and effectiveness, by using three cohesiveness features for designing an appropriate transition matrix. The key-members are determined based on the stationary distribution. We conduct a theoretical analysis on the rationality of the design of cohesiveness-aware transition matrix, utilizing Bayesian theory, Box-Cox transformation, and Copula function. Furthermore, we design an efficient refinement method to optimize the community key-members with very limited overhead. Then, we adopt it to CKS with multiple query nodes. Experimental studies across real-world datasets demonstrate the superiority of our method, which makes the query algorithm speed up by 512× on average and the highest accuracy reachs 99.3%.