6533b7d4fe1ef96bd12632c6
RESEARCH PRODUCT
The Spanning Tree based Approach for Solving the Shortest Path Problem in Social Graphs
Alexander SemenovJari VeijalainenGeorgiy KorneevAndrei Eremeevsubject
Discrete mathematicsta113Mathematical optimizationSpanning treesocial network analysisComputer scienceAtlas algorithm020206 networking & telecommunications02 engineering and technologyLongest path problemverkostoanalyysiWidest path problemOdnoklassnikiEuclidean shortest pathShortest Path Faster Algorithmsocial graph020204 information systemsShortest path problem0202 electrical engineering electronic engineering information engineeringK shortest path routingCanadian traveller problemshortest path problemMathematicsofComputing_DISCRETEMATHEMATICSdescription
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 solves the shortest path problem in social graphs modelling sites with over 100 million users with acceptable response time (50 ms per query), memory usage (less than 15 GB of the primary memory) and applicable accuracy (higher than 90% of the queries return exact result). peerReviewed
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2016-01-01 |