Spektralni normalizirani rezovi u težinskim grafovima

master's thesis

• Author: Franjo Palajsa
• Mentor: Zlatko Drmač (mentor)
• Committee member: Zlatko Drmač (predsjednik povjerenstva)
• Committee member: Luka Grubišić (član povjerenstva)
• Committee member: Miljenko Marušić (član povjerenstva)
• Committee member: Nela Bosner (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2017-11-29, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: težinski graf; spektralni normalizirani rez; Prokrustov problem
• Keywords (english): weighted graph; spectral normalized cut; Procrustes problem
• Language: croatian
• URN:NBN: urn:nbn:hr:217:351592
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2018-06-29 10:37:30