Skip to Main content Skip to Navigation
Conference papers

Markov Chains and Spectral Clustering

Abstract : The importance of Markov chains in modeling diverse systems, including biological, physical, social and economic systems, has long been known and is well documented. More recently, Markov chains have proven to be effective when applied to internet search engines such as Google’s PageRank model [7], and in data mining applications wherein data trends are sought. It is with this type of Markov chain application that we focus our research efforts. Our starting point is the work of Fiedler who in the early 70’s developed a spectral partitioning method to obtain the minimum cut on an undirected graph (symmetric system). The vector that results from the spectral decomposition, called the Fiedler vector, allows the nodes of the graph to be partitioned into two subsets. At the same time that Fiedler proposed his spectral approach, Stewart proposed a method based on the dominant eigenvectors of a Markov chain — a method which was more broadly applicable to nonsymmetric systems. Enlightened by these, somewhat orthogonal, results and combining them together, we show that spectral partitioning can be viewed in the framework of state clustering on Markov chains. Our research results to date are two-fold. First, we prove that the second eigenvector of the signless Laplacian provides a heuristic solution to the NP-complete state clustering problem which is the dual of the minimum cut problem. Second, we propose two clustering techniques for Markov chains based on two different clustering measures.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01586907
Contributor : Hal Ifip <>
Submitted on : Wednesday, September 13, 2017 - 1:50:07 PM
Last modification on : Wednesday, August 21, 2019 - 10:38:02 AM
Long-term archiving on: : Thursday, December 14, 2017 - 1:05:43 PM

File

978-3-642-25575-5_8_Chapter.pd...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Ning Liu, William Stewart. Markov Chains and Spectral Clustering. Performance Evaluation of Computer and Communication Systems (PERFORM), Oct 2010, Vienna, Austria. pp.87-98, ⟨10.1007/978-3-642-25575-5_8⟩. ⟨hal-01586907⟩

Share

Metrics

Record views

83

Files downloads

933