5
$\begingroup$

From Wikipedia

Intuitively, an expander is a finite, undirected multigraph in which every subset of the vertices "which is not too large" has a "large" boundary. Different formalisations of these notions give rise to different notions of expanders: edge expanders, vertex expanders, and spectral expanders, as defined below.

A disconnected graph is not an expander, since the boundary of a connected component is empty. Every connected graph is an expander; however, different connected graphs have different expansion parameters. The complete graph has the best expansion property, but it has largest possible degree. Informally, a graph is a good expander if it has low degree and high expansion parameters.

Edge expansion

The edge expansion (also isoperimetric number or Cheeger constant) h(G) of a graph G on n vertices is defined as $$ h(G) = \min_{0 < |S| \le \frac{n}{2} } \frac{|\partial(S)|}{|S|}\,, $$ where the minimum is over all nonempty sets S of at most n/2 vertices and $\partial(S)$ is the edge boundary of S, i.e., the set of edges with exactly one endpoint in S.

Vertex expansion

The vertex isoperimetric number $h_{\text{out}}(G)$ (also vertex expansion or magnification) of a graph G is defined as $$ h_{\text{out}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|}\,,$$

where $\partial_{\text{out}}(S)$ is the outer boundary of S, i.e., the set of vertices in $V(G)\setminus S$ with at least one neighbor in S.

  1. "an expander is a finite, undirected multigraph in which every subset of the vertices which is not too large has a large boundary." How is an expander formally defined?
  2. Do the edge and vertex expansions measure how good a expander is, and/or how connected a graph is, and/or something else?
  3. How are the edge and vertex expansions related to the degrees, as in "a graph is a good expander if it has low degree and high expansion parameters"?

Thanks and regards!

$\endgroup$
  • 1
    $\begingroup$ Not sure if it addresses all your questions, but you should check out Peter Sarnak's What is an expander? $\endgroup$ – user52274 Dec 8 '12 at 20:41
  • $\begingroup$ Thanks, @dan! Is it correct that the expansion (the quantity) has nothing to do with the sparseness of the graph, does it? $\endgroup$ – Tim Dec 9 '12 at 0:01
  • $\begingroup$ The expansion is actually quite similar to the sparsest cut in a graph. For a $d$-regular graph $G = (V,E)$ with $|V| = n$, the sparsity of a cut $S$ is defined as $$\phi(S) = \frac{E(S, V-S)}{\frac{d}{n}\cdot|S|\cdot|V-S|}$$ where $E(S,V-S)$ is the number of edges crossing the cut. The sparsest cut, $\phi(G)$, is the minimum $\phi(S)$ over all subsets $S \subseteq V$. $\endgroup$ – Xin Yuan Li May 7 '18 at 21:27
1
$\begingroup$

From Graph Theory by Hall:

An $(n,k,c)$-expander is an $X,Y$-bipartite graph $G$ with $|X| = |Y| = n$ such that $\Delta(G) \leq k$ and that $|N(S)| \geq (1 + c(1-|S|/n))\cdot |S|$ for every $S \subseteq X$ with $|S| \leq n/2$.

Here Hall uses $\Delta(G)$ to represent the maximum degree in $G$ and $N(S)$ to represent the neighbour set of $S \subseteq V$.

To answer parts two and three of your question:

  1. Edge/vertex expansion is a measure of how evenly you can divide a graph in two. Intuitively you might try to use the minimum cut or a cut which partitions the nodes into two roughly equal sized pieces but there exists graphs for which these heuristics perform poorly. The edge expansion is sort of a combination of these two heuristics. A graph with small edge expansion has a cut with few crossing edges and divides the vertices approximately in-half. See the OCW course Topics in Theoretical Computer Science: An Algorithmist's Toolkit (Lecture 3) for more detail (what the lecturer calls cut-ratio is essentially the same as edge expansion; it just hasn't been normalized).
  2. Hopefully you see how the degree figures into the discussion now from the definition. To get the edge expansion you have to divide by the degree (typically when we talk about expansions, our underlying graph is regular).
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.