Professional paper

Spectral partitioning of graph

Ivančica Mirošević orcid.org/0000-0002-6356-1943 ; ∗Fakultet elektrotehnike, strojarstva i brodogradnje, Sveučilište u Splitu

Abstract

In this paper, the clustering problem is formulated as a graph bipartitioning problem which is a discrete optimization problem, and the relaxed version of it leads to the eigenvectors of the corresponding
Laplacian matrix. Two versions of the cost functions are defined, ratio cut and normalized cut, and it is shown that they are minimized by the Fiedler vector of the Laplacian and the normalized Laplacian of
the graph.

Keywords

Spectral clustering; graph partitioning; ratio cut; normalized cut

Hrčak ID:

186510

URI

https://hrcak.srce.hr/186510

Publication date:

10.7.2017.

Article data in other languages: croatian

Visits: 1.171 *