Random walks and local cuts in graphs

DOI10.1016/j.laa.2006.07.018zbMath1115.05054OpenAlexW2032336879MaRDI QIDQ876299

Fan R. K. 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

Dirichlet eigenvaluesisoperimetric inequalityLaplacianlocal Cheeger constantlocal random walk

Mathematics Subject Classification ID

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

Related Items

Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance, Harmonic analysis on graphs via Bratteli diagrams and path-space measures, Stochastic forms of non-negative matrices and Perron-regularity, Dirichlet Eigenvalues, Local Random Walks, and Analyzing Clusters in Graphs, A Cheeger-type inequality on simplicial complexes, Graph clustering, Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile, Variational perspective on local graph clustering, Polynomial-time algorithms for submodular Laplacian systems, Eigenvalues of 2-edge-coverings, Random walks on simplicial complexes and harmonics, Compressive Sensing for Cut Improvement and Local Clustering

Cites Work

• Unnamed Item
• Statistical mechanics of complex networks
• A random graph model for massive graphs
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Random walks in a convex body and an improved volume algorithm
• Collective dynamics of ‘small-world’ networks