Markov Chains and Spectral Clustering - Performance Evaluation of Computer and Communication Systems: Milestones and Future Challenges Access content directly
Conference Papers Year : 2011

Markov Chains and Spectral Clustering

Ning Liu
  • Function : Author
  • PersonId : 1016279
William J. Stewart
  • Function : Author
  • PersonId : 1016280


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.
Fichier principal
Vignette du fichier
978-3-642-25575-5_8_Chapter.pdf (177.89 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01586907 , version 1 (13-09-2017)





Ning Liu, William J. 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⟩
69 View
1038 Download



Gmail Facebook X LinkedIn More