graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

the conductance of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

measures how "well-knit" the graph is: it controls how fast a

random walk In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space. An elementary example of a random walk is the random walk on the integer number line \mathbb Z ...

on converges to its

stationary distribution Stationary distribution may refer to: * A special distribution for a Markov chain such that if the chain starts with its stationary distribution, the marginal distribution of all states at any time will always be the stationary distribution. Assum ...

. The conductance of a graph is often called the

Cheeger constant In Riemannian geometry, the Cheeger isoperimetric constant of a compact Riemannian manifold ''M'' is a positive real number ''h''(''M'') defined in terms of the minimal area of a hypersurface that divides ''M'' into two disjoint pieces. In 1970, J ...

of a graph as the analog of its counterpart in

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 m ...

. Since

electrical networks An electrical network is an interconnection of electrical components (e.g., batteries, resistors, inductors, capacitors, switches, transistors) or a model of such an interconnection, consisting of electrical elements (e.g., voltage sources, ...

are intimately related to

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 may refer to: Common uses * The act of cutting, the separation of an object into two through acutely-directed force ** A type of wound ** Cut (archaeology), a hole dug in the past ** Cut (clothing), the style or shape of a garment ** Cut (ea ...

(S, \bar S)

in a graph is defined as: :

\varphi(S) = \frac

where the are the entries of the

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...

for , so that :

a(S) = \sum_ \sum_ a_

is the total number (or weight) of the edges incident with . 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_\varphi(S).

Equivalently, conductance of a graph is defined as follows: :

\phi(G) := \min_\frac.\,

For a -regular graph, the conductance is equal to the

isoperimetric number In mathematics, the Cheeger constant (also Cheeger number or isoperimetric number) of a graph is a numerical measure of whether or not a graph has a "bottleneck". The Cheeger constant as a measure of "bottleneckedness" is of great interest in man ...

divided by .

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 (from Latin ''percolare'', "to filter" or "trickle through"), in physics, chemistry and materials science, refers to the movement and filtering of fluids through porous materials. It is described by Darcy's law. Broader applicatio ...

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 In multivariate statistics, spectral clustering techniques make use of the spectrum (eigenvalues) of the similarity matrix of the data to perform dimensionality reduction before clustering in fewer dimensions. The similarity matrix is provided as ...

. 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 In mathematics, ergodicity expresses the idea that a point of a moving system, either a dynamical system or a stochastic process, will eventually visit all parts of the space that the system moves in, in a uniform and random sense. This implies tha ...

reversible

Markov chain A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...

with an underlying

''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 In mathematics, ergodic flows occur in geometry, through the geodesic and horocycle flows of closed hyperbolic surfaces. Both of these examples have been understood in terms of the theory of unitary representations of locally compact groups: if � ...

out of

S

Alistair Sinclair :' Alistair Sinclair (born 1960) 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 Edinbu ...

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 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 ...

in the reversible setting.

References

* * *{{cite book , author=Fan Chung , authorlink = Fan Chung , title=Spectral Graph Theory , series=CBMS Lecture Notes , volume=92 , publisher=AMS Publications , date=1997 , isbn=0-8218-0315-8 , page=212 * 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 ''Markov Chains and Mixing Times'' is a book on Markov chain mixing times. The second edition was written by David A. Levin, and Yuval Peres. Elizabeth Wilmer was a co-author on the first edition and is credited as a contributor to the second edi ...

Markov processes Algebraic graph theory Matrices Graph invariants

Generalizations and applications

Markov chains

See also

References