powered by NetLogo

view/download model file: RAndPrefAttachment.nlogo

WHAT IS IT?

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

Pressing the GO ONCE button adds one new node. To continuously add nodes, press GO.

The LAYOUT? switch controls whether or not the layout procedure is run. This procedure attempts to move the nodes around to make the structure of the network easier to see.

The PLOT? switch turns off the plots which speeds up the model.

The RESIZE-NODES button will make all of the nodes take on a size representative of their degree distribution. If you press it again the nodes will return to equal size.

If you want the model to run faster, you can turn off the LAYOUT? and PLOT? switches and/or freeze the view (using the on/off button in the control strip over the view). The LAYOUT? switch has the greatest effect on the speed of the model.

If you have LAYOUT? switched off, and then want the network to have a more appealing layout, press the REDO-LAYOUT button which will run the layout-step procedure until you press the button again. You can press REDO-LAYOUT at any time even if you had LAYOUT? switched on and it will try to make the network easier to see.


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

Let the model run a little while. How many nodes are "hubs", that is, have many connections? How many have only a few? Does some low degree node ever become a hub? How often?

Turn off the LAYOUT? switch and freeze the view to speed up the model, then allow a large network to form. What is the shape of the histogram in the top plot? What do you see in log-log plot? Notice that the log-log plot is only a straight line for a limited range of values. Why is this? Does the degree to which the log-log plot resembles a straight line grow as you add more node to the network?


EXTENDING THE MODEL

Assign an additional attribute to each node. Make the probability of attachment depend on this new attribute as well as on degree. (A bias slider could control how much the attribute influences the decision.)

Can the layout algorithm be improved? Perhaps nodes from different hubs could repel each other more strongly than nodes from the same hub, in order to encourage the hubs to be physically separate in the layout.


NETWORK CONCEPTS

There are many ways to graphically display networks. This model uses a common "spring" method where the movement of a node at each time step is the net result of "spring" forces that pulls connected nodes together and repulsion forces that push all the nodes away from each other. This code is in the layout-step procedure. You can force this code to execute any time by pressing the REDO LAYOUT button, and pressing it again when you are happy with the layout.


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.


PROCEDURES

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

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

to setup
  ca
  set degrees []   ;; initialize the array to be empty
  ;; make the initial network of two nodes and an edge
  set-default-shape turtles "circle"
  ;; make the initial network of two nodes and an edge
  make-node ;; first node
  let first-node new-node
  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
end

;;;;;;;;;;;;;;;;;;;;;;;
;;; Main Procedures ;;;
;;;;;;;;;;;;;;;;;;;;;;;

to go
  ;; new edge is green, old edges are gray
  ask links [ set color gray ]
  make-node
  repeat m [
  
  
  let partner find-partner new-node       ;; find partner & use it as attachment
                                 ;; point for new node
  ask new-node [
    move-to partner
       fd 8
    create-link-with partner [set color green]
      set degrees lput new-node degrees
      set degrees lput partner degrees
    ]
  ]
  tick
  if layout? [ layout ]
  if plot? [ do-plotting ]
end

;; used for creating a new node
to make-node
  crt 1
  [
    set color red
    set new-node self ;; set the new-node global
  ]
end

;; connects the two nodes
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
       move-to new-node
       fd 8
      set degrees lput node1 degrees
      set degrees lput node2 degrees
     ]
  ]
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 nodes 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

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

to do-plotting ;; plotting procedure
  let max-degree max [count link-neighbors] of turtles

  set-current-plot "Degree Distribution"
  plot-pen-reset  ;; erase what we plotted before
  set-plot-x-range 1 (max-degree + 1)  ;; + 1 to make room for the width of the last bar
  histogram [count link-neighbors] of turtles

  ;; for this plot, the axes are logarithmic, so we can't
  ;; use "histogram-from"; we have to plot the points
  ;; ourselves one at a time
  set-current-plot "Degree Distribution (log-log)"
  plot-pen-reset  ;; erase what we plotted before
  ;; the way we create the network there is never a zero degree node,
  ;; so start plotting at degree one
  let degree 1
  while [degree <= max-degree]
  [
    let matches turtles with [count link-neighbors = degree]
    if any? matches
      [ plotxy log degree 10
               log (count matches) 10 ]
    set degree degree + 1
  ]
end

;;;;;;;;;;;;;;
;;; Layout ;;;
;;;;;;;;;;;;;;

;; resize-nodes, change back and forth from size based on degree to a size of 1
to resize-nodes
  ifelse all? turtles [size <= 1]
  [
    ;; a node is a circle with diameter determined by
    ;; the SIZE variable; using SQRT makes the circle's
    ;; area proportional to its degree
    ask turtles [ set size sqrt count link-neighbors ]
  ]
  [
    ask turtles [ set size 1 ]
  ]
end

to layout
  ;; the number 3 here is arbitrary; more repetitions slows down the
  ;; model, but too few gives poor layouts
  repeat 3 [
    ;; the more turtles we have to fit into the same amount of space,
    ;; the smaller the inputs to layout-spring we'll need to use
    let factor sqrt count turtles
    ;; numbers here are arbitrarily chosen for pleasing appearance
    layout-spring turtles links (1 / factor) (7 / factor) (1 / factor)
    display  ;; for smooth animation
  ]
  ;; don't bump the edges of the world
  let x-offset max [xcor] of turtles + min [xcor] of turtles
  let y-offset max [ycor] of turtles + min [ycor] of turtles
  ;; big jumps look funny, so only adjust a little each time
  set x-offset limit-magnitude x-offset 0.1
  set y-offset limit-magnitude y-offset 0.1
  ask turtles [ setxy (xcor - x-offset / 2) (ycor - y-offset / 2) ]
end

to-report limit-magnitude [number limit]
  if number > limit [ report limit ]
  if number < (- limit) [ report (- limit) ]
  report number
end


; *** NetLogo 4.0beta5 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 4.0beta5 Model Copyright Notice ***