Graph Calculus: Scalable Shortest Path Analytics for Large Social Graphs through Core Net

We focus on the problem of scalable shortest path analytics for large social graphs in this paper. While shortest path distance problem has been investigated extensively, massive graphs on social networks such as Facebook and Linked In call for reinvestigation of the problem due to the requirements of scalability and suitability for distributed computing. We propose a core-net based approach to address the problem. In our new core-net algorithm, popular nodes are selected based on their node degrees. Since some of these popular nodes may not be connected, we further include bridge nodes, which connect two or more popular nodes and improve their connectivity, but are not popular nodes themselves. Breadth First Search (BFS) technique is then used to compute shortest paths between any pair of nodes on the core net. When the shortest path between two arbitrary vertices, u and v, is queried, we approximate it with triangulation. We present a graph calculus theory in which the estimated distance goes to the real shortest distance when the degree threshold goes to zero. Analysis and simulation results confirm the superiority of our design, which can easily scale to MapReduce.