Spectral Clustering for Graphs and Markov Chains

spectral clustering;graph partitioning;markov chains;eigenvalue

Liu, Ning ; Dr. William J. Stewart, Committee Chair,Dr. Harry G. Perros, Committee Co-Chair,Dr. Laurie Williams, Committee Member,Dr. Michael Devetsikiotis, Committee Member,Liu, Ning ; Dr. William J. Stewart ; Committee Chair ; Dr. Harry G. Perros ; Committee Co-Chair ; Dr. Laurie Williams ; Committee Member ; Dr. Michael Devetsikiotis ; Committee Member

University:North Carolina State University

关键词: spectral clustering;    graph partitioning;    markov chains;    eigenvalue;   

Others  :  https://repository.lib.ncsu.edu/bitstream/handle/1840.16/4886/etd.pdf?sequence=1&isAllowed=y

美国|英语

来源: null

【 摘 要 】

Spectral graph partitioning based on spectral theory has become a popular clustering method over the last few years. The starting point is the work of Fiedler who shows that an eigenvector of the Laplacian matrix of an undirected graph (symmetric system) provides the minimum cut of graph nodes. The spectral technique can also beapplied to a Markov chain to cluster states and, in general, is more broadly applicable to nonsymmetric systems. Enlightened by thesefacts, we combine them to show that Markov chains, due to two different clustering techniques they offer, are effective approachesfor clustering in more general situations. In this dissertation, we advance the state of the art of spectral clustering and introduce anew algorithm to decompose matrices into blocks.We first prove that the second eigenvector of the signless Laplacian provides a heuristic solution to the NP-complete state clustering problem which is the dual problem of graph partitioning. A newmethod for clustering nodes of a graph that have negative edge weights is also proposed.Second, a connection between the singular vectors obtained from an SVD decomposition and the eigenvectors from spectral algorithms on data clustering is revealed. We show that the singular vectors of the node-edge incidence matrix generate not only clusters on the nodes but also clusters on the edges.Third, relating spectral clustering and state clustering of Markov chains, we present two clustering techniques for Markov chains basedon two different measures and suggest a mean of incorporating both techniques to obtain comprehensive information concerning stateclusters.Fourth, we display the connection between spectral clustering and dimension reduction techniques in statistical clustering. Also, theresults obtained from spectral and statistical clustering are shown to be related.Finally, we develop a new improved spectral clustering procedure for decomposing matrices into blocks. This algorithm works well inseveral applications, especially in problems of detecting communities in complex networks, where some existing methods, e.g. MARCA and TPABLO, fail.