powered by NetLogo

view/download model file: BADiffusion.nlogo

WHAT IS IT?

This is Lada and Eytan's modification of the default BA model that comes with the NetLogo There is an added parameter gamma, which when 0 implies preferential attachment, and when 1 implies completley random attachment between a new node and the exisiting network.

Additionally, this is a diffusion model. After setting up the network with the desired number of nodes (num-nodes), it will infect one node at random. You can then step through the diffusion process either step by step (spread once) or until every node is infected (spread complete). The plot will show the number of nodes infected at each time point. The time monitor will give the current time, and in the case of the 'spread complete' option, how many steps it took until all the nodes are infected. Note that this is the SI model - nodes are either suceptible or infected and there is no recovery. The 'p' parameter gives the probability that a an infected node will infect a neighbor at each time step.

From here on down is Uri's original, much more organized documentation:
In some networks, a few "hubs" have lots of connections, while everybody else only has a few. This model shows one way such networks can arise.

Such networks can be found in a surprisingly large range of real world situations, ranging from the connections between websites to the collaborations between actors.

This model generates these networks by a process of "preferential attachment", in which new network members prefer to make a connection to the more popular existing members.


HOW IT WORKS

The model starts with two nodes connected by an edge.

At each step, a new node is added. A new node picks an existing node to connect to randomly, but with some bias. More specifically, a node's chance of being selected is directly proportional to the number of connections it already has, or its "degree." This is the mechanism which is called "preferential attachment."


HOW TO USE IT

The NUM-NODES slider controls the size of the network.

The GAMMA parameter determines whether the attachment is preferential (gamma = 0
means entirely preferential, gamma = 1 means entirely random).

Choose num-nodes and gamma and press SETUP.

Adjust the p value to determine the infectiousness of the spreading agent.

To re-infect one will infect a single individual while keeping the same topology - press "reinfect-one".

Now to allow the disease to spread, you can advance on time step at a time (each infected node will infect each of its neighbors with probability p) with the "spread once" button. To let the disease run its full course, you can click the "spread" button.


THINGS TO NOTICE

The networks that result from running this model are often called "scale-free" or "power law" networks. These are networks in which the distribution of the number of connections of each node is not a normal distribution -- instead it follows what is a called a power law distribution. Power law distributions are different from normal distributions in that they do not have a peak at the average, and they are more likely to contain extreme values (see Barabasi 2002 for a further description of the frequency and significance of scale-free networks). Barabasi originally described this mechanism for creating networks, but there are other mechanisms of creating scale-free networks and so the networks created by the mechanism implemented in this model are referred to as Barabasi scale-free networks.

You can see the degree distribution of the network in this model by looking at the plots. The top plot is a histogram of the degree of each node. The bottom plot shows the same data, but both axes are on a logarithmic scale. When degree distribution follows a power law, it appears as a straight line on the log-log plot. One simple way to think about power laws is that if there is one node with a degree distribution of 1000, then there will be ten nodes with a degree distribution of 100, and 100 nodes with a degree distribution of 10.


THINGS TO TRY

Try plotting the values for different rewiring probabilities observe how long it takes the infection to spread completely. What is the shape of the infection curve when the rewiring probability is 0? Is there much difference in the spead of spread past a certain value of p?


EXTENDING THE MODEL

Try to see if you can create the SIS model - nodes recover and return to the 'susceptible state' after either a fixed time period, or with some probability at each time step. In this case you are looking for the conditions under which you will observe epidemics - outbreaks that affect a significant fraction of the network, vs. conditions under which the outbreak remains small and contained.


NETLOGO FEATURES

Both nodes and edges are turtles. Edge turtles have the "line" shape. The edge turtle's SIZE variable is used to make the edge be the right length.

Lists are used heavily in this model. Each node maintains a list of its neighboring nodes.


RELATED MODELS

See other models in the Networks section of the Models Library, such as Giant Component.

See also Network Example, in the Code Examples section.


CREDITS AND REFERENCES

