COMPUTING SCIENCE

# Graph Theory in Practice: Part II

# Lattices and Random Graphs

In trying to understand very large small-world graphs, two simplified models serve as useful points of reference.

The simplest of all graph models are lattices—highly regular graphs in which every vertex is joined to a few neighbors. The term lattice brings to mind a two-dimensional square grid, but a lattice can have other geometries. The minimal lattice is a one-dimensional structure, like a row of people holding hands. Bending this linear lattice around and joining the two ends creates a ring lattice, or cycle. A nearest-neighbor ring lattice with *n* vertices has *n* edges, and every vertex has degree 2, meaning that two edges meet there. When edges extend both to nearest neighbors and to next-nearest neighbors, the ring has 2*n* edges and vertices of degree 4.

How does the ring lattice perform as a model of small-world graphs? Not terribly well. It is suitably sparse, with just *n* edges in the nearest-neighbor case, and there is a sense in which it is highly clustered, since all the edges are "local." But the diameter is not small. The only way to travel in a ring is to go from neighbor to neighbor; the lattice is like a railroad line without an express track. The diameter of the nearest-neighbor ring is *n*/2, which is much larger than log *n*.

Whereas a lattice is a very orderly graph, the other benchmark model is maximally random. The graphs in this class were first studied around 1960 by the Hungarian mathematicians Paul Erdos and Alfred Rényi. To build one of their graphs, you start with a collection of *n* vertices and no edges. Then you make a sweep through the graph, considering every possible pairing of vertices, and in each case you either draw an edge with probability *p* or do nothing with probability 1-*p*. The outcome of this process is easy to predict in the extreme cases: If *p*=0, the graph remains edgeless, and if *p*=1, the graph becomes a clique. Between the extremes, you can expect the graph to have about *pn*^{2}/2 edges, placed randomly and independently.

Erdos and Rényi proved a number of interesting results about these graphs. Most of the proofs are statements about "almost every" random graph; this sounds like a strangely vague manner of speaking for mathematical discourse, but it has a precise meaning. Saying that almost every random graph has some property *Q* means that as the size of the graph *n* goes to infinity, the probability of *Q* approaches 1. For example, Erdos and Rényi showed that if the edge probability *p* is greater than a certain threshold, then almost every random graph is connected. This doesn't mean you can't construct disconnected graphs if you set out to do so, but the random process has no chance of producing them when *n* approaches infinity.

As a model of small-world networks, the Erdos-Rényi random graph has some strengths. It can be made as dense or as sparse as necessary just by adjusting the edge probability *p*. And the diameter tends to be small (in some cases *too* small). But Erdos-Rényi graphs show no tendency to form clusters. They cannot, since the edges are placed independently, and neighbors of neighbors are no more likely to be linked than any other randomly chosen vertices.

**IN THIS SECTION**

EMAIL TO A FRIEND :

**Of Possible Interest**

**Technologue**: The Quest for Randomness

**Feature Article**: Twisted Math and Beautiful Geometry

**Feature Article**: Simulating Star Formation on a Galactic Scale