The spanning tree based approach for solving the shortest path problem in social graphs

Abstract

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.

Tämä pro-gradu tutkielma käsittelee lyhimmän polun ongelmaa sosiaalisia verkostoja mallintavissa sosiaalisissa graafeissa. Tämän työn kohteena ovat sosiaalisen median sivustot, joissa kullakin käyttäjällä on profiili ja käyttäjät voivat olla esimerkiksi toistensa ystäviä. Sivustoa mallintavan sosiaalisen graafin solmut mallintavat näitä profiileja ja suuntaamattomat kaaret profiilien välisiä ystävyyssuhteita. Laajemmin tällaisia graafeja käytetään esim. vaalien tulosten ennustamiseen, tai suosittelujärjestelmissä suositusten koostamiseen. Monet sosiaaliseen graafin ominaisuudet vaativat etsimään polkujoukkoja eri solmujen ja solmuryhmien välillä. Sosiaalisen graafin analyysi vaatii usein laskemaan paljon lyhimpiäpolkuja kahden solmun välillä. Tätä tarvitaan esimerkiksi mää- ritettäessä solmun polkukeskeisyyttä. Työn keskeisenä tavoitteena on kehittää lyhimmän polun etsintään tehokas yhdistelmäalgoritmi. Työssä esitellään ensin sosiaalisten graafien ominaisuuksia. Tämän jälkeen esitellään keskeiset tunnetut lyhintä polkua etsivät algoritmit, jotka vastaavat luotua vaatimusmäärittelyä. Työn tuloksena esitetään tehokas algoritmi, joka perustuu Atlas-algoritmiin ja joka kattaa myös muiden esiteltyjen algoritmien toiminnallisuuden. Opinnnäyte kertoo myös miten algoritmi toteutetaan Java-kielellä tehokkaasti. Kehittetty algoritmi on käyttöönottovaihessa Odnoklassniki - nimisellä sosiaalisen median sivustolla, jolla toimii venäjänkielinen verkkoyhteisö. Ko. sivustolla on kaikkiaan 205 miljoonaa käyttäjää ja 44 miljoonaa kävijää päivässä (se on kahdeksanneksi suosituin sivusto Venäjällä ja entisen Neuvostoliiton tasavalloissa). Ehdotettu algoritmi ratkaisee lyhimmän polun ongelman eo. sivustosta muodostetussa sosiaalisessa graafissa suorituskykyisesti vasteajan (50 ms per kysely), muistin käytön (alle 15 GBs ensisijaisen muistin) ja saavutetun tarkkuuden (yli 90%) suhteen. Algoritmi tukee myös dynaamisia sosiaalisia graafeja.