Finding Shortcuts

Begin with a two-dimensional square lattice, a checkerboard, where each vertex links to its four nearest neighbors. Now add long-distance connectors, but do not add these purely at random. For each vertex, assign a rank to all the possible destinations for your shortcut link, and as would a highway planner, base your rankings on how far the shortcut extends from the source vertex.

The probability of choosing a vertex at distance d is proportional to d—r, where r is an additional parameter of your model. If you set r equal to 0, then you select all destinations at all distances with uniform probability, and your model is now just a two-dimensional array of the Watts-Strogatz model. If r is large, now you have the best chances of choosing only nearby destinations, and you have barely altered the original form of the lattice. The crucial value turns out to be r = 2, when the probability obeys an inverse-square law.

We can easily traverse graphs where r = 2, not because they have the smallest diameters (they don't) but because we have an algorithm for finding a short path through them. The algorithm is our simple 'greedy' one. To find a route from node a to node b, list all the edges emanating from a, and then choose the edge that takes you closest to b, measure lattice distance (you do this when reading a road map). Now repeat the same map reading sequence beginning again from this intermediate point, and continue sequencing from point to point until you reach your destination. The greedy algorithm being most efficient when r = 2 determines the spectrum of edge lengths. No other algorithm performs better than the greedy algorithm at any other value of r. When r = 0, paths having fewer steps exist, but we cannot find them; when r is large, the best route to take is unlikely to be much shorter than a path you'd take over strictly local links. Freeways are not good for traveling only a few blocks.

0 0

Post a comment