Bayesian clustering of huge friendship networks
Loading...
Journal Title
Journal ISSN
Volume Title
Helsinki University of Technology |
Diplomityö
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2007
Department
Major/Subject
Informaatiotekniikka
Mcode
T-61
Degree programme
Language
en
Pages
88 + (viii)
Series
Abstract
Sosiaalisten verkkopalveluiden, joita ovat esimerkiksi MySpace, Facebook ja Last.fm, viimeaikaisen suosion kasvun myötä kiinnostus erittäin suurten ystävyysverkostojen analysointiin on kasvanut. Näissä verkoissa on jopa miljoonia solmuja, joten ne tarjoavat hyvän testiympäristön uusille verkkoalgoritmeille. Verkkojen analysointimenetelmiä voidaan hyödyntää myös muihin kuin sosiaalisiin verkkoihin, kuten proteiinien välisiin vuorovaikutusverkkoihin ja verkkosivujen välisiin linkkeihin. Sosiaalisilla verkostoilla on tyypillisesti rakenne: niissä on tiheitä solmuryhmittymiä, ja joillakin solmuilla on suhteettoman paljon yhteyksiä. Rakenne syntyy, koska ystävyydet eivät muodostu satunnaisesti. Ihmiset sen sijaan tapaavat ystävystyi samanlaisten ihmisten kanssa. Tätä voi kutsua homofiliaksi. Ystävyyksien syntyyn vaikuttavat myös muut tekijät kuten maantieteellinen sijainti ja yhteisiin aktiviteetteihin osallistuminen. M0-algoritmi löytää klusterirakenteen homofiilisistä verkoista bayesilaisen tilastollisen inferenssin avulla. Algoritmi pohjautuu generatiiviseen malliin, jossa verkon sivut luodaan latenttien komponenttien perusteella. Mallin parametrien tilastollisessa päättelyssä käytetään Gibbs-otantaa. Homofilian vuoksi samaan klusteriin kuuluvilla solmuilla on todennäköisesti yhteisiä piirteitä. Tässä diplomityössä esitetään MO-algoritmille tehokas toteutus, joka käyttää tasapainotettua binääripuuta komponenttien todennäköisyyksien tallennukseen. Toteutus toimii jopa miljoonien solmujen verkoilla. Algoritmia testataan joukolla aiemmin tutkittuja pieniä verkkoja ja Last.fm-palvelusta kerätyllä ystävyysverkolla, jossa on yli 600 000 käyttäjää. Algoritmi löytää merkityksellisiä rakenteita monenkokoisista verkoista, ja tulokset ovat vertailukelpoisia hierarkisilla klusterointimenetelmillä saatujen tulosten kanssa. Menetelmän vahvuus on solmujen sumea klusterointi, jossa solmu voi kuulua samanaikaisesti useaan klusteriin. Hyperparametrien valinta on kuitenkin usein hankalaa.Description
Supervisor
Kaski, SamuelThesis advisor
Sinkkonen, JanneKeywords
clustering, klusterointi, friendship network, ystävyysverkko, Bayesian inference, bayesilainen päättely, latent variable model, latenttimuuttujamalli
