Graphs Are The Swarm

The dots are robots. The lines are who can hear whom. That object has a name, a graph, and it is the single most important thing about a swarm. Change the lines and you change the behaviour, even if you don't touch a single robot.

The telephone game, with stakes

You remember the telephone game: one kid whispers to the next, and a sentence about a birthday party arrives as a rumour about a dragon. The message travels along a chain, a graph shaped like a line. Break one link and half the room never hears the end of the sentence.

A swarm plays the same game, constantly, to do something far less silly: agree on a number. A heading to fly. A rendezvous point. Which robot is the leader. Every robot starts with its own opinion and can only talk to neighbours within radio or sensing range. The structure of "who talks to whom" decides whether those opinions ever collapse into one.

So model it honestly. Each robot is a node. Each live communication link is an edge. The whole web is the communication graph, and unlike a textbook diagram, it is alive: as robots move, edges blink in and out. Two robots drift apart and their edge dies; two drift together and a new one is born. The algorithm a swarm is running, at any instant, is really the algorithm its current graph allows.

Connectivity decides everything

Here is the rule the whole field hangs on. Picture the graph splitting: shrink each robot's sensing radius far enough and one connected swarm fractures into two or more components: islands that can no longer reach each other.

Once a graph is split, count the components: that count is exactly how many separate answers the swarm will converge to. Split the graph into disconnected pieces and the swarm can never reach a single consensus. Each island agrees with itself and disagrees with the others, forever, with no way to even discover the disagreement exists.

This is why connectivity is the line between a swarm and a crowd. The hard engineering tension lives right here: you want to stay connected while spending as few edges as possible, because every edge is bandwidth, energy, and interference. A barely-connected graph (one whose every node hangs on a single thread, a spanning tree) is the cheapest one that still works, and also the most fragile. Drop one link and it shatters.

The number that grades a graph

"Connected or not" is binary, but real graphs live on a spectrum from barely to richly connected, and you'd like a single number for it. There is one, and it's beautiful.

Encode the graph as its Laplacian matrix $L = D - A$, where $A$ marks which nodes are neighbours and $D$ counts each node's neighbours. Compute its eigenvalues, sort them, and look at the second-smallest, $\lambda_2$. This is the algebraic connectivity, or Fiedler value, and it is a one-number verdict on the graph:

• $\lambda_2 = 0$ means the graph is disconnected: consensus is impossible.
• $\lambda_2 > 0$ means connected, and the larger it is, the more robustly so.

Better still, $\lambda_2$ doesn't just say whether the swarm can agree. It predicts how fast. Consensus error decays like $e^{-\lambda_2 t}$, so a graph with double the Fiedler value reaches agreement in half the time. The graph Laplacian's second eigenvalue predicts how fast the swarm can agree. One scalar, squeezed out of the wiring diagram, tells you almost everything you wanted to know about the swarm's mind.

The mathematician was Miroslav Fiedler, a Czech who published the key paper, titled simply "Algebraic connectivity of graphs," in 1973. He gave $\lambda_2$ a name and showed it measured how tightly a graph holds together, decades before anyone dreamed of pointing it at a drone swarm.

↘ The same matrix counts how many ways the swarm could stay connected

The Laplacian hides another trick that feels almost unfair. Strike out any one row and the matching column, take the determinant of what's left, and you get the exact number of spanning trees of the graph: the count of distinct minimal skeletons that keep every node connected with no edge to spare. This is Kirchhoff's theorem, also called the matrix-tree theorem.

For a swarm that number is a blunt robustness score. One spanning tree means the graph is hanging by a thread, with a single way to wire everyone together; lose any edge and it falls apart. Thousands of spanning trees means the web is thick with redundancy, with many backup paths if links die. So one matrix answers three different questions at once: is the swarm connected (count the zero eigenvalues), how fast can it agree ($\lambda_2$), and how many ways could it stay connected (the matrix-tree determinant). Not bad for a grid of plus and minus ones.

↘ The matrices, and why λ₁ is always exactly zero

Build the adjacency matrix $A$ for a graph with $n$ nodes:

$A_{ij} = \begin{cases} 1 & \text{if } (i,j) \text{ is an edge} \\ 0 & \text{otherwise} \end{cases}$

and the degree matrix $D$, a diagonal matrix holding each node's neighbour count:

$D_{ii} = \sum_j A_{ij}$

The Laplacian is their difference, $L = D - A$. It is symmetric and positive semi-definite, so its eigenvalues are real and non-negative; sort them $\lambda_1 \le \lambda_2 \le \dots \le \lambda_n$.

The smallest is always exactly zero: $\lambda_1 = 0$. The reason is lovely. The all-ones vector $\mathbf{1}$ satisfies $L\mathbf{1} = 0$, because every row of $L$ sums to (degree) minus (its own edges) $= 0$. That zero eigenvalue is the swarm saying "if everyone already agrees, nothing changes."

The real content is the multiplicity of that zero. A connected graph has exactly one zero eigenvalue, so $\lambda_2 > 0$. A graph in $k$ disconnected pieces has $k$ zeros (meaning $\lambda_2 = 0$), one independent "everyone-agrees" vector per island. The Fiedler value flips from positive to zero at the precise instant the graph falls apart.

To detect a split in code, you don't even need eigenvalues: run a depth-first search and count connected components. If the count exceeds one, $\lambda_2 = 0$ and consensus is off the table.

Key takeaways

• A swarm is a graph: robots are nodes, live communication links are edges, and the graph is alive, with edges appearing and vanishing as robots move.
• Connectivity is non-negotiable. A disconnected graph splits the swarm into islands that converge to different answers and can never reconcile.
• The Fiedler value $\lambda_2$, the second eigenvalue of the Laplacian $L = D - A$, grades the graph: zero means disconnected, larger means faster consensus ($\text{error} \propto e^{-\lambda_2 t}$).
• Design the graph and you've designed the behaviour, usually by controlling geometry, not hardware.