Memory-Efficient Fast Shortest Path Estimation in Large Social Networks

Abstract

As the sizes of contemporary social networks surpass billions of users, so grows the need for fast graph algorithms to analyze them. A particularly important basic operation is the computation of shortest paths between nodes. Classical exact algorithms for this problem are prohibitively slow on large graphs, which motivates the development of approximate methods. Of those, landmark-based methods have been actively studied in recent years. Landmark-based estimation methods start by picking a fixed set of landmark nodes, precomputing the distance from each node in the graph to each landmark, and storing the precomputed distances in a data structure. Prior work has shown that the number of landmarks required to achieve a given level of precision grows with the size of the graph. Simultaneously, the size of the data structure is proportional to the product of the size of the graph and the number of landmarks. In this work we propose an alternative landmark-based distance estimation approach that substantially reduces space requirements by means of pruning: computing distances from each node to only a small subset of the closest landmarks. We evaluate our method on the DBLP, Orkut, Twitter and Skype social networks and demonstrate that the resulting estimation algorithms are comparable in query time and potentially superior in approximation quality to equivalent non-pruned landmark-based methods, while requiring less memory or disk space.