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

Lixin Fu, Jing Deng

2015

Abstract

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.

Paper Citation

in Harvard Style

Fu L. and Deng J. (2015). ROBE - Knitting a Tight Hub for Shortest Path Discovery in Large Social Graphs . In Proceedings of the 17th International Conference on Enterprise Information Systems - Volume 1: ICEIS, ISBN 978-989-758-096-3, pages 97-107. DOI: 10.5220/0005353500970107

in Bibtex Style

@conference{iceis15,
author={Lixin Fu and Jing Deng},
title={ROBE - Knitting a Tight Hub for Shortest Path Discovery in Large Social Graphs},
booktitle={Proceedings of the 17th International Conference on Enterprise Information Systems - Volume 1: ICEIS,},
year={2015},
pages={97-107},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005353500970107},
isbn={978-989-758-096-3},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 17th International Conference on Enterprise Information Systems - Volume 1: ICEIS,
TI - ROBE - Knitting a Tight Hub for Shortest Path Discovery in Large Social Graphs
SN - 978-989-758-096-3
AU - Fu L.
AU - Deng J.
PY - 2015
SP - 97
EP - 107
DO - 10.5220/0005353500970107