Skip to the main content

Osječki matematički list, Vol. 17 No. 1, 2017.

Professional paper

Spectral partitioning of graph

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

Full text: croatian pdf 538 Kb

page 71-87

downloads: 515

cite

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.648 *