Lattice Model

The simplest of all graphs are highly regular lattices in which every vertex joins to just a few neighbors. 'Lattice' brings to mind a two-dimensional square grid, but a lattice graph may have other geometries. A minimal lattice is a one-dimensional structure, like a chorus line with dancers holding hands. Bringing this linear lattice line into a circle and joining its two ends forms a ring lattice or cycle. A nearest-neighbor ring lattice with n vertices has n edges, (each dancer is a vertex) and every vertex has degree 2, meaning that two edges meet at each vertex. When edges extend both to nearest neighbors and to next-nearest neighbors, the ring has 2n edges and vertices of degree 4. A ring lattice is a poor example of a small-world graph. It is suitably sparse, having just n edges in the nearest-neighbor case, so in one sense it is highly clustered, because all its edges are 'local.' But the diameter of a ring graph cannot be small. The only way to traverse a ring graph is to pass from neighbor to neighbor; a lattice has too many vertices. It is like taking a streetcar that stops at all the stops along the route. One gets there faster by taxi. The diameter of the nearest-neighbor ring is n/2. This is much larger than log n.

0 0

Post a comment