Expander Graphs and their Applications
By Shlomo Hoory. 2006
2,009 citations recorded by the source corpus.
A major consideration we had in writing this survey was to make it accessible to mathematicians as well as to computer scientists, since expander graphs, the protagonists of our story, come up in numerous and often surprising contexts in both fields. But, perhaps, we should start with a few words about graphs in general. They are, of course, one of the prime objects of study in Discrete Mathematics. However, graphs are among the most ubiquitous models of both natural and human-made structures. In the natural and social sciences they model relations among species, societies, companies, etc. In computer science, they represent networks of communication, data organization, computational devices as well as the flow of computation, and more. In mathematics, Cayley graphs are useful in Group Theory. Graphs carry a natural metric and are therefore useful in Geometry, and though they are “just” one-dimensional complexes, they are useful in certain parts of Topology, e.g. Knot Theory. In statistical physics, graphs can represent local connections between interacting parts of a system, as well as the dynamics of a physical process on such systems. The study of these models calls, then, for the comprehension of the significant structural properties of the relevant graphs. But are there nontrivial structural properties which are universally important? Expansion of a graph requires that it is simultaneously sparse and highly connected. Expander graphs were first defined by Bassalygo and Pinsker, and their existence first proved by Pinsker in the early ’70s. The property of being an expander seems significant in many of these mathematical, computational and physical contexts. It is not surprising that expanders are useful in the design and analysis of communication networks. What is less obvious is that expanders have surprising utility in other computational settings such as in the theory of error correcting codes and the theory of pseudorandomness. In mathematics, we will encounter e.g. their role in the study of metric embeddings, and in particular in work around the Baum-Connes Conjecture. Expansion is closely related to the convergence rates of Markov Chains, and so they play a key role in the study of Monte-Carlo algorithms in statistical mechanics and in a host of practical computational applications. The list of such interesting and fruitful connections goes on and on with so many applications we will not even
Subfields: Computational Theory and Mathematics, Electrical and Electronic Engineering, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Alexander Lubotzky
- Daniel A. Spielman
- Nikhil Srivastava
- Terence Tao
- Assaf Naor
- Adam W. Marcus
- Jure Leskovec
- David P. Woodruff
In Electrical and Electronic Engineering
- Jayadev Acharya
- Ziteng Sun
- Himanshu Tyagi
- Clément Louis Canonne
- Adam W. Marcus
- Daniel A. Spielman
- Charles Bordenave
- Alexander Lubotzky
In Algorithms & Complexity
- Jure Leskovec
- Prateek Jain
- Srinadh Bhojanapalli
- Alexander Lubotzky
- Daniel A. Spielman
- P. P. Varj'u
- Misha Gromov
- Pavel Panteleev
Citations in the corpus
- Big Bird: Transformers for Longer Sequences (2020, background): “It is well-known that random graphs are expanders and can approximate complete graphs in a number of different contexts including in their spectral properties [80, 38].”
- Representation Learning on Graphs with Jumping Knowledge Networks (2018, background): “Random walks starting inside an expander converge rapidly in O(log |V |) steps to an almost-uniform distribution (Hoory et al., 2006).”
- The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains (2012, methodology): “It has proved particularly useful for the construction of expander graphs [21], graph visualization [17, Section 16.7], spectral clustering [22], graph coloring [17, Section 16.9], and numerous other applications in chemistry, physics, and computer science (see, e.g., [23] for a recent review).”
- Provable Bounds for Learning Some Deep Representations (2013, background): “Throughout, we need well-known properties of random graphs with expected degree d, such as the fact that they are expanders (Hoory et al., 2006); these properties appear in the supplementary material.”
- Adjacency matrices of random digraphs: singularity and anti-concentration (2015, background): “In the undirected setting, expansion properties of graphs are a subject of very intense research (see, in particular, [17] and references therein).”
- Nonlinear spectral calculus and super-expanders (2012, background): “Note that if Y contains at least two points then (5) implies that {Xn}n=1 are necessarily also expanders in the classical sense (see [21, 35] for more on classical expanders).”
- THE NON-BACKTRACKING SPECTRUM OF THE UNIVERSAL COVER OF A GRAPH (2007, background): “…the Mixing Lemma for expanders states that the number of edges e ( S, T ) between any two vertex sets S , T in a d -regular graph satisfies e ( S, T ) − d | S || T | /N ≤ λ 2 | S || T | , where λ 2 is the second largest eigenvalue in absolute value (see [22] for a survey on expander graphs).”
- Expansion in $SL_d(O_K/I)$, $I$ square-free (2010, background): “Hoory, Linial and Widgerson [21] for a recent survey of expanders and their applications) and recently they found remarkable applications in pure mathematics as well (see Bourgain, Gamburd and Sarnak [8] and Long, Lubotzky and Reid [23]).”
- Entropy and isoperimetry for linear and non-linear group actions (2008, background): “) (b) The isoperimetric inequalities for iterated wreath products of finite groups and graphs (see [9]) and their modifications provide examples of graphs with expandertype isoperimetry (see [19]).”
- Spectra of subdivision-vertex and subdivision-edge neighbourhood coronae (2012, background): “, is called a family of ε-expander graphs [9], where ε > 0 is a fixed constant, if (i) all these graphs are k-regular for a fixed integer k ≥ 3; (ii) a(Gi) ≥ ε for i = 1, 2, 3, .”
- Transition from Tracy–Widom to Gaussian fluctuations of extremal eigenvalues of sparse Erdős–Rényi graphs (2017, background): “To mention some, we refer the readers to the books [9, 11] for a general discussion on spectral graph theory, the survey article [35] for the connection between eigenvalues and expansion properties of graphs, and the articles [12, 13,48, 49, 51,53, 56–58] on the applications of eigenvalues and eigen”
- Optimal and scalable distribution of content updates over a mobile social network (2009, background): “Graphs exhibiting a bounded expansion, also called expander graphs, are abundant [15], [17]; in particular, any graph with a sufficiently rich random structure is an expander.”
- Topology of random simplicial complexes: a survey (2013, background): “” (For a survey of expander graphs and their applications, see [30].”
- Expander graphs, gonality, and variation of Galois representations (2010, methodology): “We refer readers to the survey paper of Hoory, Linial and Wigderson [35] for extensive background information on expansion in graphs, in particular on expanders.”
- Size biased couplings and the spectral gap for random regular graphs (2015, background): “Results like this bounding the edge discrepancy for random regular graphs have often been of interest; see the expander mixing lemma [37], Lemma 2.”
- Expansion in SLd(Z/qZ), q arbitrary (2010, background): “Expanders have a wide range of applications in computer science (see e.g. Hoory, Linial and Widgerson [19] for a recent survey on expanders) and recently they found remarkable applications in pure mathematics as well (see Bourgain, Gamburd and Sarnak [7] and Long, Lubotzky and Reid [22]).”
- Asymptotically good Quantum and locally testable classical LDPC codes (2021, methodology): “Let us now state without proof a well-known variant of the expander mixing lemma for ( n, w, λ )- regular graphs [35, Lemma 2.5].”