powered by NetLogo

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


PROCEDURES

; 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