Conductance (probability)

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 a uniform 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 ${\displaystyle (S,{\bar {S}})}$ in a graph is defined as:

where the ${\displaystyle a_{ij}}$ are the entries of the adjacency matrix for G, so that

...
Wikipedia