<博士論文>
ラプラシアン行列と標準カットに基づくグラフ分割に関する研究

作成者
指導教員等
本文言語
学位授与年度
学位授与大学
学位
学位種別
出版タイプ
アクセス権
概要 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.続きを見る
目次 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

本文情報を非表示

math140 pdf 2.14 MB 641 本文
math140_abstract pdf 17.8 KB 161 要旨

詳細

レコードID
selfDOI
査読有無
関連情報
キーワード
報告番号
学位記番号
受理日
部局
所蔵場所
所蔵場所
所在記号
注記
登録日 2013.07.12
更新日 2019.06.12

この資料を見た人はこんな資料も見ています