Klusterointi harvoissa graafeissa

Abstract

Tutkielmassa esitellään graafin solmujen klusterointiongelma, tarkastellaan sitä erityisesti harvoissa graafeissa ja ratkaistaan se hajautetun laskennan mallissa.

Lähdetään ensin liikkeelle määrittelemällä graafin metsäisyys ja mitä harvalla graafilla tarkoitetaan. Ensimmäisessä luvussa myös tutustutaan riippumattomiin joukkoihin. Lopuksi esitellään tiukka yläraja maksimaalisen riippumattoman joukon laskevan ahneen algoritmin suoritusajalle, kun algoritmia ajetaan rinnakkaisesti.

Toisessa luvussa määritellään hajautetun laskennan mallit LOCAL ja MPC (Massively Parallel Computation), joista jälkimmäistä on tutkittu laajalti 2010-luvulla. MPC-mallissa on käytössä tekniikat graafin eksponentiaatio ja kierrosten tiivistäminen, joiden avulla voidaan simuloida LOCAL-algoritmeja tehokkaasti.

Luvussa 3 perehdytään korrelaatioklusterointiin. Esitellään ongelman ratkaiseva yksinkertainen algoritmi ja todistetaan, että se on 3-approksimaatio. Sitten pohditaan, miten algoritmi voidaan toteuttaa rinnakkaistetusti. Lopuksi osoitetaan muutamia ominaisuuksia, joita pienen metsäisyyden graafeilla on mitä korrelaatioklusterointiin tulee ja hyödynnetään niitä algoritmien suunnittelussa.

Neljännessä luvussa esitellään tutkielman päätulos, MPC-algoritmi korrelaatioklusteroinnille, joka on eksponentiaalisesti nopeampi kuin aiempi nopein tunnettu algoritmi. Sen toteutuksessa hyödynnetään luvun 2 tekniikoita ja luvun 1 tulosta maksimaalisista riippumattomista joukoista.