Conductance (graph theory)

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.^{[citation needed]} 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 $(S,{\bar {S}})$ in a graph is defined as:

\varphi (S)={\frac {\sum _{i\in S,j\in {\bar {S}}}a_{ij}}{\min(a(S),a({\bar {S}}))}}

where the $a ij$ are the entries of the adjacency matrix for $G$ , so that

a(S)=\sum _{i\in S}\sum _{j\in V}a_{ij}

is the total number (or weight) of the edges incident with $S$ . $a (S)$ is also called a volume of the set $S\subseteq V$ .

The conductance of the whole graph is the minimum conductance over all the possible cuts:

\phi (G)=\min _{S\subseteq V}\varphi (S).

Equivalently, conductance of a graph is defined as follows:

\phi (G):=\min _{S\subseteq V;0\leq a(S)\leq a(V)/2}{\frac {\sum _{i\in S,j\in {\bar {S}}}a_{ij}}{a(S)}}.\,

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 $S$ of the capacity of $S$ divided by the ergodic flow out of $S$ . 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 $\Phi _{S}$ 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 $\Phi _{S}$ over sets $S$ that have a total stationary probability of at most 1/2.

Conductance is related to Markov chain mixing time in the reversible setting.

References

Béla Bollobás (1998). Modern graph theory. GTM. Vol. 184. Springer-Verlag. p. 321. ISBN 0-387-98488-7.
Kannan, R.; Vempala, S.; Vetta, A. (May 2004). "On clusterings: Good, bad and spectral" (PDF). J. ACM. 51 (3): 497–515. doi:10.1145/990308.990313.
Fan Chung (1997). Spectral Graph Theory. CBMS Lecture Notes. Vol. 92. AMS Publications. p. 212. ISBN 0-8218-0315-8.
A. Sinclair. Algorithms for Random Generation and Counting: A Markov Chain Approach. Birkhauser, Boston-Basel-Berlin, 1993.
D. Levin, Y. Peres, E. L. Wilmer: Markov Chains and Mixing Times

Generalizations and applications

Markov chains

See also

References