Orion: Shortest Path Estimation for Large Social Graphs

Xiaohan Zhao

Alessandra Sala

Christo Wilson

Haitao Zheng

Ben Y. Zhao

*
Proceedings of the Third USENIX Workshop on Online Social Networks (WOSN)*

Paper Abstract

Through measurements, researchers continue to produce large social graphs that capture relationships, transactions, and social interactions between users. Efficient analysis of these graphs requires algorithms that scale well with graph size. We examine node distance computation, a critical primitive in graph problems such as computing node separation, centrality computation, mutual friend detection, and community detection. For large million-node social graphs, computing even a single shortest path using traditional breadth-first-search can take several seconds.

In this paper, we propose a novel node distance estimation mechanism that
effectively maps nodes in high dimensional graphs to positions in
low-dimension Euclidean coordinate spaces, thus allowing constant time node
distance computation. We describe Orion, a prototype *graph coordinate
system*, and explore critical decisions in its design. Finally, we
evaluate the accuracy of Orion's node distance estimates, and show that it
can produce accurate results in applications such as node
separation, node centrality, and ranked social search.