powered by NetLogo

view/download model file: SmallWorldWS.nlogo

WHAT IS IT?

This model explores the formation of networks that result in the "small world" phenomenon -- the idea that a person is only a couple of connections away any other person in the world.

A popular example of the small world phenomenon is the network formed by actors appearing in the same movie (e.g. the "six degrees of Kevin Bacon" game), but small worlds are not limited to people-only networks. Other examples range from power grids to the neural networks of worms. This model illustrates some general, theoretical conditions under which small world networks between people or things might occur.


HOW IT WORKS

This model is an adaptation of a model proposed by Duncan Watts and Steve Strogatz (1998). It begins with a network where each person (or "node") is connected to his or her two neighbors on either side.

The REWIRE-ONCE button creates the network and then visits all edges and tries to rewire them. By rewiring, we mean changing one end of a connected pair of nodes, and keeping the other end the same. The REWIRING-PROBABILITY slider determines the probability that an edge will get rewired. Running VARY REWIRING-PROBABILITY will rewire at multiple probabilities and produces a range of possible networks with varying average path lengths and clustering coefficients.

To identify small worlds, the "average path length" (abbreviated "av-path") and "clustering coefficient" (abbreviated "cc") of the network are calculated and plotted. (Note: The plots for both the clustering coefficient and average path length are normalized by dividing by the values of the initial network. The monitors give the actual values.)

Average Path Length: Average path length is calculated by finding the shortest path between all pairs of nodes, adding them up, and then dividing by the total number of pairs. This shows us, on average, the number of steps it takes to get from one member of the network to another.

Clustering Coefficient: Another property of small world networks is that from one person's perspective it seems unlikely that they could be only a few steps away from anybody else in the world. This is because their friends more or less know all the same people they do. The clustering coefficient is a measure of this "all-my-friends-know-each-other" property. This is sometimes described as the friends of my friends are my friends. More precisely, the clustering coefficient of a node is the ratio of existing links connecting a node's neighbors to each other to the maximum possible number of such links.


HOW TO USE IT

The NUM-NODES slider controls the size of the network. Choose a size and press INITIAL SETUP.

Pressing the REWIRE-ONCE button rewires the network for a given REWIRING-PROBABILITY.

Pressing the VARY REWIRING-PROBABILITY button re-creates the initial network (each node connected to its two neighbors on each side for a total of four neighbors) and rewires all the edges with varying rewiring probability, then plots the resulting network properties.


THINGS TO NOTICE

Note that for certain ranges of the fraction of nodes, the relative average path length decreases faster than the relative clustering coefficient. That is, the average path length soon reaches that of the random graph (the graph when REWIRING-PROBABILITY = 1), while the clustering coefficient more slowly descends to that value. The region when the average shortest path is close to that of a random graph while the clustering coefficient is still significantly higher than that of a random graph is when one would call the graph "small world".


THINGS TO TRY

Try plotting the values for different rewiring probabilities and observe the trends of the values for average path length and clustering coefficient. What is the relationship between rewiring probability and fraction of nodes? In other words, what is the relationship between the rewire-one plot and the rewire-all plot?

Do the trends depend on the number of nodes in the network?


EXTENDING THE MODEL

Try to see if you can produce the same results if you start with a different initial network. Create new BehaviorSpace experiments to compare results.

In a precursor to this model, Watts and Strogatz created an "alpha" model where the rewiring was not based on a global rewiring probability. Instead, the probability that a node got connected to another node depended on how many mutual connections the two nodes had. The extent to which mutual connections mattered was determined by the parameter "alpha." Create the "alpha" model and see if it also can result in small world formation.


RELATED MODELS

Diffusion in a small world:
http://projects.si.umich.edu/netlearn/NetLogo4/SmallWorldDiffusionSIS.html

Search in a small world:
http://projects.si.umich.edu/netlearn/NetLogo4/SmallWorldSearch.html

