Bayesian clustering of huge friendship networks

Loading...
Thumbnail Image

URL

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

Other note

Citation