Search in a Small World (Kleinberg's model)

created with NetLogo. Setup will take a bit of time, please be patient.

view/download model file: SmallWorldSearch.nlogo

WHAT IS IT?

This is Kleinberg's model of small world search. While the Watts Strogatz small world model showed how a few random connections added to a regular lattice can dramatically reduce average path lenthgs, it did not explain why individual are able to navigate such links effectively using simple greedy strategies. These strategies may be something like "pick one of my friends who is closest to the target".

In Kleinberg's model, nodes are arranged on a lattice. Each node is connected to its 4 closest neighbors, and the lattice wraps around. In addition, each node gets one "long range" link, and links to another node with probability proportional to the euclidean distance d to the -rth power. i.e. p(e(n1,n2)) ~ (dist(n1,n2))^(-r)


HOW IT WORKS

After setting up the lattice and long-range links using the SETUP command, you can start running the search algorithm. To run it once, select GO ONCE, to run it repeatedly, select GO. A starting point and target are chosen at random. At each point, the algorithm checks whether it has reached the target. If it hasn't, it picks a link neighbor of the current node that it hasn't visited before that is closest . If all the link neighbors have been visited at least once, it picks the visited link-neighbor that is closest to the target.

There are two plots. One shows the average number of steps it takes to reach a target at a given lattice distance. The second plot shows a histogram of the search times (number of steps).


HOW TO USE IT

The r slider controls whether long range (low r) or short range (high r) links are more likely. Choose an r and press SETUP.

Then simply press GO and observe the mean search time, as well as how it varies with distance from source to target.

Keep varying r, trying to find the optimum that will give the shortest search time.


THINGS TO NOTICE

Note that even though r = 0 gives the most long-range shortcuts, it does not give the shortest search time.


NETWORK CONCEPTS

In this model we constructed a special kind of small world network -- one where the probability of long range links depends on their length. We saw that these long range links shorten the average path length, but that the navigability of these ties depends how localized they are.


CREDITS AND REFERENCES

The model used here was originally published in:
J. Kleinberg. Navigation in a small world, Nature,
406:845 (2000)

; Copyright 2008 by Eytan Bakshy, Lada Adamic.
;
; This model is licensed under a Creative Commons Attribution 3.0 License.
; http://creativecommons.org/licenses/by/3.0/
;
; You can refer to this model as:
; http://projects.si.umich.edu/netlearn/NetLogo4/SmallWorldSearch.html