Knitting a Tight Hub for Shortest Path Discovery in Large Social Graphs

摘要

Scalable and efficient algorithms are needed to compute shortest paths between any pair of vertices in large social graphs. In this work, we propose a novel ROBE scheme to estimate the shortest distances. ROBE is based on a hub serving as the skeleton of the large graph. In order to stretch the hub into every corner in the network, we first choose representative nodes with highest degrees that are at least two hops away from each other. Then bridge nodes are selected to connect the representative nodes. Extension nodes are also added to the hub to ensure that the originally connected parts in the large graph are not separated in the hub graph. To improve performance, we compress the hub through chain collapsing, tentacle retracting, and clique compression techniques. A query evaluation algorithm based on the compressed hub is given. We compare our approach with other state-of-the-art techniques and evaluate their performance with respect to miss rate, error rate, as well as construction time through extensive simulations. ROBE is demonstrated to be two orders faster and has more accurate estimations than two recent algorithms, allowing it to scale very well in large social graphs.