Bayesian clustering of huge friendship networks

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Helsinki University of Technology | Diplomityö
Date
2007
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, Samuel
Thesis advisor
Sinkkonen, Janne
Keywords
clustering, klusterointi, friendship network, ystävyysverkko, Bayesian inference, bayesilainen päättely, latent variable model, latenttimuuttujamalli
Citation