Export Mendeley
＜Doctoral Thesis＞
A study on normalized Laplacian, normalized cut and graph partitioning
| Creator | |
|---|---|
| Examiner | |
| Language | |
| Academic Year Conferred | |
| Conferring University | |
| Degree | |
| Degree Type | |
| Publication Type | |
| Access Rights | |
| JaLC DOI | |
| Abstract | 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 |
| Table of Contents | Abstract Acknowledgments 1 Introduction 2 Minimum normalized cut of some graph classes 3 Difference Laplacian, normalized Laplacian, signless Laplacian and their eigenvalues 4 Counter examples for Mcut(G) ?= Lcut(G) 5 Laplacian energy of directed graphs 6 Spectral clustering for directed graphs References |
Hide fulltext details.
| File | FileType | Size | Views | Description |
|---|---|---|---|---|
math140
|
2.14 MB | 954 | 本文 | |
|
math140_abstract
|
17.8 KB | 350 | 要旨 |
Details
| Record ID | |
|---|---|
| Peer-Reviewed | |
| Keywords | |
| Report Number | |
| Number of Diploma | |
| Granted Date | |
| Date Accepted | |
| Faculty | |
| Location | |
| Location | |
| Call Number | |
| Notes | |
| Created Date | 2013.07.12 |
| Modified Date | 2023.11.21 |