Mendeley出力
＜博士論文＞
ラプラシアン行列と標準カットに基づくグラフ分割に関する研究
| 作成者 | |
|---|---|
| 論文調査委員 | |
| 本文言語 | |
| 学位授与年度 | |
| 学位授与大学 | |
| 学位 | |
| 学位種別 | |
| 出版タイプ | |
| アクセス権 | |
| JaLC DOI | |
| 概要 | 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
|
2.14 MB | 1,060 | 本文 | |
|
math140_abstract
|
17.8 KB | 408 | 要旨 |
詳細
| レコードID | |
|---|---|
| 査読有無 | |
| キーワード | |
| 報告番号 | |
| 学位記番号 | |
| 授与日(学位/助成/特許) | |
| 受理日 | |
| 部局 | |
| 所蔵場所 | |
| 所蔵場所 | |
| 所在記号 | |
| 注記 | |
| 登録日 | 2013.07.12 |
| 更新日 | 2023.11.21 |