Spektralni rezovi u usmjerenim grafovima

master's thesis

• Title (english): Spectral cuts in directed graphs
• Author: Andrej Slapničar
• Mentor: Zlatko Drmač (mentor)
• Committee member: Nela Bosner (predsjednik povjerenstva)
• Committee member: Igor Ciganović (član povjerenstva)
• Committee member: Vjekoslav Kovač (član povjerenstva)
• Committee member: Nikola Sandrić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2023-09-27, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: težinski graf; Rayleighovi kvocijenti; najmanji spektralni rez
• Keywords (english): weighted graph; Rayleigh quotients; minimizing spectral cuts
• Language: croatian
• URN:NBN: urn:nbn:hr:217:047483
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar računarstva i matematike (sveučilišni magistar računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-02-05 13:46:28