This model is based on:
Albert-Laszlo Barabasi. Linked: The New Science of Networks, Perseus Publishing, Cambridge, Massachusetts, pages 79-92.

For a more technical treatment, see:
Albert-Laszlo Barabasi & Reka Albert. Emergence of Scaling in Random Networks, Science, Vol 286, Issue 5439, 15 October 1999, pages 509-512.

Barabasi's webpage has additional information at: http://www.nd.edu/~alb/

The layout algorithm is based on the Fruchterman-Reingold layout algorithm. More information about this algorithm can be obtained at: http://citeseer.ist.psu.edu/fruchterman91graph.html.

For a model similar to the one described in the first extension, please consult:
W. Brian Arthur, "Urban Systems and Historical Path-Dependence", Chapt. 4 in Urban systems and Infrastructure, J. Ausubel and R. Herman (eds.), National Academy of Sciences, Washington, D.C., 1988.

To refer to this model in academic publications, please use: Wilensky, U. (2005). NetLogo Preferential Attachment model. http://ccl.northwestern.edu/netlogo/models/PreferentialAttachment. 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/PreferentialAttachment for terms of use.

Modified by Lada Adamic 2007


PROCEDURES

; adapted from models library by Lada Adamic (see copyright below)
; for the purposes of SI708/CSCS608
; also now contains major improvements by Eytan Bakshy

globals
[
  new-node  ;; the last node we created
  degrees   ;; this is an array that contains each node in
            ;; proportion to its degree
  time
  num-infected
  tree-mode?
]

turtles-own
[
  infected?        ;; true if agent has been infected
  infection-count  ;; the number of turtles a turtle has infected
]

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

to setup
  ca
  set tree-mode? false
  set-default-shape turtles "circle"
  set degrees []   ;; initialize the array to be empty
  ;; make the initial network of two turtles and an edge
  
  make-node ;; add the very first node
  
  let first-node new-node  ;; remember that its the first node
  
  ;; the following few lines create a cycle of length 5
  ;; this is just an arbitrary way to start a network
  
  let prev-node new-node
  repeat 4 [
    make-node ;; second node
    make-edge new-node prev-node ;; make the edge
    set degrees lput prev-node degrees
    set degrees lput new-node degrees
    set prev-node new-node
  ]
  make-edge new-node first-node
  
  set time 0
  set num-infected 0

  while [count turtles < num-nodes] [
    no-display
    ;; new edge is green, old edges are gray
    ask links [ set color gray + 2]
    ;; old turtles are blue
    ask turtles [set color gray + 2]
  
    make-node  ;; add one new node
  
    ;; it's going to have m edges
    repeat m [
      let partner find-partner new-node      ;; find a partner for the new node
      ask partner [set color gray + 2]    ;; set color of partner to gray
      make-edge new-node partner     ;; connect it to the partner we picked before
    ]
    if layout? [ do-layout ]
    if plot? [ do-plotting ]
    display
  ]
  ask one-of turtles
  [ set infected? true
    set color red + 2
  ]
end



;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Runtime Procedures ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;

; reset diffusion simulation
to reinfect-one
  clear-plot
  set num-infected 1
  set time 0
  ask turtles [
    set color gray + 2
    set infected? false
  ]
  ask links [
    set color gray + 2
  ]
  ask one-of turtles
  [ set infected? true
    set color red + 2
  ]
end

;; toggle infection tree mode
;; when tree-mode is on, only links responsible for contagion and infected nodes
;; are displayed. tree-mode also affects layout
to toggle-tree
  ifelse tree-mode?
  [
    ask turtles with [not infected?] [show-turtle]
    ask links with [color != red - 1] [show-link]  
    set tree-mode? false
  ]
  [
    ask turtles with [not infected?] [hide-turtle]
    ask links with [color != red - 1] [hide-link]
    set tree-mode? true
  ]
end

