Expander Graph
An expander graph is an undirected multigraph that is sparse but has strong connectivity
Properties of expander graphs
- If there are two large and non-overlapping groups of nodes in a graph, the probability that there’s an edge connecting them is high
- The neighborhood of a small group of nodes is larger than the group itself
- Expander graphs always contain Hamiltonian Cycles as proven by Sudakov et. al
c-Expander
An expander graph is a c-Expander when the neighborhood of a node group A is c times larger than A
Applications
- Online social networks make use of expander graphs
- Expanders are used in error-correcting codes
- Random algorithms can be optimized using expander graphs