Interpolate Between Extremes

Strogatz interpolated and found that his modified graphs described well many diverse situations (Ref: Small World Networks). He began with a regular ring lattice and then 'rewired' some of the edges to introduce randomness. To do this, examine each edge of an original lattice in turn. Either leave the edge as you find it or redirect the edge to another randomly chosen location. Your decision to rewire an edge is governed solely by a probability p, which you adjust over the range from 0 to 1. If p equals 0, you leave the edge alone, and the lattice remains unchanged. If p equals one, you transform your lattice into a random graph.

In analyzing their rewired lattice graphs, Watts and Strogatz did not examine the shortest path between the most distant vertices, the diameter of the graph. They studied the minimum path length L averaged over all pairs of vertices. They found the minimum length of a path changed markedly as rewiring probability increased, and they rewired more and more edges. L is at its maximum in the regular lattice, but L falls steeply after rewiring just a few edges.

0 0

Post a comment