to spread
  ;; infection can't take place while in infection tree mode
  ;; or if every agent has already been infected
  if all? turtles [infected?]
    [stop]
  ask turtles with [ infected? = true ]
  [
    ;; infect neighbors
    ask link-neighbors
    [ 
      if ( random-float 1 <= p )  ;; infect with probability p
      [
        if not infected?  ;; agents can be infected only once
        [
          set infected? true
          show-turtle
          set color red + 1
          ;; incremement infection-count of the node doing the infection
          ask myself [set infection-count infection-count + 1]
          ;; color the link with the node doing the infection
          ask link-with myself [set color red - 1 show-link]
          ;; increment the total number of infected agents
          set num-infected num-infected + 1
        ]
      ]
    ]

    ;; resize node so that the area is proportional to the current number of infections
    set size 1 * sqrt (infection-count + 1)
  ]
  
  do-plotting
  tick
end

;; used for creating a new node
to make-node
  create-turtles 1  ;; don't know what this is - lada
  [
    set color gray + 2
    set size 0.5
    set infected? false
    set new-node self ;; set the new-node global
  ]
end

to reset-node
    set color gray - 0.75
    set size 2.1
    set infected? false
    set infection-count 0
end

;; Find a node to attach to
;; the degree of a node
;; 0 < gamma < 1 means gamma*100 percent of the 
;; time attach randomly, rest of the time attach
;; preferentially 

to-report find-partner [node1]
  ;; set a local variable called ispref that
  ;; determines if this link is going to be
  ;; preferential of not
  let ispref (random-float 1 >= gamma)
  
  ;; initialize partner to be the node itself
  ;; this will have to be changed
  let partner node1
  
  ;; if preferential attachment then choose
  ;; from our degrees array
  ;; otherwise chose one of the turtles at random
  ifelse ispref 
  [
    set partner one-of degrees
   ]
   [
     set partner one-of turtles
     ]
     
   ;; but need to check that partner chosen isn't
   ;; the node itself and also isn't a node that
   ;; our node is already connected to
   ;; if this is the case, it will try another
   ;; partner and try again
  let checkit true
  while [checkit] [
    ask partner [
      ifelse ((link-neighbor? node1) or (partner = node1))
        [
          ifelse ispref 
          [
            set partner one-of degrees
           ]
           [
             set partner one-of turtles
           ]
            set checkit true
         ]
         [
           set checkit false
         ]
       ] 
    ]
  report partner
end

;;;;;;;;;;;;;;;;;;;;;;;
;;; Edge Operations ;;;
;;;;;;;;;;;;;;;;;;;;;;;

;; connects the two turtles
to make-edge [node1 node2]
  ask node1 [
    ifelse (node1 = node2) 
    [
      show "error: self-loop attempted"
    ]
    [
      create-link-with node2 [ set color green ]
     ;; position the new node near its partner
      setxy ([xcor] of node2) ([ycor] of node2)
      rt random 360
      fd 8
      set degrees lput node1 degrees
     set degrees lput node2 degrees
     ]
  ]
end


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

to do-plotting
     ;; plot the number of infected individuals at each step
     set-current-plot "Number infected"
     set-current-plot-pen "inf"
     
     plotxy ticks num-infected
end

;;;;;;;;;;;;;;
;;; Layout ;;;
;;;;;;;;;;;;;;
;; resize-turtles, change back and forth from size based on degree to a size of 1

;; spring layout of infection tree while in tree mode
;; otherwise, layout all nodes and links
to do-layout
  ifelse tree-mode?
    [repeat 5 [layout-spring (turtles with [infected?]) (links with [color = red - 1]) 0.2 4 0.9]]
    [repeat 5 [layout-spring turtles links 0.2 4 0.9]]
  display
end


; *** NetLogo 3.1.3 Model Copyright Notice ***
;
; 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 Preferential Attachment model.
; http://ccl.northwestern.edu/netlogo/models/PreferentialAttachment.
; 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/PreferentialAttachment
; for terms of use.
;
; *** End of NetLogo 3.1.3 Model Copyright Notice ***