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%.

Event temporal relation extraction is an important part of natural language processing. Many models are being used in this task with the development of deep learning. However, most of the existing methods cannot accurately obtain the degree of association between different tokens and events, and event-related information cannot be effectively integrated. In this paper, we propose an event information integration model that integrates event information through multilayer bidirectional long short-term memory (Bi-LSTM) and attention mechanism. Although the above scheme can improve the extraction performance, it can still be further optimized. To further improve the performance of the previous scheme, we propose a novel relational graph attention network that incorporates edge attributes. In this approach, we first build a semantic dependency graph through dependency parsing, model a semantic graph that considers the edges’ attributes by using top-k attention mechanisms to learn hidden semantic contextual representations, and finally predict event temporal relations. We evaluate proposed models on the TimeBank-Dense dataset. Compared to previous baselines, the Micro-F1 scores obtained by our models improve by 3.9% and 14.5%, respectively.