The spanning tree based approach for solving the shortest path problem in social graphs - Eremeev, Andrei (2016)
This thesis is devoted to the shortest path problem in social graphs. Social graphs represent individuals and social relationships between them. As for social networking sites, their users are represented as vertices of the social graph, and the relationship which indicates whether two users are friends in the social networking site are represented as edges of the social graph. Therefore, social graphs are widely investigated by sociologists in order to determine rules and properties of various social processes. Analysis of such social graphs may be used in prediction of results of election, or recommendation systems. Calculation of many social graph metrics requires computation of shortest paths between vertices of the social graph. Often, analysis of social graphs requires calculation of plenty of shortest paths, for instance, paths between each pair of vertices. Searching of plenty of shortest paths is needed in calculation of betweenness centrality of a vertex. The goal of the Master’s thesis is to synthesis an efficient shortest path searching algorithm. First, characteristics of social graphs are reviewed; thereafter, existing shortest path searching algorithms are reviewed based on defined requirements. Then, an efficient algorithm which is based on the Atlas algorithm, one of the existing algorithms, is synthesized. The Master’s thesis also tells how to implement the algorithm in Java more efficiently. The developed algorithm is under deployment into the Odnoklassniki social networking site, a Russian social networking site, which contains 205 million of users and 44 million of visitors per day (the eight most visited site in Russia and former Soviet Republics). The proposed algorithm solves the shortest path problem in social graphs with acceptable performance (50 ms per query), memory usage (less than 15 GB of the primary memory) and applicable accuracy (more than 90%). Also, the algorithm supports dynamic social graphs.