Conductance (graph)

In graph theory the conductance of a graph "G"=("V","E") measures how "well-knit" the graph is: it controls how fast a random walk on "G" converges to its stationary distribution. The conductance of a graph is often called the Cheeger constant of a graph as the 
analog of its counterpart in spectral geometry. Since electrical networks are intimately related to random walks
with a long history in the usage of the term "conductance", this alternative name helps avoid possible confusion.
The conductance of a cut formula_1 in a graph is defined as:
where the formula_3 are the entries of the adjacency matrix for "G", so that
is the total number (or weight) of the edges incident with "S". formula_5 is also called a volume of the set formula_6.
The conductance of the whole graph is the minimum conductance over all the possible cuts:
Equivalently, conductance of a graph is defined as follows: 
For a "d"-regular graph, the conductance is equal to the isoperimetric number divided by "d".
Generalizations and applications.
In practical applications, one often considers the conductance only over a cut. A common generalization of conductance is to handle the case of weights assigned to the edges: then the weights are added; if the weight is in the form of a resistance, then the reciprocal weights are added.
The notion of conductance underpins the study of percolation in physics and other applied areas; thus, for example, the permeability of petroleum through porous rock can be modeled in terms of the conductance of a graph, with weights given by pore sizes.
Conductance also helps measure the quality of a Spectral clustering. The maximum among the conductance of clusters provides a bound which can be used, along with inter-cluster edge weight, to define a measure on the quality of clustering. Intuitively, the conductance of a cluster (which can be seen as a set of vertices in a graph) should be low. Apart from this, the conductance of the subgraph induced by a cluster (called "internal conductance") can be used as well.
Markov chains.
For an ergodic reversible Markov chain with an underlying graph "G", the conductance is a way to measure how hard it is to leave a small set of nodes. Formally, the conductance of a graph is defined as the minimum over all sets formula_9 of the capacity of formula_9 divided by the ergodic flow out of formula_9. Alistair Sinclair showed that conductance is closely tied to mixing time in ergodic reversible Markov chains. We can also view conductance in a more probabilistic way, as the minimal probability of leaving a small set of nodes given that we started in that set to begin with. Writing formula_12 for the conditional probability of leaving a set of nodes S given that we were in that set to begin with, the conductance is the minimal formula_12 over sets formula_9 that have a total stationary probability of at most 1/2. 
Conductance is related to Markov chain mixing time in the reversible setting. 