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

;
;
; You can refer to this model as:
; http://projects.si.umich.edu/netlearn/NetLogo4/SmallWorldSearch.html

## PROCEDURES

```; written by Eytan Bakshy

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]]
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
[
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)
[create-link-with last ? [set color gray + 2] stop]
]
]
]
end

to send-message-to [my-target]
let passer ifelse-value (nearest-virgin = nobody)
[nearest-virgin]
[
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
[
set color blue
set thickness 2
]

set t t + 1
display
send-message-to my-target
]
end

to select-targets
[
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 turtles [set color blue + 2 set size 1 set label "" set had-msg? false]
select-targets
[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

```