dc.contributor.author | Eremeev, Andrei | |
dc.contributor.author | Korneev, Georgiy | |
dc.contributor.author | Semenov, Alexander | |
dc.contributor.author | Veijalainen, Jari | |
dc.contributor.editor | Majchrzak, Tim A. | |
dc.contributor.editor | Traverso, Paolo | |
dc.contributor.editor | Monfort, Valérie | |
dc.contributor.editor | Krempels, Karl-Heinz | |
dc.date.accessioned | 2016-05-13T06:26:54Z | |
dc.date.available | 2016-05-13T06:26:54Z | |
dc.date.issued | 2016 | |
dc.identifier.citation | Eremeev, A., Korneev, G., Semenov, A., & Veijalainen, J. (2016). The Spanning Tree based Approach for Solving the Shortest Path Problem in Social Graphs. In T. A. Majchrzak, P. Traverso, V. Monfort, & K.-H. Krempels (Eds.), <i>WEBIST 2016 : Proceedings of the 12th International conference on web information systems and technologies. Volume 1</i> (pp. 42-53). SCITEPRESS. <a href="https://doi.org/10.5220/0005859400420053" target="_blank">https://doi.org/10.5220/0005859400420053</a> | |
dc.identifier.other | CONVID_25703519 | |
dc.identifier.other | TUTKAID_70017 | |
dc.identifier.uri | https://jyx.jyu.fi/handle/123456789/49765 | |
dc.description.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). | |
dc.language.iso | eng | |
dc.publisher | SCITEPRESS | |
dc.relation.ispartof | WEBIST 2016 : Proceedings of the 12th International conference on web information systems and technologies. Volume 1 | |
dc.subject.other | social graph | |
dc.subject.other | shortest path problem | |
dc.subject.other | Odnoklassniki | |
dc.subject.other | Atlas algorithm | |
dc.title | The Spanning Tree based Approach for Solving the Shortest Path Problem in Social Graphs | |
dc.type | conferenceObject | |
dc.identifier.urn | URN:NBN:fi:jyu-201605122519 | |
dc.contributor.laitos | Tietojenkäsittelytieteiden laitos | fi |
dc.contributor.laitos | Department of Computer Science and Information Systems | en |
dc.contributor.oppiaine | Tietojärjestelmätiede | fi |
dc.contributor.oppiaine | Information Systems Science | en |
dc.type.uri | http://purl.org/eprint/type/ConferencePaper | |
dc.date.updated | 2016-05-12T12:15:11Z | |
dc.relation.isbn | 978-989-758-186-1 | |
dc.type.coar | http://purl.org/coar/resource_type/c_5794 | |
dc.description.reviewstatus | peerReviewed | |
dc.format.pagerange | 42-53 | |
dc.type.version | acceptedVersion | |
dc.rights.copyright | © INSTICC, 2016. This is an author's final draft version of an article whose final and definitive form has been published in the WEBIST Proceedings. Published by SCITEPRESS. | |
dc.rights.accesslevel | openAccess | fi |
dc.relation.conference | International conference on web information systems and technologies | |
dc.subject.yso | verkostoanalyysi | |
jyx.subject.uri | http://www.yso.fi/onto/yso/p26690 | |
dc.relation.doi | 10.5220/0005859400420053 | |
dc.type.okm | A4 | |