Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Expander graph
Summary
In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.
Intuitively, an expander graph is a finite, undirected multigraph in which every subset of the vertices that 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.
The edge expansion (also isoperimetric number or Cheeger constant) h(G) of a graph G on n vertices is defined as
where
which can also be written as ∂S = E(S, ) with := V(G) \ S the complement of S and
the edges between the subsets of vertices A,B ⊆ V(G).
In the equation, the minimum is over all nonempty sets S of at most vertices and ∂S is the edge boundary of S, i.e., the set of edges with exactly one endpoint in S.
Intuitively,
is the minimum number of edges that need to be cut in order to split the graph in two.
The edge expansion normalizes this concept by dividing with smallest number of vertices among the two parts.
To see how the normalization can drastically change the value, consider the following example.
Take two complete graphs with the same number of vertices n and add n edges between the two graphs by connecting their vertices one-to-one.
The minimum cut will be n but the edge expansion will be 1.
Notice that in min , the optimization can be equivalently done either over 0 ≤ ≤ or over any non-empty subset, since .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood