Random walks and local cuts in graphs

DOI10.1016/J.LAA.2006.07.018MaRDI QIDQ876299zbMATH OpenOpenAlexFDO

Authors Fan Chung

Publication date 18 April 2007

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2006.07.018

zbMATH Keywords

isoperimetric inequalityLaplacianDirichlet eigenvalueslocal Cheeger constantlocal random walk

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 4197088
• Cutoff phenomena for random walks on random regular graphs
• scientific article; zbMATH DE number 4007384
• Random walks and bisections in random circulant graphs
• Random walks on graphs: ideas, techniques and results
• Random walks on the random graph
• Random walks on dense graphs and graphons
• Cutpoints for simple random walks on quasi-transitive graphs
• scientific article; zbMATH DE number 878897
• scientific article; zbMATH DE number 909704

Cites work

• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• A random graph model for massive graphs
• Collective dynamics of `small-world' networks
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Random walks in a convex body and an improved volume algorithm
• Statistical mechanics of complex networks

Cited in

(20)

• Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• Graph clustering
• Dirichlet eigenvalues, local random walks, and analyzing clusters in graphs
• A Cheeger-type inequality on simplicial complexes
• The cut metric, random graphs, and branching processes
• Polynomial-time algorithms for submodular Laplacian systems
• The normalized graph cut and Cheeger constant: from discrete to continuous
• Random walks on simplicial complexes and harmonics
• Harmonic analysis on graphs via Bratteli diagrams and path-space measures
• scientific article; zbMATH DE number 7651049 (Why is no real title available?)
• Random walks associated with symmetric \(M\)-matrices
• Cut ratios and Laplacian eigenvalues
• Compressive sensing for cut improvement and local clustering
• Stochastic forms of non-negative matrices and Perron-regularity
• scientific article; zbMATH DE number 878889 (Why is no real title available?)
• Variational perspective on local graph clustering
• A Schur complement Cheeger inequality
• Eigenvalues of 2-edge-coverings
• Optimal Cheeger cuts and bisections of random geometric graphs
• Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile

This page was built for publication: Random walks and local cuts in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q876299)