Expander graph
Encyclopedia
In combinatorics
, an expander graph is a sparse graph that has strong connectivity
properties, quantified using vertex
, edge or spectral expansion as described below. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory
, design of robust computer network
s, and the theory of error-correcting codes.
.
)
of a graph 
is defined as
where the minimum is over all nonempty sets
of at most 
vertices and 
is the edge boundary of 
, i.e., the set of edges with exactly one endpoint in 
.
(also vertex expansion or magnification) of a graph 
is defined as
where
is the outer boundary of 
, i.e., the set of vertices in 
with at least one neighbor in 
.
In a variant of this definition (called unique neighbor expansion)
is replaced by the set of vertices in 
with exactly one neighbor in 
.
The vertex isoperimetric number
of a graph 
is defined as
where
is the inner boundary of 
, i.e., the set of vertices in 
with at least one neighbor in 
.
is regular
, a linear algebra
ic definition of expansion is possible based on the eigenvalues of the adjacency matrix
of 
(where 
is the number of loops at the 
th vertex). Because 
is symmetric, the spectral theorem
implies that
has 
real-valued eigenvalues 
. Because 
is regular, 
where 
is the degree
of vertices of
. In some contexts, the spectral gap
of
is defined to be 
. In other contexts, the spectral gap is 
, where
The normalized version of this definition, where we consider the matrix
and get eigenvalues between −1 and 1, is also widely used and more convenient in the statement of some results.
Frequently one will refer to the second-largest eigenvalue of a graph G, which is the max of
and 
. Depending on the context it may be either the normalized version (taking value between 0 and 1) or the un-normalized version (taking value between 0 and d).
For not necessarily regular graphs, the spectrum of a graph can be defined similarly using its Laplacian matrix
.
of 
-regular graphs is an edge expander family if there is a constant 
such that 
for each 
. Typically we want 
to be constant, though it is sometimes also interesting to consider 
or even 
. Similarly, 
is a vertex expander family if there is a constant 
such that 
for each 
, and 
is a spectral expander family if some positive constant is a lower bound for the spectral gap of each 
.
These definitions can be extended to the case of directed graph
s. A directed graph can also be interpreted as a balanced bipartite graph
(with all edges going from one copy of
to another copy). The definition of bipartite expanders can further be generalized to the case of unbalanced bipartite graphs.
In particular, for any
-regular graph 
,
Consequently, for constant degree graphs, vertex and edge expansion are qualitatively the same.
is 
-regular, there is a relationship between 
and the spectral gap 
of 
. An inequality "due to Cheeger and Buser in the continuous case and to Tanner, Alon, and Milman in the discrete case" states that
This inequality is closely related to the Cheeger bound
for Markov chains and can be seen as a discrete version of Cheeger's inequality in Riemannian geometry
.
Similar connections between vertex isoperimetric numbers and the spectral gap have also been studied:
Asymptotically speaking, the quantities
, 
, and 
are all upper bounded by the spectral gap 
.
-regular graph has good expansion, with high probability. Ramanujan graph
s are a family of
-regular expander graphs with 
being constant and with explicit constructions, that have essentially the largest possible spectral gap. Algebraic
constructions based on Cayley graph
s are known for various variants of expander graphs. Most recently, combinatorial constructions of expanders have also been discovered.
Expander graphs have found extensive applications in computer science
, in designing algorithm
s, error correcting code
s, extractors, pseudorandom generator
s, sorting network
s and robust computer network
s. They have also been used in proofs of many important results in computational complexity theory
, such as SL
=L
and the PCP theorem
. In cryptography
, expander graphs are used to construct hash function
s.
The following are some properties of expander graphs that have proven useful in many areas.
, the number of edges between 
and 
is approximately what you would expect in a random 
-regular graph, i.e. 
.
, with high probability the average of our samples is close to the expectation of the random variable. The expander walk sampling lemma, due to and , states that this also holds true when sampling from a walk on an expander graph. This is particularly useful in the theory of derandomization, since sampling according to an expander walk uses much fewer random bits than sampling independently.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, an expander graph is a sparse graph that has strong connectivity
Connectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
properties, quantified using vertex
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
, edge or spectral expansion as described below. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, design of robust computer network
Computer network
A computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....
s, and the theory of error-correcting codes.
Definitions
There are several different ways to measure the expansion properties of a finite, undirected multigraphMultigraph
In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge....
.Edge expansion
The edge expansion (also isoperimetric number or Cheeger constantCheeger 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 is defined as
where the minimum is over all nonempty sets
of at most vertices and is the edge boundary of , i.e., the set of edges with exactly one endpoint in .Vertex expansion
The vertex isoperimetric number (also vertex expansion or magnification) of a graph is defined as
where
is the outer boundary of , i.e., the set of vertices in with at least one neighbor in .In a variant of this definition (called unique neighbor expansion)
is replaced by the set of vertices in with exactly one neighbor in .The vertex isoperimetric number
of a graph is defined as
where
is the inner boundary of , i.e., the set of vertices in with at least one neighbor in .Spectral expansion
When is regularRegular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
, a linear algebra
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
ic definition of expansion is possible based on the eigenvalues of the adjacency matrix
Adjacency 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...
of (where is the number of loops at the th vertex). Because is symmetric, the spectral theoremSpectral theorem
In mathematics, particularly linear algebra and functional analysis, the spectral theorem is any of a number of results about linear operators or about matrices. In broad terms the spectral theorem provides conditions under which an operator or a matrix can be diagonalized...
implies that
has real-valued eigenvalues . Because is regular, where is the degreeDegree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
of vertices of
. In some contexts, the spectral gapSpectral gap
In mathematics, the spectral gap is the difference between the moduli of the two largest eigenvalues of a matrix or operator; alternately, it is sometimes taken as the smallest non-zero eigenvalue. Various theorems relate this difference to other properties of the system.See:* Expander graph *...
of
is defined to be . In other contexts, the spectral gap is , whereThe normalized version of this definition, where we consider the matrix
and get eigenvalues between −1 and 1, is also widely used and more convenient in the statement of some results.Frequently one will refer to the second-largest eigenvalue of a graph G, which is the max of
and . Depending on the context it may be either the normalized version (taking value between 0 and 1) or the un-normalized version (taking value between 0 and d).For not necessarily regular graphs, the spectrum of a graph can be defined similarly using its Laplacian matrix
Laplacian matrix
In the mathematical field of graph theory the Laplacian matrix, sometimes called admittance matrix or Kirchhoff matrix, is a matrix representation of a graph. Together with Kirchhoff's theorem it can be used to calculate the number of spanning trees for a given graph. The Laplacian matrix can be...
.
Expander families
A family of -regular graphs is an edge expander family if there is a constant such that for each . Typically we want to be constant, though it is sometimes also interesting to consider or even . Similarly, is a vertex expander family if there is a constant such that for each , and is a spectral expander family if some positive constant is a lower bound for the spectral gap of each .These definitions can be extended to the case of directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
s. A directed graph can also be interpreted as a balanced bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
(with all edges going from one copy of
to another copy). The definition of bipartite expanders can further be generalized to the case of unbalanced bipartite graphs.Relationships between different expansion properties
The expansion parameters defined above are related to each other.In particular, for any
-regular graph ,Consequently, for constant degree graphs, vertex and edge expansion are qualitatively the same.
Cheeger inequalities
When is -regular, there is a relationship between and the spectral gap of . An inequality "due to Cheeger and Buser in the continuous case and to Tanner, Alon, and Milman in the discrete case" states that
This inequality is closely related to the Cheeger bound
Cheeger bound
In mathematics, the Cheeger bound is a bound of the second largest eigenvalue of the transition matrix of a finite-state, discrete-time, reversible stationary Markov chain. It can be seen as a special case of Cheeger inequalities in expander graphs....
for Markov chains and can be seen as a discrete version of Cheeger's inequality in Riemannian geometry
Riemannian geometry
Riemannian geometry is the branch of differential geometry that studies Riemannian manifolds, smooth manifolds with a Riemannian metric, i.e. with an inner product on the tangent space at each point which varies smoothly from point to point. This gives, in particular, local notions of angle, length...
.
Similar connections between vertex isoperimetric numbers and the spectral gap have also been studied:
Asymptotically speaking, the quantities
, , and are all upper bounded by the spectral gap .Examples of expanders
A random-regular graph has good expansion, with high probability. Ramanujan graphRamanujan graph
A Ramanujan graph, named after Srinivasa Ramanujan, is a regular graph whose spectral gap is almost as large as possible . Such graphs are excellent spectral expanders....
s are a family of
-regular expander graphs with being constant and with explicit constructions, that have essentially the largest possible spectral gap. AlgebraicAbstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
constructions based on Cayley graph
Cayley graph
In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...
s are known for various variants of expander graphs. Most recently, combinatorial constructions of expanders have also been discovered.
Applications and useful properties
The original motivation for expanders is to build economical robust networks (phone or computer): an expander with bounded valence is precisely an asymptotic robust graph with number of edges growing linearly with size (number of vertices), for all subsets.Expander graphs have found extensive applications in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, in designing algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s, error correcting code
Expander code
In coding theory, expander codes are a type of linear block code that arises by using bipartite expander graphs. Along with concatenated codes, expander codes are interesting since they can construct binary codes with constant positive rate and relative distance...
s, extractors, pseudorandom generator
Pseudorandom generator
In theoretical computer science, a pseudorandom generator is a deterministic procedure that produces a pseudorandom distribution from a short uniform input, known as a random seed.-Definition:...
s, sorting network
Sorting network
A sorting network is an abstract mathematical model of a network of wires and comparator modules that is used to sort a sequence of numbers. Each comparator connects two wires and sorts the values by outputting the smaller value to one wire, and the larger to the other...
s and robust computer network
Computer network
A computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....
s. They have also been used in proofs of many important results in computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, such as SL
SL (complexity)
In computational complexity theory, SL is the complexity class of problems log-space reducible to USTCON , which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the...
=L
L (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
and the PCP theorem
PCP theorem
In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity .The PCP theorem says that for some universal constant K, for every...
. In cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, expander graphs are used to construct hash function
Hash function
A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys. For example, a single integer can serve as an index to an array...
s.
The following are some properties of expander graphs that have proven useful in many areas.
Expander mixing lemma
The expander mixing lemma states that, for any two subsets of the vertices, the number of edges between and is approximately what you would expect in a random -regular graph, i.e. .Expander walk sampling
The Chernoff bound states that, when sampling many independent samples from a random variables in the range, with high probability the average of our samples is close to the expectation of the random variable. The expander walk sampling lemma, due to and , states that this also holds true when sampling from a walk on an expander graph. This is particularly useful in the theory of derandomization, since sampling according to an expander walk uses much fewer random bits than sampling independently.