From Big Data to Ramanujan: expander graphs

A visual and conceptual journey guided by the image of a 3-regular expander

Starting Node: Why Look at Graphs in Big Data?

In the classes I teach on Big Data and Graphs, one of the topics covered is regular graphs. These networks, where each node has exactly the same number of connections, seem simple at first glance but hide extraordinary behaviors. What often surprises people is that structures with such low link density can be incredibly efficient at transmitting information, distributing tasks, or resisting failures. Based on that idea, I built this article as a guided journey, like a directed acyclic graph: no cycles, a clear direction, where each concept naturally leads to the next. This is applied here to a regular graph that is not a DAG, but rather an undirected and cyclic graph. I use the idea of a “DAG” as a metaphor for progression, not for the object represented, because this article revolves around a specific image that clearly illustrates many of the ideas we explore theoretically.

DAG and Graph

Show original animation

Source: Own elaboration

Central Node: The Image That Guides Everything

Topology and Spectrum of a 3-Regular Expander

Source: Own elaboration

The image accompanying this article is divided into two parts. On the left, we see a 3-regular graph with 50 nodes. Each node has exactly three connections, represented by lines of different colors. The colors of the nodes indicate their eigenvector centrality: a value that reflects how structurally important they are to the network. This spectral metric reveals which nodes are better positioned to influence the flow of information. Despite the lack of large hubs or concentrations of links, the graph remains clearly cohesive.

But beyond its functionality, this graph also has undeniable visual value. The curved lines, gradual colors, informal symmetry: all contribute to an aesthetic feeling reminiscent of geometric artwork or natural visualizations. Its beauty is not decorative; it arises from its internal structure. In this sense, graphs are a bridge between utility and art: they are algorithms that look good. And this is not anecdotal. In data science, a good visualization can reveal invisible patterns. The way a network is drawn can help us understand its behavior—and also communicate it. This graph not only functions—it’s also visually compelling.

The plot shows adjacency eigenvalues with a semicircular comparison curve. For fixed degree, such as d = 3, the limiting spectral density of random regular graphs is Kesten–McKay. Wigner’s semicircle arises as the degree grows, with appropriate normalisation. A 50-vertex sample does not establish a limiting law.

Intermediate Node: The Expander Paradox

This graph is an example of what’s known as an expander: a network that, despite having few connections per node, is very difficult to fragment. Local connectivity is low, but global connectivity is high. Practically speaking, this means that an expander allows for robust and efficient information distribution without the need to invest in redundant links. There are no single routes or critical dependencies: any node quickly connects to the rest of the graph. This paradox—low density, high cohesion—is what makes expanders so valuable for theoretical computer science, network design, data encoding, and distributed computing.

Analysis Node: Eigenvalues as a Tool

The unnormalised adjacency matrix has principal eigenvalue $d$; its spectral gap is $d-\lambda_2$. The asymptotic Alon–Boppana bound includes the factor 2: for degree 3, $2\sqrt{2}\approx2.83$. A Ramanujan graph requires $|\lambda|\leq2\sqrt{d-1}$ for every nontrivial eigenvalue, excluding $d$ and, when applicable, $-d$. The image alone does not verify this condition.

Historical Node: Ramanujan, Wigner, and a Famous Bet

Ramanujan graphs are named after a technical result derived from the number theory of Srinivasa Ramanujan, which enabled the construction of optimal expanders using advanced algebraic tools. However, for many years, they were believed to be extremely difficult to find. Peter Sarnak and Noga Alon, two prominent mathematicians in this field, made an informal bet in the 1980s: how common are Ramanujan graphs among all regular graphs? Sarnak believed they were rare, the product of sophisticated construction. Alon, on the other hand, suspected they were common in randomness.

Huang, McKenzie and Yau proved universality of the extreme eigenvalues. Approximately 69% of random regular graphs of fixed degree are Ramanujan in the limit of many vertices. This is not a guarantee for any particular 50-vertex graph.

Image: Circular Dance of the Spectrum: Eigenvalues of a 3-Regular Expander

Show original animation

Source: Own elaboration

The radial plot presents the eigenvalue histogram and a comparison curve. Its visual value connects topology and spectrum; quantitative interpretation at fixed degree should use Kesten–McKay.

Applied Node: Why This Matters in Big Data

The discovery isn’t just theoretical. In practice, graphs like this enable the construction of more efficient distributed systems, networks more resistant to failures, and faster algorithms. In Big Data environments, where millions of operations must coordinate without saturation or interruptions, expanders offer a way to interconnect processes by minimizing links but maximizing global efficiency. This idea also applies to neural networks, cryptographic protocols, and the design of circuits and supercomputers. The beauty is that these systems don’t depend on having many resources, but on having a well-thought-out—or even well-randomized—structure.

How Flow Expands in a Regular Network

Show original animation

Source: Own elaboration

The final visualization shows, step by step, how flow spreads from a source node in a 3-regular expander. Node 0 remains fixed on the left, while its three first-level neighbors (nodes 42, 38, and 33) appear in the central column. On the right are the second-level neighbors: 13, 15, 19, 20, 26, and 39. At first, we only see the nodes, but then the edges are drawn progressively: first those connecting node 0 with its immediate neighbors, then the links from each of those to their own neighbors. This visually materializes two-hop propagation: with just three connections per node, the flow quickly reaches multiple destinations. The aesthetic choices—dark background, cyan nodes with black labels, white frame, and illuminated edges—reinforce the message. Even in a graph as sparse as this, the flow is distributed evenly and without bottlenecks. Together, this sequence not only explains the structure of a 3-regular expander but makes it tangible: you see how the “data river” branches out and efficiently reaches the rest of the network.

Terminal Node A: Technical Glossary

• Regular graph: all nodes have the same number of connections (degree).
• Expander: graph with low local but high global connectivity.
• Eigenvalues: numbers derived from the adjacency matrix revealing structural properties of the graph.
• λ₂: second-largest eigenvalue, key indicator of expansion.
• Ramanujan graph: a d-regular graph whose nontrivial eigenvalues satisfy $|\lambda|\leq2\sqrt{d-1}$.
• Wigner’s semicircle law: statistical distribution followed by eigenvalues of many random matrices.

Terminal Node B: Bibliography and Conceptual Base

Huang, McKenzie and Yau · Ramanujan Property and Edge Universality of Random Regular Graphs (2025)

Bauerschmidt, Huang and Yau · Local Kesten–McKay law for random regular graphs

• Quanta Magazine (2025): “New Proof Settles Decades-Old Bet About Connected Networks”
• Noga Alon & Peter Sarnak, expander graph theory
• Horng-Tzer Yau, Jiaoyang Huang, and Theo McKenzie, proof of universality in regular graphs
• Big Data & Graph Theory Lectures, 2024 course

Epilogue

Like a directed acyclic graph, this journey had a clear path with no turning back. We started with a simple image, delved into theory, traveled through a mathematical history, and arrived at a concrete conclusion with practical implications. Today, that image—with its modest nodes and minimal connections—can no longer be seen the same way: it’s a gateway to one of the most powerful and elegant concepts in modern graph theory. And not just for its efficiency, but also for its beauty. Because in graphs, as in knowledge, structure is also a form of art.