{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T13:46:03Z","timestamp":1787060763949,"version":"build-2736575974"},"reference-count":102,"publisher":"MIT Press","issue":"11","license":[{"start":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T00:00:00Z","timestamp":1695081600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,10,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Markov chains are a class of probabilistic models that have achieved widespread application in the quantitative sciences. This is in part due to their versatility, but is compounded by the ease with which they can be probed analytically. This tutorial provides an in-depth introduction to Markov chains and explores their connection to graphs and random walks. We use tools from linear algebra and graph theory to describe the transition matrices of different types of Markov chains, with a particular focus on exploring properties of the eigenvalues and eigenvectors corresponding to these matrices. The results presented are relevant to a number of methods in machine learning and data mining, which we describe at various stages. Rather than being a novel academic study in its own right, this text presents a collection of known results, together with some new concepts. Moreover, the tutorial focuses on offering intuition to readers rather than formal understanding and only assumes basic exposure to concepts from linear algebra and probability theory. It is therefore accessible to students and researchers from a wide variety of disciplines.<\/jats:p>","DOI":"10.1162\/neco_a_01611","type":"journal-article","created":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T14:50:17Z","timestamp":1695135017000},"page":"1713-1796","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":25,"title":["A Tutorial on the Spectral Theory of Markov Chains"],"prefix":"10.1162","volume":"35","author":[{"given":"Eddie","family":"Seabrook","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Neuroinformatik, Ruhr-Universit\u00e4t, D-44780, Bochum, Germany eddie.seabrook@ini.rub.de"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laurenz","family":"Wiskott","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Neuroinformatik, Ruhr-Universit\u00e4t, D-44780, Bochum, Germany laurenz.wiskott@ini.rub.de"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"281","published-online":{"date-parts":[[2023,10,10]]},"reference":[{"key":"2023101122595999700_bib1","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/j.laa.2004.09.003","article-title":"On the spectra of nonsymmetric Laplacian matrices","volume":"399","author":"Agaev","year":"2005","journal-title":"Linear Algebra and Its Applications"},{"key":"2023101122595999700_bib2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-14142-8","volume-title":"Data mining","author":"Aggarwal","year":"2015"},{"key":"2023101122595999700_bib3","article-title":"Reversible Markov chains and random walks on graphs","author":"Aldous","year":"2002"},{"issue":"2","key":"2023101122595999700_bib4","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1109\/MCSE.2006.34","article-title":"The Monte Carlo method in science and engineering","volume":"8","author":"Amar","year":"2006","journal-title":"Computing in Science and Engineering"},{"key":"2023101122595999700_bib5","author":"Andrieux","year":"2011","journal-title":"Spectral signature of nonequilibrium conditions"},{"key":"2023101122595999700_bib6","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0024-3795(93)90286-W","article-title":"On swapping diagonal blocks in real Schur form","volume":"186","author":"Bai","year":"1993","journal-title":"Linear Algebra and Its Applications"},{"key":"2023101122595999700_bib7","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/978-3-662-04166-6_10","article-title":"A generalized cover time for random walks on graphs","volume-title":"Formal power series and algebraic combinatorics","author":"Banderier","year":"2000"},{"key":"2023101122595999700_bib8","first-page":"585","article-title":"Laplacian eigenmaps and spectral techniques for embedding and clustering","volume-title":"Advances in neural information processing systems 14","author":"Belkin","year":"2001"},{"issue":"6","key":"2023101122595999700_bib9","doi-asserted-by":"publisher","first-page":"1373","DOI":"10.1162\/089976603321780317","article-title":"Laplacian eigenmaps for dimensionality reduction and data representation","volume":"15","author":"Belkin","year":"2003","journal-title":"Neural Computation"},{"issue":"8","key":"2023101122595999700_bib10","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1016\/j.jcss.2007.08.006","article-title":"Towards a theoretical foundation for Laplacian-based manifold methods","volume":"74","author":"Belkin","year":"2008","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"2023101122595999700_bib11","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1080\/15427951.2005.10129098","article-title":"A survey on PageRank computing","volume":"2","author":"Berkhin","year":"2005","journal-title":"Internet Mathematics"},{"key":"2023101122595999700_bib12","article-title":"History of Monte Carlo","volume-title":"Monte Carlo techniques in radiation therapy","author":"Bielajew","year":"2012"},{"issue":"3","key":"2023101122595999700_bib13","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1002\/nla.274","article-title":"Matlab code for sorting real Schur forms","volume":"9","author":"Brandts","year":"2002","journal-title":"Numerical Linear Algebra with Applications"},{"key":"2023101122595999700_bib14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3124-8","volume-title":"Markov chains: Gibbs fields, Monte Carlo simulation and queues","author":"Br\u00e9maud","year":"1999"},{"issue":"1","key":"2023101122595999700_bib15","doi-asserted-by":"publisher","DOI":"10.37236\/1065","article-title":"Kernels of directed graph Laplacians","volume":"13","author":"Caughman","year":"2006","journal-title":"Electronic Journal of Combinatorics"},{"key":"2023101122595999700_bib16","first-page":"1065","article-title":"A tutorial introduction to Monte Carlo methods, Markov chain Monte Carlo and particle filtering","volume-title":"Academic Press library in signal processing","author":"Cemgil","year":"2014"},{"key":"2023101122595999700_bib17","doi-asserted-by":"crossref","first-page":"1461","DOI":"10.1109\/CDC.2011.6161471","article-title":"Advection on graphs","volume-title":"Proceedings of the IEEE Conference on Decision and Control and European Control Conference","author":"Chapman","year":"2011"},{"key":"2023101122595999700_bib18","first-page":"2707","article-title":"Directed graph embedding","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence","author":"Chen","year":"2007"},{"issue":"1","key":"2023101122595999700_bib19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00026-005-0237-z","article-title":"Laplacians and the Cheeger inequality for directed graphs","volume":"9","author":"Chung","year":"2005","journal-title":"Annals of Combinatorics"},{"key":"2023101122595999700_bib20","volume-title":"Spectral graph theory","author":"Chung","year":"1997"},{"issue":"1","key":"2023101122595999700_bib21","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.acha.2006.04.006","article-title":"Diffusion maps","volume":"21","author":"Coifman","year":"2006","journal-title":"Applied and Computational Harmonic Analysis"},{"issue":"21","key":"2023101122595999700_bib22","doi-asserted-by":"publisher","first-page":"7426","DOI":"10.1073\/pnas.0500334102","article-title":"Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps","volume":"102","author":"Coifman","year":"2005","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"21","key":"2023101122595999700_bib23","doi-asserted-by":"publisher","first-page":"7432","DOI":"10.1073\/pnas.0500896102","article-title":"Geometric diffusions as a tool for harmonic analysis and structure definition of data: Multiscale methods","volume":"102","author":"Coifman","year":"2005","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"4","key":"2023101122595999700_bib24","doi-asserted-by":"publisher","first-page":"1319","DOI":"10.1137\/15M1032272","article-title":"Finding dominant structures of nonreversible Markov processes","volume":"14","author":"Conrad","year":"2016","journal-title":"Multiscale Modeling and Simulation"},{"issue":"4","key":"2023101122595999700_bib25","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1162\/neco.2008.01-07-455","article-title":"Predictive coding and the slowness principle: An information-theoretic approach","volume":"20","author":"Creutzig","year":"2008","journal-title":"Neural Computation"},{"issue":"4","key":"2023101122595999700_bib26","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1162\/neco.1993.5.4.613","article-title":"Improving generalization for temporal difference learning: The successor representation","volume":"5","author":"Dayan","year":"1993","journal-title":"Neural Computation"},{"issue":"1","key":"2023101122595999700_bib27","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1090\/bull\/1722","article-title":"Eigenvectors from eigenvalues: A survey of a basic identity in linear algebra","volume":"59","author":"Denton","year":"2021","journal-title":"Bulletin of the American Mathematical Society"},{"issue":"1","key":"2023101122595999700_bib28","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1137\/0613013","article-title":"Numerical considerations in computing invariant subspaces","volume":"13","author":"Dongarra","year":"1992","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"issue":"5","key":"2023101122595999700_bib29","doi-asserted-by":"publisher","first-page":"6376","DOI":"10.1007\/s40314-018-0697-0","article-title":"Spectral clustering for non-reversible Markov chains","volume":"37","author":"Fackeldey","year":"2018","journal-title":"Computational and Applied Mathematics"},{"issue":"1","key":"2023101122595999700_bib30","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005981","article-title":"Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process","volume":"1","author":"Fill","year":"1991","journal-title":"Annals of Applied Probability"},{"issue":"6","key":"2023101122595999700_bib31","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1145\/1953122.1953146","article-title":"PageRank: Standing on the shoulders of giants","volume":"54","author":"Franceschet","year":"2011","journal-title":"Communications of the ACM"},{"issue":"3","key":"2023101122595999700_bib32","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.physrep.2011.09.001","article-title":"Stochastic theory of nonequilibrium steady states. Part II: Applications in chemical biophysics","volume":"510","author":"Ge","year":"2012","journal-title":"Physics Reports"},{"key":"2023101122595999700_bib33","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-74437-7_6","volume-title":"Periodic Markov chains","author":"Gebali","year":"2008"},{"key":"2023101122595999700_bib34","author":"Ghojogh","year":"2021","journal-title":"Laplacian-based dimensionality reduction including spectral clustering, Laplacian eigenmap, locality preserving projection, graph embedding, and diffusion map: Tutorial and survey."},{"key":"2023101122595999700_bib35","first-page":"3556","article-title":"Representations for stable off-policy reinforcement learning","volume-title":"Proceedings of the 37th International Conference on Machine Learning","author":"Ghosh","year":"2020"},{"issue":"4","key":"2023101122595999700_bib36","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0304-4149(74)90001-5","article-title":"Random walks on graphs","volume":"2","author":"G\u00f6bel","year":"1974","journal-title":"Stochastic Processes and Their Applications"},{"key":"2023101122595999700_bib37","doi-asserted-by":"crossref","DOI":"10.56021\/9781421407944","volume-title":"Matrix computations","author":"Golub","year":"2013","edition":"4th"},{"key":"2023101122595999700_bib38","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.rinp.2014.09.002","article-title":"Detailed balance in micro- and macrokinetics and micro-distinguishability of macro-processes","volume":"4","author":"Gorban","year":"2014","journal-title":"Results in Physics"},{"issue":"9","key":"2023101122595999700_bib39","doi-asserted-by":"publisher","first-page":"1225","DOI":"10.1002\/cpe.1386","article-title":"Parallel eigenvalue reordering in real Schur forms","volume":"21","author":"Granat","year":"2009","journal-title":"Concurrency and Computation: Practice and Experience"},{"issue":"4","key":"2023101122595999700_bib40","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1137\/120880173","article-title":"Geometrical structure of Laplacian eigenfunctions","volume":"55","author":"Grebenkov","year":"2013","journal-title":"SIAM Review"},{"issue":"1","key":"2023101122595999700_bib41","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/1012001","article-title":"A retrospective and prospective survey of the Monte Carlo method","volume":"12","author":"Halton","year":"1970","journal-title":"SIAM Review"},{"issue":"1","key":"2023101122595999700_bib42","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1093\/biomet\/57.1.97","article-title":"Monte Carlo sampling methods using Markov chains and their applications","volume":"57","author":"Hastings","year":"1970","journal-title":"Biometrika"},{"key":"2023101122595999700_bib43","first-page":"1325","article-title":"Graph Laplacians and their convergence on random neighborhood graphs","volume":"8","author":"Hein","year":"2007","journal-title":"Journal of Machine Learning Research"},{"key":"2023101122595999700_bib44","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/11871637_21","article-title":"Web communities identification from random walks","volume-title":"Knowledge discovery in databases: PKDD 2006","author":"Huang","year":"2006"},{"key":"2023101122595999700_bib45","doi-asserted-by":"crossref","DOI":"10.1007\/b94615","volume-title":"Mathematical theory of nonequilibrium steady states","author":"Jiang","year":"2004"},{"key":"2023101122595999700_bib46","first-page":"290","article-title":"Transductive learning via spectral graph partitioning","volume-title":"Proceedings of the Twentieth International Conference on International Conference on Machine Learning","author":"Joachims","year":"2003"},{"key":"2023101122595999700_bib47","author":"Johansen","year":"2007","journal-title":"Monte Carlo methods"},{"key":"2023101122595999700_bib48","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1145\/1273496.1273545","article-title":"Constructing basis functions from directed graphs for value function approximation","volume-title":"Proceedings of the 24th International Conference on Machine Learning","author":"Johns","year":"2007"},{"key":"2023101122595999700_bib49","first-page":"561","article-title":"Spectral learning","volume-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence","author":"Kamvar","year":"2003"},{"issue":"1","key":"2023101122595999700_bib50","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF01565412","article-title":"Zur Theorie der Markoffschen Ketten","volume":"112","author":"Kolmogoroff","year":"1936","journal-title":"Mathematische Annalen"},{"issue":"6","key":"2023101122595999700_bib51","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1002\/wics.1314","article-title":"Why the Monte Carlo method is so important today","volume":"6","author":"Kroese","year":"2014","journal-title":"WIREs Computational Statistics"},{"key":"2023101122595999700_bib52","volume-title":"Markov chains and mixing times","author":"Levin","year":"2009"},{"issue":"4","key":"2023101122595999700_bib53","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1080\/15427951.2012.708890","article-title":"Digraph Laplacian and the degree of asymmetry","volume":"8","author":"Li","year":"2012","journal-title":"Internet Mathematics"},{"key":"2023101122595999700_bib54","first-page":"87","article-title":"Markov chains and spectral clustering","volume-title":"Performance evaluation of computer and communication systems: Milestones and future challenges","author":"Liu","year":"2011"},{"key":"2023101122595999700_bib55","article-title":"Random walks on graphs: A survey","author":"Lov\u00e1sz","year":"1993","journal-title":"Open Journal of Discrete Mathematics"},{"key":"2023101122595999700_bib56","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1145\/1102351.1102421","article-title":"Proto-value functions: Developmental reinforcement learning","volume-title":"Machine learning: Proceedings of the Twenty-Second International Conference","author":"Mahadevan","year":"2005"},{"key":"2023101122595999700_bib57","first-page":"2169","article-title":"Proto-value functions: A Laplacian framework for learning representation and control in Markov decision processes","volume":"8","author":"Mahadevan","year":"2007","journal-title":"Journal of Machine Learning Research"},{"key":"2023101122595999700_bib58","first-page":"1194","article-title":"Learning representation and control in continuous Markov decision processes","volume-title":"Proceedings of the 21st National Conference on Artificial Intelligence","author":"Mahadevan","year":"2006"},{"issue":"6","key":"2023101122595999700_bib59","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1109\/MSP.2020.3014597","article-title":"Signal processing on directed graphs: The role of edge directionality when processing and learning from network data","volume":"37","author":"Marques","year":"2020","journal-title":"IEEE Signal Processing Magazine"},{"key":"2023101122595999700_bib60","first-page":"135","article-title":"Clustering by weighted cuts in directed graphs","volume-title":"Proceedings of the 2007 SIAM International Conference on Data Mining","author":"Meil\u0103","year":"2007"},{"key":"2023101122595999700_bib61","article-title":"Learning segmentation by random walks","volume-title":"Advances in neural information processing systems","author":"Meil\u0103","year":"2000"},{"key":"2023101122595999700_bib62","first-page":"203","article-title":"A random walks view of spectral segmentation","volume-title":"Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics","author":"Meil\u0103","year":"2001"},{"issue":"6","key":"2023101122595999700_bib63","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1063\/1.1699114","article-title":"Equation of state calculations by fast computing machines","volume":"21","author":"Metropolis","year":"1953","journal-title":"Journal of Chemical Physics"},{"key":"2023101122595999700_bib64","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719512","volume-title":"Matrix analysis and applied linear algebra","author":"Meyer","year":"2000"},{"key":"2023101122595999700_bib65","first-page":"3835","article-title":"On complex spectra and metastability of Markov models","volume-title":"Proceedings of the 47th IEEE Conference on Decision and Control","author":"Meyn","year":"2008"},{"key":"2023101122595999700_bib66","article-title":"Directed graphs and mysterious complex eigenvalues","author":"Mieghem","year":"2018"},{"key":"2023101122595999700_bib67","first-page":"849","article-title":"On spectral clustering: Analysis and an algorithm","volume-title":"Advances in neural information processing systems 14","author":"Ng","year":"2001"},{"key":"2023101122595999700_bib68","author":"Ng","year":"1987","journal-title":"Programs to swap diagonal blocks."},{"key":"2023101122595999700_bib69","article-title":"The PageRank citation ranking: Bringing order to the web","author":"Page","year":"1999","journal-title":"Proceedings of the International World Wide Conference"},{"key":"2023101122595999700_bib70","volume-title":"Markov processes and applications: Algorithms, networks, genome and finance","author":"Pardoux","year":"2010"},{"key":"2023101122595999700_bib71","first-page":"1","article-title":"Perturbations of non-diagonalizable stochastic matrices with preservation of spectral properties","volume":"70","author":"Pauwelyn","year":"2021","journal-title":"Linear and Multilinear Algebra"},{"key":"2023101122595999700_bib72","first-page":"845","article-title":"Spectral clustering of biological sequence data","volume-title":"Proceedings of the 20th National Conference on Artificial Intelligence","author":"Pentney","year":"2005"},{"key":"2023101122595999700_bib73","first-page":"990","article-title":"Directed graph embedding: An algorithm based on continuous limits of Laplacian-type operators","volume-title":"Advances in neural information processing systems","author":"Perrault-Joncas","year":"2011"},{"key":"2023101122595999700_bib74","first-page":"2574","article-title":"An analysis of Laplacian methods for value function approximation in MDPs","volume-title":"Proceedings of the 20th International Joint Conference on Artificial Intelligence","author":"Petrik","year":"2007"},{"key":"2023101122595999700_bib75","author":"Porod","year":"2021","journal-title":"Dynamics of Markov chains for undergraduates"},{"issue":"3","key":"2023101122595999700_bib76","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1080\/00029890.1982.11995407","article-title":"Mean curvature, the Laplacian, and soap bubbles","volume":"89","author":"Reilly","year":"1982","journal-title":"American Mathematical Monthly"},{"issue":"5","key":"2023101122595999700_bib77","article-title":"The evolution of Markov chain Monte Carlo methods","volume":"117","author":"Richey","year":"2010","journal-title":"American Mathematical Monthly"},{"issue":"5","key":"2023101122595999700_bib78","doi-asserted-by":"publisher","DOI":"10.1002\/wics.1435","article-title":"Accelerating MCMC algorithms","volume":"10","author":"Robert","year":"2018","journal-title":"WIREs Computational Statistics"},{"key":"2023101122595999700_bib79","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1007\/978-3-540-30115-8_35","article-title":"The principal components analysis of a graph, and its relationships to spectral clustering","volume-title":"Machine learning: ECML 2004","author":"Saerens","year":"2004"},{"key":"2023101122595999700_bib80","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1016\/j.acha.2022.10.003","article-title":"Harmonic analysis on directed graphs and applications: From Fourier analysis to wavelets","volume":"62","author":"Sevi","year":"2023","journal-title":"Applied and Computational Harmonic Analysis"},{"issue":"3","key":"2023101122595999700_bib81","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1109\/MSP.2012.2235192","article-title":"The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains","volume":"30","author":"Shuman","year":"2013","journal-title":"IEEE Signal Processing Magazine"},{"key":"2023101122595999700_bib82","first-page":"1","article-title":"Graph Fourier transform based on directed Laplacian","volume-title":"Proceedings of the 2016 International Conference on Signal Processing and Communications","author":"Singh","year":"2016"},{"key":"2023101122595999700_bib83","author":"Spielman","year":"2019","journal-title":"Spectral and algebraic graph theory"},{"issue":"12","key":"2023101122595999700_bib84","doi-asserted-by":"publisher","first-page":"3287","DOI":"10.1162\/NECO_a_00214","article-title":"On the relation of slow feature analysis and Laplacian eigenmaps","volume":"23","author":"Sprekeler","year":"2011","journal-title":"Neural Computation"},{"key":"2023101122595999700_bib85","article-title":"Design principles of the hippocampal cognitive map","volume-title":"Advances in neural information processing systems","author":"Stachenfeld","year":"2014"},{"issue":"11","key":"2023101122595999700_bib86","doi-asserted-by":"publisher","first-page":"1643","DOI":"10.1038\/nn.4650","article-title":"The hippocampus as a predictive map","volume":"20","author":"Stachenfeld","year":"2017","journal-title":"Nature Neuroscience"},{"key":"2023101122595999700_bib87","volume-title":"Introduction to the numerical solution of Markov chains","author":"Stewart","year":"1994"},{"key":"2023101122595999700_bib88","volume-title":"Reinforcement learning: An introduction","author":"Sutton","year":"2018","edition":"2nd"},{"key":"2023101122595999700_bib89","first-page":"945","article-title":"Partially labeled classification with Markov random walks","volume-title":"Advances in neural information processing systems","author":"Szummer","year":"2001"},{"key":"2023101122595999700_bib90","article-title":"Data clustering by Markovian relaxation and the information bottleneck method","volume-title":"Advances in neural information processing systems","author":"Tishby","year":"2001"},{"key":"2023101122595999700_bib91","article-title":"Geometric random walks: A survey","volume":"52","author":"Vempala","year":"2005","journal-title":"Combinatorial and Computational Geometry"},{"issue":"4","key":"2023101122595999700_bib92","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","article-title":"A tutorial on spectral clustering","volume":"17","author":"von Luxburg","year":"2007","journal-title":"Statistics and Computing"},{"key":"2023101122595999700_bib93","author":"Weber","year":"2017","journal-title":"Eigenvalues of non-reversible Markov chains: A case study."},{"issue":"23","key":"2023101122595999700_bib94","doi-asserted-by":"publisher","first-page":"7907","DOI":"10.1073\/pnas.0707563105","article-title":"Optimal partition and effective dynamics of complex networks","volume":"105","author":"Weinan","year":"2008","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"2023101122595999700_bib95","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1109\/ICCV.1999.790354","article-title":"Segmentation using eigenvectors: A unifying view","volume-title":"Proceedings of the Seventh IEEE International Conference on Computer Vision","author":"Weiss","year":"1999"},{"key":"2023101122595999700_bib96","volume-title":"Introduction to graph theory","author":"West","year":"2001","edition":"2nd"},{"key":"2023101122595999700_bib97","author":"Wiskott","year":"2019","journal-title":"Laplacian matrix for dimensionality reduction and clustering"},{"issue":"4","key":"2023101122595999700_bib98","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1162\/089976602317318938","article-title":"Slow feature analysis: Unsupervised learning of invariances","volume":"14","author":"Wiskott","year":"2002","journal-title":"Neural Computation"},{"issue":"1","key":"2023101122595999700_bib99","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1137\/16M1091162","article-title":"Mixed-integer programming for cycle detection in nonreversible Markov processes","volume":"16","author":"Witzig","year":"2018","journal-title":"Multiscale Modeling and Simulation"},{"key":"2023101122595999700_bib100","article-title":"The Laplacian in RL: Learning representations with efficient approximations","author":"Wu","year":"2019","journal-title":"Proceedings of the 7th International Conference on Learning Representations"},{"issue":"1\u20132","key":"2023101122595999700_bib101","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.physrep.2011.09.002","article-title":"Stochastic theory of nonequilibrium steady states and its applications. Part I","volume":"510","author":"Zhang","year":"2012","journal-title":"Physics Reports"},{"key":"2023101122595999700_bib102","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1145\/1102351.1102482","article-title":"Learning from labeled and unlabeled data on a directed graph","volume-title":"Proceedings of the 22nd International Conference on Machine Learning","author":"Zhou","year":"2005"}],"updated-by":[{"DOI":"10.1162\/neco_e_01662","type":"erratum","label":"Erratum","source":"publisher","updated":{"date-parts":[[2024,2,16]],"date-time":"2024-02-16T00:00:00Z","timestamp":1708041600000}}],"container-title":["Neural Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/neco\/article-pdf\/35\/11\/1713\/2162715\/neco_a_01611.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/neco\/article-pdf\/35\/11\/1713\/2162715\/neco_a_01611.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T19:00:59Z","timestamp":1697050859000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/neco\/article\/35\/11\/1713\/117578\/A-Tutorial-on-the-Spectral-Theory-of-Markov-Chains"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,10]]},"references-count":102,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2023,10,10]]},"published-print":{"date-parts":[[2023,10,10]]}},"URL":"https:\/\/doi.org\/10.1162\/neco_a_01611","relation":{},"ISSN":["0899-7667","1530-888X"],"issn-type":[{"value":"0899-7667","type":"print"},{"value":"1530-888X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,11]]},"published":{"date-parts":[[2023,10,10]]}}}