Shortest path tree sampling for landmark selection in large networks

Shlomi Maliah, Rami Puzis, Guy Shani

Journal of Complex Networks 5 (5), 795-815, 2017

Computing the distance between vertices in a large dynamic network is an important task in many real-time applications. An exact real-time computation is often infeasible, due to the network size, dynamic changes and the requirement for rapid response. We hence revert to estimates. One popular method for distance estimation uses a set of vertices, called landmarks, whose distance from all other vertices is computed offline. Then, the online query estimates the distance between two arbitrary vertices by summing the computed distances from the source to a landmark and from the landmark to the target. In this paper we suggest a new method for computing the set of landmarks, based on a sampled set of shortest path trees (SPTs). The SPTs provide a good estimation of the number of shortest paths that a vertex covers, which is strongly correlated with distance estimation error. We provide an extensive set of …