This applet demonstrates search in a 2D world. Nodes are laid out approximately (so that the edges don't exactly overlap) on a 2D grid and are connected to their 4 closest neighbors. In addition, each node selects one other node to connect to, with probability inversely proportional to the distance to that node (i.e. 1/(distance)²). If the chosen node is out of bounds, the edge is not shown.

You can find a path between two randomly chosen nodes by clicking on the 'find path' button. The starting point is shown in green, the target in red. The algorithm always chooses the neighbor closest to the target as the next link in the chain. The path is plotted out and the total number of steps taken is shown below. As with all Guess applets you can pan by holding down the left mouse button and dragging the mouse, and zoom in and out by moving the mouse while holding down the right mouse button.

You can also experiment with networks where the probability of long range range links is 1/(distance) or 1/(distance)⁴

Note that this network is really too small to realistically show the dependence between the network structure and search speed for large networks. Rather it may just suggest how things may behave .

The relationship between spatial network structure and search is beautifully explained in Jon Kleinberg's short paper: Navigation in a Small World.

troubleshooting:

This URL should have popped up a window with something that looks like:

If you're not seeing it, make sure you are allowing pop-ups, and that you have Java 1.4+.