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.
Type de document :
Communication dans un congrès
Karin Anna Hummel; Helmut Hlavacs; Wilfried Gansterer. Performance Evaluation of Computer and Communication Systems (PERFORM), Oct 2010, Vienna, Austria. Springer, Lecture Notes in Computer Science, LNCS-6821, pp.87-98, 2011, Performance Evaluation of Computer and Communication Systems. Milestones and Future Challenges. 〈10.1007/978-3-642-25575-5_8〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01586907
Contributeur : Hal Ifip <>
Soumis le : mercredi 13 septembre 2017 - 13:50:07
Dernière modification le : mercredi 13 septembre 2017 - 15:19:41
Document(s) archivé(s) le : jeudi 14 décembre 2017 - 13:05:43

Fichier

978-3-642-25575-5_8_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Ning Liu, William Stewart. Markov Chains and Spectral Clustering. Karin Anna Hummel; Helmut Hlavacs; Wilfried Gansterer. Performance Evaluation of Computer and Communication Systems (PERFORM), Oct 2010, Vienna, Austria. Springer, Lecture Notes in Computer Science, LNCS-6821, pp.87-98, 2011, Performance Evaluation of Computer and Communication Systems. Milestones and Future Challenges. 〈10.1007/978-3-642-25575-5_8〉. 〈hal-01586907〉

Partager

Métriques

Consultations de la notice

11

Téléchargements de fichiers

3