Spektralni rezovi u usmjerenim grafovima

diplomski rad

• Naslov (engleski): Spectral cuts in directed graphs
• Autor: Andrej Slapničar
• Mentor: Zlatko Drmač (mentor)
• Član povjerenstva: Nela Bosner (predsjednik povjerenstva)
• Član povjerenstva: Igor Ciganović (član povjerenstva)
• Član povjerenstva: Vjekoslav Kovač (član povjerenstva)
• Član povjerenstva: Nikola Sandrić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2023-09-27, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu opisane su metode spektralnog klasteriranja podataka koji su reprezentirani težinskim grafom. Metode spektralnog klasteriranja traže particiju koja ima najmanji spektralni rez koji mjeri koliko su dobro podaci podijeljeni u grupe za neku particiju. Predstavljene su tri metode spektralnog klasteriranja koje su dobivene postepenom generalizacijom, metoda minimizacije spektralnog normaliziranog reza biparticije u neusmjerenom grafu, metoda minimizacije spektralnog normaliziranog reza višečlane particije u neusmjerenom grafu i metoda minimizacije spektralnog težinskog reza višečlane particije u usmjerenom grafu. Sve tri metode minimizacije spektralnih rezova su izvedene na sličan način. Prvo problem minimizacije spektralnog reza zapisujemo matrično te relaksiramo diskretni problem minimizacije kako bismo ga sveli na problem minimizacije Rayleighovih kvocijenata čime dobijemo rješenje relaksiranog kontinuiranog problema minimizacije spektralnog reza. Zatim pronalazimo približno rješenje početnog diskretnog problema minimizacije tako da klasteriramo redove u matrici relaksiranog rješenja kao točke u \( \R^k \) koristeći algoritam \( k \)-sredina. U zadnjem poglavlju je navedena implementacija algoritama za ove metode te su dani primjeri na kojima su ti algoritmi testirani.

Sažetak (engleski)

In this paper, we give a description of spectral clustering methods where data is represented by a weighted graph. In spectral clustering, the goal is to find the partition that has the smallest spectral cut, which is a measurement of how well the data are divided into groups for some partition. Three spectral clustering methods obtained by gradual generalization are presented, the method of minimizing the spectral normalized cut of a bipartition in an undirected graph, the method of minimizing the spectral normalized cut of a partition in an undirected graph, and the method of minimizing the spectral weighted cut of a partition in a directed graph. All three methods of minimizing spectral cuts are derived similarly. First, we represent the minimization problem of a spectral cut in matrix form and relax that discrete minimization problem in order to reduce it to the problem of Rayleigh quotients minimization, which gives us the solution to the relaxed continuous minimization problem of a spectral cut. We then find an approximate solution to the initial discrete minimization problem by clustering the rows in the relaxed solution matrix as points in \( \R^k \) using the \( k \)-means algorithm. In the last chapter, the implementation of algorithms for these methods is given, and examples are shown on which these algorithms were tested.

• Ključne riječi: težinski graf; Rayleighovi kvocijenti; najmanji spektralni rez
• Ključne riječi (engleski): weighted graph; Rayleigh quotients; minimizing spectral cuts
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:047483
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: sveučilišni magistar računarstva i matematike (univ. mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-02-05 13:46:28