Random walks and local cuts in graphs
Linear Algebra and its ApplicationsPublished 3 October 2006
Fan Chung
Citations65
SJR quartileQ1
SJR score0.98
SNIP1.40
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
For a specified subset S of vertices in a graph G we consider local cuts that separate a subset of S. We consider the local Cheeger constant which is the minimum Cheeger ratio over all subsets of S, and we examine the relationship between the local Cheeger constant and the Dirichlet eigenvalue of the induced subgraph on S. These relationships are summarized in a local Cheeger inequality. The proofs are based on the methods of establishing isoperimetric inequalities using random walks and the spectral methods for eigenvalues with Dirichlet boundary conditions.
Keywords
MathematicsBiochemistry, Genetics and Molecular Biology
NatureCollective dynamics of ‘small-world’ networks
43,160 Citations1998Duncan J. Watts, Steven H. Strogatz
Simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder are explored, finding that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs.
Reviews of Modern PhysicsStatistical mechanics of complex networks
20,607 Citations2002Réka Albert, Albert-Ĺaszló Barabási
A simple model based on these two principles was able to reproduce the power-law degree distribution of real networks, indicating a heterogeneous topology in which the majority of the nodes have a small degree, but there is a significant fraction of highly connected nodes that play an important role in the connectivity of the network.
On power-law relationships of the Internet topology
4,222 Citations1999Michalis Faloutsos, Petros Faloutsos +1 more
These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period, and can be used to generate and select realistic topologies for simulation purposes.
A random graph model for massive graphs
925 Citations2000William Aiello, Fan Chung +1 more
A random graph model is proposed which is a special case of sparse random graphs with given degree sequences which involves only a small number of parameters, called logsize and log-log growth rate, which capture some universal characteristics of massive graphs.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
784 Citations2004Daniel A. Spielman, Shang‐Hua Teng
This paper presents algorithms for solving symmetric, diagonally-dominant linear systems to accuracy ε in time linear in their number of non-zeros and log (κf (A) ε), where ε is the condition number of the matrix defining the linear system.
Random Structures and AlgorithmsRandom walks in a convex body and an improved volume algorithm
425 Citations1993László Lovász, Miklós Simonovits
A randomized algorithm using O(n7 log’ n) separation calls to approximate the volume of a convex body with a fixed relative error is given and the mixing rate of Markov chains from finite to arbitrary Markov Chains is analyzed.
The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume
198 Citations2002László Lovász, Miklós Simonovits
The authors generalize a bound on the mixing rate of time-reversible Markov chains in terms of their conductance by not assuming time reversibility and using a weaker notion of conductance and prove an isoperimetric inequality for subsets of a convex body.