Conductance (graph theory)
In theoretical computer science, graph theory, and mathematics, the conductance is a parameter of a Markov chain that is closely tied to its mixing time, that is, how rapidly the chain converges to its stationary distribution, should it exist.
Equivalently, the conductance can be viewed as a parameter of a directed graph, in which case it can be used to analyze how quickly random walks in the graph converge.
The conductance of a graph is closely related to the Cheeger constant of the graph, which is also known as the edge expansion or the isoperimetic number.
However, due to subtly different definitions, the conductance and the edge expansion do not generally coincide if the graphs are not regular.
On the other hand, the notion of electrical conductance that appears in electrical networks is unrelated to the conductance of a graph.
The conductance was first defined by Mark Jerrum and Alistair Sinclair in 1988 to prove that the permanent of a matrix with entries from {0,1} has a polynomial-time approximation scheme.
[1] In the proof, Jerrum and Sinclair studied the Markov chain that switches between perfect and near-perfect matchings in bipartite graphs by adding or removing individual edges.
They defined and used the conductance to prove that this Markov chain is rapidly mixing.
This means that, after running the Markov chain for a polynomial number of steps, the resulting distribution is guaranteed to be close to the stationary distribution, which in this case is the uniform distribution on the set of all perfect and near-perfect matchings.
This rapidly mixing Markov chain makes it possible in polynomial time to draw approximately uniform random samples from the set of all perfect matchings in the bipartite graph, which in turn gives rise to the polynomial-time approximation scheme for computing the permanent.
For undirected d-regular graphs
without edge weights, the conductance
is equal to the Cheeger constant
vertices, vertex set
is the total weight of all edges that are crossing the cut from
, that is, the total weight of all edges that start at
is now defined as the minimum conductance over all possible cuts:
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.
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
divided by the ergodic flow out of
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 probability of leaving a set of nodes given that we started in that set to begin with.
In some literature, this quantity is also called the bottleneck ratio of G. Conductance is related to Markov chain mixing time in the reversible setting.
Precisely, for any irreducible, reversible Markov Chain with self loop probabilities
