More Accurate Estimation of Shortest Paths in Social Networks

The shortest distance query between two given nodes is a fundamental but critical operation over social networks. Due to the computational efficiency of accurate methods is too low to be adopted for large-scale networks, recent researches about the shortest distance estimation mainly focus on approximate methods, in particular using landmark-based indexing strategy. A proper balance between computation rate and precision is greatly needed as the error of conventional landmark-based strategy is intolerable. In this paper, we analyze the deficiency in existing landmark embedding approaches. This paper mainly presents Local Subgraph Query (LSQ) algorithm for calculating the shortest path by dint of landmark embedding information. Besides, we propose an improved version of LSQ, termed Batch Subgraph Query (BSQ) algorithm, by aggregating landmarks and query nodes to raise accuracy. Experimental results on real-world datasets show that our methods outperform most of the state-of-the-art algorithms with significant estimation error decrease and few time penalty increases in social networks.