| fullrecord |
[{"key": "dc.contributor.advisor", "value": "Semenov, Alexander", "language": null, "element": "contributor", "qualifier": "advisor", "schema": "dc"}, {"key": "dc.contributor.advisor", "value": "Korneev, Georgiy", "language": null, "element": "contributor", "qualifier": "advisor", "schema": "dc"}, {"key": "dc.contributor.author", "value": "Eremeev, Andrei", "language": null, "element": "contributor", "qualifier": "author", "schema": "dc"}, {"key": "dc.date.accessioned", "value": "2016-03-27T21:48:05Z", "language": null, "element": "date", "qualifier": "accessioned", "schema": "dc"}, {"key": "dc.date.available", "value": "2016-03-27T21:48:05Z", "language": null, "element": "date", "qualifier": "available", "schema": "dc"}, {"key": "dc.date.issued", "value": "2016", "language": null, "element": "date", "qualifier": "issued", "schema": "dc"}, {"key": "dc.identifier.other", "value": "oai:jykdok.linneanet.fi:1525091", "language": null, "element": "identifier", "qualifier": "other", "schema": "dc"}, {"key": "dc.identifier.uri", "value": "https://jyx.jyu.fi/handle/123456789/49203", "language": null, "element": "identifier", "qualifier": "uri", "schema": "dc"}, {"key": "dc.description.abstract", "value": "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\u2019s 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\u2019s 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.", "language": "en", "element": "description", "qualifier": "abstract", "schema": "dc"}, {"key": "dc.description.abstract", "value": "T\u00e4m\u00e4 pro-gradu tutkielma k\u00e4sittelee lyhimm\u00e4n polun ongelmaa sosiaalisia\r\nverkostoja mallintavissa sosiaalisissa graafeissa. T\u00e4m\u00e4n ty\u00f6n kohteena ovat sosiaalisen\r\nmedian sivustot, joissa kullakin k\u00e4ytt\u00e4j\u00e4ll\u00e4 on profiili ja k\u00e4ytt\u00e4j\u00e4t voivat\r\nolla esimerkiksi toistensa yst\u00e4vi\u00e4. Sivustoa mallintavan sosiaalisen graafin\r\nsolmut mallintavat n\u00e4it\u00e4 profiileja ja suuntaamattomat kaaret profiilien v\u00e4lisi\u00e4\r\nyst\u00e4vyyssuhteita. Laajemmin t\u00e4llaisia graafeja k\u00e4ytet\u00e4\u00e4n esim. vaalien tulosten\r\nennustamiseen, tai suositteluj\u00e4rjestelmiss\u00e4 suositusten koostamiseen. Monet\r\nsosiaaliseen graafin ominaisuudet vaativat etsim\u00e4\u00e4n polkujoukkoja eri solmujen\r\nja solmuryhmien v\u00e4lill\u00e4. Sosiaalisen graafin analyysi vaatii usein laskemaan\r\npaljon lyhimpi\u00e4polkuja kahden solmun v\u00e4lill\u00e4. T\u00e4t\u00e4 tarvitaan esimerkiksi m\u00e4\u00e4-\r\nritett\u00e4ess\u00e4 solmun polkukeskeisyytt\u00e4. Ty\u00f6n keskeisen\u00e4 tavoitteena on kehitt\u00e4\u00e4\r\nlyhimm\u00e4n polun etsint\u00e4\u00e4n tehokas yhdistelm\u00e4algoritmi. Ty\u00f6ss\u00e4 esitell\u00e4\u00e4n ensin\r\nsosiaalisten graafien ominaisuuksia. T\u00e4m\u00e4n j\u00e4lkeen esitell\u00e4\u00e4n keskeiset tunnetut\r\nlyhint\u00e4 polkua etsiv\u00e4t algoritmit, jotka vastaavat luotua vaatimusm\u00e4\u00e4rittely\u00e4.\r\nTy\u00f6n tuloksena esitet\u00e4\u00e4n tehokas algoritmi, joka perustuu Atlas-algoritmiin ja\r\njoka kattaa my\u00f6s muiden esiteltyjen algoritmien toiminnallisuuden. Opinnn\u00e4yte\r\nkertoo my\u00f6s miten algoritmi toteutetaan Java-kielell\u00e4 tehokkaasti. Kehittetty\r\nalgoritmi on k\u00e4ytt\u00f6\u00f6nottovaihessa Odnoklassniki - nimisell\u00e4 sosiaalisen median\r\nsivustolla, jolla toimii ven\u00e4j\u00e4nkielinen verkkoyhteis\u00f6. Ko. sivustolla on kaikkiaan\r\n205 miljoonaa k\u00e4ytt\u00e4j\u00e4\u00e4 ja 44 miljoonaa k\u00e4vij\u00e4\u00e4 p\u00e4iv\u00e4ss\u00e4 (se on kahdeksanneksi\r\nsuosituin sivusto Ven\u00e4j\u00e4ll\u00e4 ja entisen Neuvostoliiton tasavalloissa).\r\nEhdotettu algoritmi ratkaisee lyhimm\u00e4n polun ongelman eo. sivustosta muodostetussa\r\nsosiaalisessa graafissa suorituskykyisesti vasteajan (50 ms per kysely),\r\nmuistin k\u00e4yt\u00f6n (alle 15 GBs ensisijaisen muistin) ja saavutetun tarkkuuden\r\n(yli 90%) suhteen. Algoritmi tukee my\u00f6s dynaamisia sosiaalisia graafeja.", "language": "fi", "element": "description", "qualifier": "abstract", "schema": "dc"}, {"key": "dc.description.provenance", "value": "Submitted using Plone Publishing form by Andrei Eremeev (aneremee) on 2016-03-27 21:48:04.127225. Form: Master's Thesis publishing form (https://kirjasto.jyu.fi/publish-and-buy/publishing-forms/masters-thesis-publishing-form). JyX data: [jyx_publishing-allowed (fi) =True]", "language": "en", "element": "description", "qualifier": "provenance", "schema": "dc"}, {"key": "dc.description.provenance", "value": "Submitted by jyx lomake-julkaisija (jyx-julkaisija.group@korppi.jyu.fi) on 2016-03-27T21:48:05Z\nNo. of bitstreams: 2\nURN:NBN:fi:jyu-201603281950.docx: 582291 bytes, checksum: c6c0d89b9ac080728480dbd152f0db24 (MD5)\nlicense.html: 4307 bytes, checksum: 09e9c4747504606af8c862ec2db55dff (MD5)", "language": "en", "element": "description", "qualifier": "provenance", "schema": "dc"}, {"key": "dc.description.provenance", "value": "Made available in DSpace on 2016-03-27T21:48:05Z (GMT). No. of bitstreams: 2\nURN:NBN:fi:jyu-201603281950.docx: 582291 bytes, checksum: c6c0d89b9ac080728480dbd152f0db24 (MD5)\nlicense.html: 4307 bytes, checksum: 09e9c4747504606af8c862ec2db55dff (MD5)\n Previous issue date: 2016", "language": "en", "element": "description", "qualifier": "provenance", "schema": "dc"}, {"key": "dc.format.extent", "value": "1 verkkoaineisto (70 s.)", "language": null, "element": "format", "qualifier": "extent", "schema": "dc"}, {"key": "dc.format.mimetype", "value": "application/pdf", "language": null, "element": "format", "qualifier": "mimetype", "schema": "dc"}, {"key": "dc.language.iso", "value": "eng", "language": null, "element": "language", "qualifier": "iso", "schema": "dc"}, {"key": "dc.rights", "value": "In Copyright", "language": "en", "element": "rights", "qualifier": null, "schema": "dc"}, {"key": "dc.subject.other", "value": "social graph", "language": null, "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "social network analysis", "language": null, "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "shortest path problem", "language": null, "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "Odnoklassniki", "language": null, "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "the Atlas algorithm", "language": null, "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.title", "value": "The spanning tree based approach for solving the shortest path problem in social graphs", "language": null, "element": "title", "qualifier": null, "schema": "dc"}, {"key": "dc.type", "value": "master thesis", "language": null, "element": "type", "qualifier": null, "schema": "dc"}, {"key": "dc.identifier.urn", "value": "URN:NBN:fi:jyu-201603281950", "language": null, "element": "identifier", "qualifier": "urn", "schema": "dc"}, {"key": "dc.type.ontasot", "value": "Pro gradu -tutkielma", "language": "fi", "element": "type", "qualifier": "ontasot", "schema": "dc"}, {"key": "dc.type.ontasot", "value": "Master\u2019s thesis", "language": "en", "element": "type", "qualifier": "ontasot", "schema": "dc"}, {"key": "dc.contributor.faculty", "value": "Informaatioteknologian tiedekunta", "language": "fi", "element": "contributor", "qualifier": "faculty", "schema": "dc"}, {"key": "dc.contributor.faculty", "value": "Faculty of Information Technology", "language": "en", "element": "contributor", "qualifier": "faculty", "schema": "dc"}, {"key": "dc.contributor.department", "value": "Tietojenk\u00e4sittelytieteiden laitos", "language": "fi", "element": "contributor", "qualifier": "department", "schema": "dc"}, {"key": "dc.contributor.department", "value": "Department of Computer Science and Information Systems", "language": "en", "element": "contributor", "qualifier": "department", "schema": "dc"}, {"key": "dc.contributor.organization", "value": "University of Jyv\u00e4skyl\u00e4", "language": "en", "element": "contributor", "qualifier": "organization", "schema": "dc"}, {"key": "dc.contributor.organization", "value": "Jyv\u00e4skyl\u00e4n yliopisto", "language": "fi", "element": "contributor", "qualifier": "organization", "schema": "dc"}, {"key": "dc.subject.discipline", "value": "Ohjelmistotuotanto", "language": "fi", "element": "subject", "qualifier": "discipline", "schema": "dc"}, {"key": "dc.date.updated", "value": "2016-03-27T21:48:05Z", "language": null, "element": "date", "qualifier": "updated", "schema": "dc"}, {"key": "yvv.contractresearch.funding", "value": "0", "language": null, "element": "contractresearch", "qualifier": "funding", "schema": "yvv"}, {"key": "dc.type.coar", "value": "http://purl.org/coar/resource_type/c_bdcc", "language": null, "element": "type", "qualifier": "coar", "schema": "dc"}, {"key": "dc.rights.accesslevel", "value": "openAccess", "language": "fi", "element": "rights", "qualifier": "accesslevel", "schema": "dc"}, {"key": "dc.type.publication", "value": "masterThesis", "language": null, "element": "type", "qualifier": "publication", "schema": "dc"}, {"key": "dc.subject.oppiainekoodi", "value": "601", "language": null, "element": "subject", "qualifier": "oppiainekoodi", "schema": "dc"}, {"key": "dc.subject.yso", "value": "graafit", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "algoritmit", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "sosiaaliset verkostot", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "sosiaalinen media", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.format.content", "value": "fulltext", "language": null, "element": "format", "qualifier": "content", "schema": "dc"}, {"key": "dc.rights.url", "value": "https://rightsstatements.org/page/InC/1.0/", "language": null, "element": "rights", "qualifier": "url", "schema": "dc"}, {"key": "dc.type.okm", "value": "G2", "language": null, "element": "type", "qualifier": "okm", "schema": "dc"}]
|