Naslov
Spektralno particioniranje grafa i primjena na ekstrakciju znanja
(Spectral partitioning of graph and application to extraction of knowledge)

Autori
Mirošević, Ivančica

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, magistarski rad

Fakultet
Prirodoslovno-matematički fakultet, Matematički odjel

Mjesto
Zagreb

Datum
14.07

Godina
2005

Stranica
145

Mentor
Slapničar, Ivan

Ključne riječi
Laplceova matrica grafa; razmjerni rez; normalizirani rez; k-mean algoritam; Ky-Fanov teorem; spektralno particioniranje; Fiedlerov vektor
(Laplacoian matrix; proportional cut; normalised cut; k-means algorithm; Ky-Fan theorem; spectral partitioning; Fiedler vector)

Sažetak
Važna primjena particioniranja grafa je razvrstavanje podataka u skupine uporabom modela grafa. Sličnosti među parovima podataka definiraju matricu susjedstva težinskog grafa koja sadrži sve informacije potrebne za razvrstavanje podataka. U ovom radu formuliran je diskretni optimalizacijski problem particioniranja grafa, čija relaksirana verzija upućuje na svojstvene vektore Laplaceove matrice grafa. Definirane su dvije varijante ciljne funkcije, razmjerni i normalizirani rez, i to najprije za problem biparticioniranja grafa, a zatim i za opći problem k-particioniranja grafa. Na početku rada objašnjen je klasični algoritam k-sredina za particioniranje skupa točaka zadanih u Euklidskom prostoru Rn, poboljšan algoritmom prve varijacije. Za slučaj problema biparticioniranja grafa naveden je dokaz da je rješenje relaksiranog problema minimaliziranja ciljnih funkcija dano Fiedlerovim vektorom nenormalizirane i normalizirane Laplaceove matrice grafa (svojstvenim vektorom pridruženim drugoj najmanjoj svojstvenoj vrijednosti). Prema Ky Fanovom teoremu rješenje relaksiranog problema k-particioniranja grafa dano je matricom svojstvenih vektora pridruženih najmanjim svojstvenim vrijednostima. Grupiranjem redaka matrice svojstvenih vektora u k skupina, obično algoritmom k-sredina, istovremeno se grupiraju i podaci. Budući da je u slučaju nepovezanog grafa s k komponenti povezanosti particija jednoznačno određena s k linearno nezavisnih svojstvenih vektora pridruženih svojstvenoj vrijednosti 0, navedeno je nekoliko rezultata iz teorije matričnih perturbacija koji podupiru ideju o particioniranju povezanog grafa na osnovi svojstvenih vektora pridruženih svojstvenim vrijednostima Laplaceove matrice koje su blizu nuli. Na kraju rada ponuđena je ideja modeliranja kolekcije dokumenata kao bipartitnog grafa izmedu dokumenata i riječi, uz pomoć kojeg se problem istovremenog particioniranja dokumenata i riječi može shvatiti kao problem particioniranja bipartitnog grafa. U tom slučaju je za rekonstrukciju particije na osnovi minizacije normaliziranog reza dovoljno računati singularne vektore riječi-dokumenti matrice, koja je bitno manjih dimenzija od cijele matrice susjedstva grafa. Na primjerima je prikazano funkcioniranje spektralnih algoritama. Pri particioniranju bipartitnog grafa korišteni su testni podaci s interneta, te elektronički udžbenik Matematika 1 prof. Ivana Slapničara.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika

POVEZANOST RADA