Spektralni normalizirani rezovi u težinskim grafovima

diplomski rad

• Autor: Franjo Palajsa
• Mentor: Zlatko Drmač (mentor)
• Član povjerenstva: Zlatko Drmač (predsjednik povjerenstva)
• Član povjerenstva: Luka Grubišić (član povjerenstva)
• Član povjerenstva: Miljenko Marušić (član povjerenstva)
• Član povjerenstva: Nela Bosner (č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: 2017-11-29, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu dajemo detaljan opis metode particioniranja težinskog grafa primjenom kriterija spektralnog normaliziranog reza. Argumentiramo odabir takvog kriterija u kontekstu zahtjeva na dobro particioniranje. U teorijskom razvoju metode uglavnom se pozivamo na elementarne pojmove i rezultate iz spektralne teorije matrica. Prvo problem particioniranja oblikujemo kao optimizacijski problem koji potom relaksiramo. Rješenja relaksiranog optimizacijskog problema dana su ortogonalnim transformacijama prvih nekoliko svojstvenih vektora simetrične matrice. U drugom koraku nastojimo pronaći rješenje originalnog diskretnog problema koje je najbliže dobivenom skupu kontinuiranih rješenja. To ostvarujemo iterativnim postupkom u kojem naizmjenično primjenjujemo dvije procedure: metodom potiskivanja ne-maksimuma pronalazimo diskretno rješenje najbliže kontinuiranom, dok se kontinuirano rješenje koje je dobra aproksimacija diskretnog može dobiti rješavanjem ortogonalnog Prokrustovog problema. Možemo garantirati da je tako dobiveno rješenje skoro globalno-optimalno. U zadnjem poglavlju dajemo implementaciju metode koju potom testiramo i evaluiramo.

Sažetak (engleski)

In this thesis we give a detailed description of a weighted graph partitioning method using the spectral normalized cut criterion. We argue the choice of such a criterion in the context of good partitioning requirements. In the theoretical development of the method we mainly rely on elementary definitions and results from spectral theory. First we redefine the partitioning problem as an optimization problem that we then relax. The solutions to the relaxed optimization problem are given by orthogonal transformations of the first few eigenvectors of a symmetric matrix. In the next step we try to find a solution to the original discrete problem that is closest to the obtained set of continuous optima. We can achieve this in an iterative fashion by alternately applying two procedures: using non-maximum suppression we find the discrete solution closest to a continuous one, while the continuous optimum that is a good approximation of a discrete one can be obtained by solving the orthogonal Procrustes problem. We can guarantee that the obtained solution is nearly global-optimal. In the last chapter we implement the method which we then test and evaluate.

• Ključne riječi: težinski graf; spektralni normalizirani rez; Prokrustov problem
• Ključne riječi (engleski): weighted graph; spectral normalized cut; Procrustes problem
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:351592
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2018-06-29 10:37:30