The graph conductance 
of a graph 
,
also called the edge conductance or normalized edge expansion, is an isoperimetric
parameter that measures how difficult it is to separate 
into two large pieces by deleting relatively few edges. It
is defined by
 |
(1)
|
where
 |
(2)
|
is the volume of 
and
 |
(3)
|
Equivalently, since
 |
(4)
|
graph conductance is also equal to
 |
(5)
|
Graph conductance is closely related to the Cheeger constant. The latter is often defined by
 |
(6)
|
so conductance differs only in replacing the cardinality of a vertex set by its volume.
For a 
-regular graph,
 |
(7)
|
but for irregular graphs the two quantities do not in general coincide.
Graph conductance plays an important role in the study of expanders, random walks, and spectral graph theory. In particular, it appears in discrete versions of Cheeger inequalities relating isoperimetric properties to eigenvalues of the Laplacian and normalized Laplacian.
Some authors use slightly different normalizations or allow the minimum to range over all nonempty proper subsets 
, replacing 
in the denominator by 
. This gives an equivalent formulation of
the same quantity.
