Conductance (graph theory)

Definition

For undirected d-regular graphs ${\displaystyle G}$ without edge weights, the conductance ${\displaystyle \phi (G)}$ is equal to the Cheeger constant ${\displaystyle h(G)}$ divided by d, that is, we have ${\displaystyle \phi (G)=h(G)/d}$.

More generally, let ${\displaystyle G}$ be a directed graph with ${\displaystyle n}$ vertices, vertex set ${\displaystyle V}$, edge set ${\displaystyle E}$, and real weights ${\displaystyle a_{ij}\ge 0}$ on each edge ${\displaystyle ij\in E}$. Let ${\displaystyle S\subseteq V}$ be any vertex subset. The conductance ${\displaystyle \phi (S)}$ of the cut ${\displaystyle (S,\overline{S})}$ is defined via$${\displaystyle \phi (S)=\frac{{\displaystyle a(S,\overline{S})}}{min(\mathrm{v}\mathrm{o}\mathrm{l}(S),\mathrm{v}\mathrm{o}\mathrm{l}(\overline{S}))},}$$where$${\displaystyle a(S,T)=\sum _{i\in S}\sum _{j\in T}{a}_{ij},}$$and so ${\displaystyle a(S,\overline{S})}$ is the total weight of all edges that are crossing the cut from ${\displaystyle S}$ to ${\displaystyle \overline{S}}$ and$${\displaystyle \mathrm{v}\mathrm{o}\mathrm{l}(S)=a(S,V)=\sum _{i\in S}\sum _{j\in V}{a}_{ij}}$$is the volume of ${\displaystyle S}$, that is, the total weight of all edges that start at ${\displaystyle S}$. If ${\displaystyle \mathrm{v}\mathrm{o}\mathrm{l}(S)}$ equals ${\displaystyle 0}$, then ${\displaystyle a(S,\overline{S})}$ also equals ${\displaystyle 0}$ and ${\displaystyle \phi (S)}$ is defined as ${\displaystyle 1}$.

The conductance ${\displaystyle \phi (G)}$ of the graph ${\displaystyle G}$ is now defined as the minimum conductance over all possible cuts:$${\displaystyle \phi (G)=\underset{S\subseteq V}{min}\phi (S).}$$Equivalently, the conductance satisfies$${\displaystyle \phi (G)=min\left\{\frac{a(S,\overline{S})}{\mathrm{v}\mathrm{o}\mathrm{l}(S)}:\mathrm{v}\mathrm{o}\mathrm{l}(S)\le \frac{\mathrm{v}\mathrm{o}\mathrm{l}(V)}{2}\right\}.}$$

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 ${\displaystyle S}$ of the capacity of ${\displaystyle S}$ divided by the ergodic flow out of ${\displaystyle 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 probability of leaving a set of nodes given that we started in that set to begin with. This may also be written as

${\displaystyle \mathrm{\Phi }=\underset{S\subseteq V,0<\pi (S)\le \frac{1}{2}}{min}{\mathrm{\Phi }}_S=\underset{S\subseteq V,0<\pi (S)\le \frac{1}{2}}{min}\frac{\sum _{x\in S,y\in \overline{S}}\pi (x)P(x,y)}{\pi (S)},}$

where ${\displaystyle \pi }$ is the stationary distribution of the chain. 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 ${\displaystyle P(y,y)\ge 1/2}$ for all states ${\displaystyle y}$ and an initial state ${\displaystyle x\in \mathrm{\Omega }}$,

${\displaystyle \frac{1}{4\mathrm{\Phi }}\le {\tau }_x(\delta )\le \frac{2}{{\mathrm{\Phi }}^2}(\ln \pi (x{)}^{-1}+\ln {\delta }^{-1})}$.