Graph coloring in a small world:
http://projects.si.umich.edu/netlearn/NetLogo4/GraphColoring.html


CREDITS AND REFERENCES

This model is adapted from:
Duncan J. Watts, Six Degrees: The Science of a Connected Age (W.W. Norton & Company, New York, 2003), pages 83-100.

The work described here was originally published in:
DJ Watts and SH Strogatz. Collective dynamics of 'small-world' networks, Nature,
393:440-442 (1998)

For more information please see Watts' website: http://smallworld.columbia.edu/index.html

The small worlds idea was first made popular by Stanley Milgram's famous experiment (1967) which found that two random US citizens where on average connected by six acquaintances (giving rise to the popular "six degrees of separation" expression):
Stanley Milgram. The Small World Problem, Psychology Today, 2: 60-67 (1967).

This model and documentation was adapted by Eytan Bakshy and Lada Adamic from: Wilensky, U. (2005). NetLogo Small Worlds model. http://ccl.northwestern.edu/netlogo/models/SmallWorlds. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.


PROCEDURES

globals
[
  clust-coeff               ;; the clustering coefficient of the network
                                       ;; this is the average of clustering coefficients of all nodes
  average-path-length                  ;; average path length of the network
  clustering-coefficient-of-lattice    ;; the clustering coefficient of the initial lattice
  average-path-length-of-lattice       ;; average path length of the initial lattice
  infinity                             ;; a very large number.
                                         ;; used to denote distance between two nodes which
                                         ;; don't have a connected or unconnected path between them
  tot-links
  num-valid-nodes
   clustcoeffsum
   numqualifyingnodes
   current-node
   num-neighbors
   n1
   n2
   is-connected
]

turtles-own
[
  distance-from-other-nodes
  node-clustering-coefficient
]

;;;;;;;;;;;;;;;;;;;;;;;;
;;; Setup Procedures ;;;
;;;;;;;;;;;;;;;;;;;;;;;;

to generate-topology
  
  set infinity 99999
  set-default-shape turtles "outlined circle"
  ;; setup small world topology
;  create-turtles num-nodes
  ask turtles
    [reset-node]
  ask links
    [die]
  
  ;; Layout turtles:
  layout-circle (sort turtles) max-pxcor - 8
  ;; space out turtles to see clustering
  ask turtles
  [
    facexy 0 0
    if who mod 2 = 0 [fd 4]
  ]
  display
  create-lattice
    ;; make sure num-nodes is setup correctly else run setup first
  if count turtles != num-nodes [
    setup
  ]
;  setup
  rewire-network
  set is-connected do-calculations
  do-plotting
end

; ************************
; calculation of clustering coefficient as described by Watts and Strogatz
; ************************
to cluster-coeff
  set numqualifyingnodes 0
  set clustcoeffsum 0
ask turtles [
  set tot-links 0

  set num-neighbors count link-neighbors
  set current-node self
   ask link-neighbors
  [
     set tot-links (tot-links + count link-neighbors with [link-neighbor? current-node])
  ]
   if (num-neighbors > 1)
   [set clustcoeffsum (clustcoeffsum + (tot-links / (num-neighbors * (num-neighbors - 1))))
   set numqualifyingnodes numqualifyingnodes + 1]
]
set clust-coeff (clustcoeffsum / numqualifyingnodes)
  create-lattice
end      

to initial-setup
  ca
  set infinity 99999
  set rewiring-probability 0
  set-default-shape turtles "outlined circle"
  ;; setup small world topology
  create-turtles num-nodes
  ask turtles
    [reset-node]
  ask links
    [set color gray + 1.5]
  
  ;; Layout turtles:
  layout-circle (sort turtles) max-pxcor - 8
  ;; space out turtles to see clustering
  ask turtles
  [
    facexy 0 0
    if who mod 2 = 0 [fd 4]
  ]
  display
  create-lattice
  rewire-network
  
  set is-connected do-calculations
 set clustering-coefficient-of-lattice clust-coeff
 set average-path-length-of-lattice average-path-length
  display
