## ＜Doctoral Thesis＞A study on normalized Laplacian, normalized cut and graph partitioning

 A study on normalized Laplacian, normalized cut and graph partitioning Creator Name Affiliation Affiliation Name Graduate School of Mathematics, Kyushu University 溝口, 佳寛 English 2011 九州大学 Kyushu University DOCTOR OF FUNCTIONAL MATHEMATICS Doctoral Degree Version of Record open access https://doi.org/10.15017/21705 In the last decade important relationships between Laplacian eigenvalues and the eigenvectors of graphs and several other graph parameters were discovered. Spectral clustering uses eigenvalues and eig...envectors of matrices associated with graphs to find clusters in the graphs and is widely used to analysis the social networks, web graphs, communication networks etc. In this thesis, we present some of the results and discuss their consequences in spectral clustering and graph energy. We mainly consider normalized Laplacian matrix to find the bipartitions of graphs. There is a close relationship between the second smallest eigenvalue of normalized Laplacian matrix and the normalized cut introduced by Shi and Malik. We compare these two clustering methods and discuss their performances. Several authors considered the applications of normalized cut for graph partitioning and less attention is paid for theoretical explanation of this measure compare with isoperimetric and Cheeger constant. Here we use the notation Mcut(G) to represent the minimum normalized cut and derive formula for Mcut(G) of some basic classes of graphs such as paths, cycles, complete graphs, double trees and cycle cross paths and some complex graphs such as lollipop type graphs LP_n_,_m and LP'_n_,_2, roach type graphs R_n_,_k, weighted paths P_n_,_k and double tree cross paths. Next we discuss three matrices associated with graphs called difference Laplacian matrix, normalized Laplacian matrix and signless Laplacian matrix and review some known results. Specially we discuss the boundary values of the second smallest eigenvalue of the difference and normalized Laplacian matrices using isoperimetric number and Cheeger constant. Next we address the problem of finding graphs which perform poorly on spectral methods. We use the term Lcut(G) to represent the minimum normalized cut of partitions produced by the second eigenvector of normalized Laplacian matrix. We give counter examples of graphs and conditions, where Mcut(G) and Lcut(G) produce different clusters on graphs. Next we address the problem of finding directed graphs with minimum Laplacian energy. First, we define Laplacian energy of a directed graph as the sum of squares of eigenvalues of a Laplacian matrix. Then we derive a formula for Laplacian energy of a simple directed graph using outdegrees of vertices. This motivates us to consider the problem of minimizing sum of squares of degrees in order to find the graphs with minimum Laplacian energy. Finally, we demonstrate the experimental results about spectral clustering on directed graphs. We extend the undirected spectral clustering algorithms to directed graphs using directed Laplacian matrix. Further we propose an algorithm based on merging techniques.show more AbstractAcknowledgments1 Introduction2 Minimum normalized cut of some graph classes3 Difference Laplacian, normalized Laplacian, signless Laplacian and their eigenvalues4 Counter examples for Mcut(G) ?= Lcut(G)5 Laplacian energy of directed graphs6 Spectral clustering for directed graphsReferences

### Hide fulltext details.

math140 pdf 2.14 MB 1,006 本文
math140_abstract pdf 17.8 KB 376 要旨

### Details

Record ID 21705 Refereed Laplacian graph partitioning 甲第10645号 数理博甲第0140号 2012-03-27 2012-01-25 数理博 SciTech 学位論文書庫【閉架】 Closed Stacks 数理博/甲/140 主1-参1 数理 2013.07.12 2023.11.21