0000000000241483
AUTHOR
Andrei Eremeev
The Spanning Tree based Approach for Solving the Shortest Path Problem in Social Graphs
Nowadays there are many social media sites with a very large number of users. Users of social media sites and relationships between them can be modelled as a graph. Such graphs can be analysed using methods from social network analysis (SNA). Many measures used in SNA rely on computation of shortest paths between nodes of a graph. There are many shortest path algorithms, but the majority of them suits only for small graphs, or work only with road network graphs that are fundamentally different from social graphs. This paper describes an efficient shortest path searching algorithm suitable for large social graphs. The described algorithm extends the Atlas algorithm. The proposed algorithm so…
The spanning tree based approach for solving the shortest path problem in social graphs
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…