powered by NetLogo

view/download model file: SmallWorldSearch.nlogo

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)

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).

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.

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

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.

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

; written by Eytan Bakshy ; slightly modified by Lada Adamic turtles-own [had-msg?] globals [t sender target dist-list lattice-density max-search-length av-search-length sumdist numdist] to setup clear-all reset-ticks set lattice-density 2 set max-search-length world-width set sumdist 0 set numdist 0 set-current-plot "Travel Time Counts" set-plot-x-range 0 world-width / 2 set-current-plot "Mean Travel Time" set-plot-x-range 0 world-width / 2 ask patches with [(pxcor) mod lattice-density = 0 and (pycor) mod lattice-density = 0] [ sprout 1 [set color yellow]] ask turtles [ set shape "circle" set color blue + 2 ; create-links-with turtles-on patches at-points (list (list 0 lattice-density) (list lattice-density 0)) [set color grey] create-links-with other turtles with [distance myself <= lattice-density] [set color white] ] make-long-range-ties set dist-list n-values (max-search-length + 1) [ [] ] end to make-long-range-ties ask turtles [ let turtle-dist-pairs [(list ((abs distance myself) ^ (0 - r)) self)] of other turtles let total-dist sum map [first ?] turtle-dist-pairs foreach turtle-dist-pairs [ if random-float 1.0 < (first ? / total-dist) [if not link-neighbor? (last ?) [create-link-with last ? [set color gray + 2] stop] ] ] ] end to send-message-to [my-target] let nearest-virgin min-one-of (link-neighbors with [not had-msg?]) [distance my-target] let passer ifelse-value (nearest-virgin = nobody) [nearest-virgin] [min-one-of (link-neighbors) [distance my-target]] ask passer [ if my-target = self or t > max-search-length [ set sumdist sumdist + t set numdist numdist + 1 set size 4 stop] set color blue set label t ask link-with myself [ set color blue set thickness 2 ] set t t + 1 display send-message-to my-target ] end to select-targets ask one-of turtles [ set sender self set color green set size 2 ] ask one-of turtles with [self != sender] [ set target self set color red set size 2 ] end to go set t 1 ask links [set thickness 0 set color white set label ""] ask links with [link-length > lattice-density] [set color gray + 2] ask turtles [set color blue + 2 set size 1 set label "" set had-msg? false] select-targets ask sender [send-message-to target] display do-plot end to do-plot let dist [distance sender] of target set dist-list replace-item (t - 1) dist-list (fput dist (item (t - 1) dist-list)) set av-search-length sumdist / numdist set-current-plot "Mean Travel Time" plot-pen-reset let i 0 foreach but-last dist-list [ if ? != [] [plotxy i (mean ?)] set i i + 1 ] let j 0 set-current-plot "Travel Time Counts" plot-pen-reset auto-plot-off let unity max (map [length ?] dist-list) foreach but-last (map [length ?] dist-list) [ plotxy j ? / unity set j j + 1 ] end