Graph invariants | Matrices | Markov processes | Algebraic graph theory
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 in a graph is defined as: where the aij are the entries of the adjacency matrix for G, so that is the total number (or weight) of the edges incident with S. a(S) is also called a volume of the set . 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. (Wikipedia).
