The Spanning Tree based Approach for Solving the Shortest Path Problem in Social Graphs

Andrei Eremeev, Georgiy Korneev, Alexander Semenov, Jari Veijalainen

2016

Abstract

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).

Paper Citation

in Harvard Style

Eremeev A., Korneev G., Semenov A. and Veijalainen J. (2016). The Spanning Tree based Approach for Solving the Shortest Path Problem in Social Graphs . In Proceedings of the 12th International Conference on Web Information Systems and Technologies - Volume 1: WEBIST, ISBN 978-989-758-186-1, pages 42-53. DOI: 10.5220/0005859400420053

in Bibtex Style

@conference{webist16,
author={Andrei Eremeev and Georgiy Korneev and Alexander Semenov and Jari Veijalainen},
title={The Spanning Tree based Approach for Solving the Shortest Path Problem in Social Graphs},
booktitle={Proceedings of the 12th International Conference on Web Information Systems and Technologies - Volume 1: WEBIST,},
year={2016},
pages={42-53},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005859400420053},
isbn={978-989-758-186-1},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 12th International Conference on Web Information Systems and Technologies - Volume 1: WEBIST,
TI - The Spanning Tree based Approach for Solving the Shortest Path Problem in Social Graphs
SN - 978-989-758-186-1
AU - Eremeev A.
AU - Korneev G.
AU - Semenov A.
AU - Veijalainen J.
PY - 2016
SP - 42
EP - 53
DO - 10.5220/0005859400420053