Show simple item record

dc.contributor.advisorSemenov, Alexander
dc.contributor.advisorKorneev, Georgiy
dc.contributor.authorEremeev, Andrei
dc.date.accessioned2016-03-27T21:48:05Z
dc.date.available2016-03-27T21:48:05Z
dc.date.issued2016
dc.identifier.otheroai:jykdok.linneanet.fi:1525091
dc.identifier.urihttps://jyx.jyu.fi/handle/123456789/49203
dc.description.abstractThis 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.en
dc.description.abstractTä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.fi
dc.format.extent1 verkkoaineisto (70 s.)
dc.language.isoeng
dc.rightsJulkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.fi
dc.rightsThis publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.en
dc.subject.othersocial graph
dc.subject.othersocial network analysis
dc.subject.othershortest path problem
dc.subject.otherOdnoklassniki
dc.subject.otherthe Atlas algorithm
dc.titleThe spanning tree based approach for solving the shortest path problem in social graphs
dc.identifier.urnURN:NBN:fi:jyu-201603281950
dc.type.ontasotPro gradufi
dc.type.ontasotMaster's thesisen
dc.contributor.tiedekuntaInformaatioteknologian tiedekuntafi
dc.contributor.tiedekuntaFaculty of Information Technologyen
dc.contributor.laitosTietojenkäsittelytieteiden laitosfi
dc.contributor.laitosDepartment of Computer Science and Information Systemsen
dc.contributor.yliopistoUniversity of Jyväskyläen
dc.contributor.yliopistoJyväskylän yliopistofi
dc.contributor.oppiaineOhjelmistotuotantofi
dc.date.updated2016-03-27T21:48:05Z
dc.rights.accesslevelopenAccessfi
dc.contributor.oppiainekoodi601
dc.subject.ysograafit
dc.subject.ysoalgoritmit
dc.subject.ysososiaaliset verkostot
dc.subject.ysososiaalinen media


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record