end

to setup
;  ca
  ask links [die]
  set infinity 99999
  
  ask turtles
    [reset-node]
  ask links
    [set color gray + 1.5]
    
  create-lattice
  rewire-network
  
  set is-connected do-calculations
; show average-path-length
 do-plotting
  display
end

to vary-p
;  clear-plot
  initial-setup
  set rewiring-probability 0.0
  while [rewiring-probability < 1.0] [
    setup
    set rewiring-probability rewiring-probability + 0.05
  ]
end

to reset-node
    set color gray - 0.75
    set size 2.1
end

  
;; WARNING: the simplified rewiring algorithm does not certain checks (ie disconnected graph)
;; for large networksthis shouldn't be too much of an issue.
to rewire-network
  ask links
  [
    ;; whether to rewire it or not?
    if (random-float 1) < rewiring-probability
    [
      ask end1
      [
        create-link-with one-of other turtles with [not link-neighbor? myself ]
          [set color gray + 1.5]
      ]
      die
    ]
  ]
end


;; spring layout all nodes and links
to do-layout
    repeat 5 [layout-spring turtles links 0.2 4 0.9]
  display
end

;; creates a new lattice
to create-lattice
  ;; iterate over the nodes
  let n 0
  while [n < count turtles]
  [
    ;; make links with the next two neighbors
    ;; this makes a lattice with average degree of 4
    make-link-between turtle n
              turtle ((n + 1) mod count turtles)
    make-link-between turtle n
              turtle ((n + 2) mod count turtles)
    set n n + 1
  ]
  
end


;; connects the two nodes
to make-link-between [node1 node2]
  ask node1 [
    create-link-with node2
      [ set color gray + 1.5]
  ]
end

to-report do-calculations
  
  ;; set up a variable so we can report if the network is disconnected
  let connected? true
  
  ;; check whether network got disconnected and ignore those runs (should not happen often);
  ;; we only want to calculate average path length when we have one connected component
  set average-path-length __average-path-length turtles links
  
  ;; find the clustering coefficient and add to the aggregate for all iterations
  cluster-coeff
  
  ;; report whether the network is connected or not
  report connected?
end


to find-path-lengths
  ;; reset the distance list

  set average-path-length __average-path-length turtles links
   
end


;;;;;;;;;;;;;;;;
;;; Plotting ;;;
;;;;;;;;;;;;;;;;

to do-plotting
     ;; plot the number of infected individuals at each step
     set-current-plot "Clustering coefficient and average path length"
     set-current-plot-pen "av-path"
     plotxy rewiring-probability
            average-path-length / average-path-length-of-lattice
   
     set-current-plot-pen "cc"
     ;; note: dividing by initial value to normalize the plot
     plotxy rewiring-probability
            clust-coeff / clustering-coefficient-of-lattice
end

; *** NetLogo 4.0 Model Copyright Notice ***
;
; This model was adopted by Eytan Bakshy and Lada Adamic from
; the model below:
;
; Copyright 2005 by Uri Wilensky.  All rights reserved.
;
; Permission to use, modify or redistribute this model is hereby granted,
; provided that both of the following requirements are followed:
; a) this copyright notice is included.
; b) this model will not be redistributed for profit without permission
;    from Uri Wilensky.
; Contact Uri Wilensky for appropriate licenses for redistribution for
; profit.
;
; To refer to this model in academic publications, please use:
; Wilensky, U. (2005).  NetLogo Small Worlds model.
; http://ccl.northwestern.edu/netlogo/models/SmallWorlds.
; Center for Connected Learning and Computer-Based Modeling,
; Northwestern University, Evanston, IL.
;
; In other publications, please use:
; Copyright 2005 Uri Wilensky.  All rights reserved.
; See http://ccl.northwestern.edu/netlogo/models/SmallWorlds
; for terms of use.
;
; *** End of NetLogo 4.0 Model Copyright Notice ***