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)

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

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)