Conductance (graph)
Encyclopedia
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 walk
s
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
are the entries of the adjacency matrix
for G, so that
is the total number (or weight) of the edges incident with S.
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.
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.
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
of the capacity
of
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 minimal probability of leaving a small set of nodes given that we started in that set to begin with. Writing
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 
over sets 
that have a total stationary probability of at most 1/2.
Conductance is related to Markov chain mixing time
in the reversible setting.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
the conductance of a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
G=(V,E) measures how "well-knit" the graph is: it controls how fast a random walk
Random walk
A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the...
on G converges to a uniform distribution. The conductance of a graph is often called the Cheeger constant
Cheeger constant (graph theory)
In mathematics, the Cheeger constant of a graph is a numerical measure of whether or not a graph has a "bottleneck"...
of a graph as the
analog of its counterpart
Cheeger constant
In Riemannian geometry, the Cheeger isoperimetric constant of a compact Riemannian manifold M is a positive real number h defined in terms of the minimal area of a hypersurface that divides M into two disjoint pieces of equal volume...
in spectral geometry
Spectral geometry
Spectral geometry is a field in mathematics which concerns relationships between geometric structures of manifolds and spectra of canonically defined differential operators. The case of the Laplace–Beltrami operator on a closed Riemannian manifold has been most intensively studied, although other...
. Since electrical networks are intimately related to random walk
Random walk
A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the...
s
with a long history in the usage of the term "conductance", this alternative name helps avoid possible confusion.
The conductance of a cut
Cut (graph theory)
In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cut-set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are in its cut-set.In an unweighted undirected graph, the...
in a graph is defined as:where the
are the entries of the adjacency matrixAdjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
for G, so that
is the total number (or weight) of the edges incident with S.
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.
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
Percolation
In physics, chemistry and materials science, percolation concerns the movement and filtering of fluids through porous materials...
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.
Markov chains
For an ergodic reversible Markov chainMarkov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
with an underlying graph
Graph (data structure)
In computer science, a graph is an abstract data structure that is meant to implement the graph and hypergraph concepts from mathematics.A graph data structure consists of a finite set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices...
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
of the capacityFlow network
In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are...
of
divided by the ergodic flow out of . Alistair SinclairAlistair Sinclair
Alistair Sinclair is a British computer scientist and computational theorist.Sinclair received his B.A. in Mathematics from St. John’s College, Cambridge in 1979, and his Ph.D. in Computer Science from the University of Edinburgh in 1988 under the supervision of Mark Jerrum...
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
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 over sets that have a total stationary probability of at most 1/2.Conductance is related to Markov chain mixing time
Markov chain mixing time
In probability theory, the mixing time of a Markov chain is the time until the Markov chain is "close" to its steady state distribution.More precisely, a fundamental result about Markov chains is that a finite state irreducible aperiodic chain has a unique stationary distribution π and,...
in the reversible setting.