Search in a Small World

Abstract

In a graph with a "small world" topology,nodes are highly clustered yet the path length between them is small. Such a topology can make search problems very difficult since local decisions quickly propagate globally.We showthat graphs associated with many different search problems have a small world topology, and that the cost of solving such search problems can have a heavy-tailed distribution. The strategy of randomization and restarts appears to eliminate these heavy tails. A novel restart schedule in which the cutoff bound is increased geometrically appears particularly effective.