HOTnet (a)

No preview image

1 collaborator

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 are ubiquitous of real world situations, ranging from the connections between websites to the collaborations between actors.

The model generates these networks by a process of "Highly/Heuristically Optimized/Organized Tolerance/Tradeoffs", in which new network members make a connection to the members which optimize multiple functional objectives.

HOW IT WORKS

The model starts with two nodes connected by an edge: the root node, in the center, and a node situated randomly in the space.

At each step, a new node is added. A new node is created in a random place in the space and then it chooses to attach himself to the node which minimizes the sum of two objectives: Euclidean distance from the node to attach to and number of hops from the root node.

HOW TO USE IT

First you have to hit SETUP button which creates two connected nodes. Pressing the GO-ONCE button adds one new node. To continuously add nodes, press GO.

The PLOT? switch turns off the plots.

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

If you 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 but should be used only after simulation run, to avoid interfering with base logic.

If you want save nodes degree on a file for later use, push SAVE-NODES-DEGREE. It will save a file called "NodesDegree.txt".

If you want the model to run faster, you can turn off the PLOT? switch, slide to the right the speed and/or uncheck "view updates".

THINGS TO NOTICE

The networks that result from running this model are often called "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. Alex Fabrikant, Elias Koutsoupias, and Christos H. Papadimitriou propose a plausible explanation of the power law distributions of degrees observed in the graphs arising in the Internet topology based on a toy model of Internet growth in which two objectives are optimized simultaneously: “last mile” connection costs, and transmission delays measured in hops. Results seem to suggest that power laws tend to arise as a result of complex, multi-objective optimization. John C. Doyle et al. goes even further showing the power of S-metric and how this kind of networks can have greater performance and resilience than "scale-free" networks like "preferential attachment" of Barabasi & Albert.

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?

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 attachment depend on this new attribute as well as on degree or other parameters.

In this network all nodes are peers but this is not the case of internet where differences exist between end users and ISPs; can be power law degrees distribution preserved?

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.

What about S(g)? How does it vary? Why?

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

Nodes are turtle agents and edges are link agents. The layout-spring primitive places the nodes, as if the edges are springs and the nodes are repelling each other.

RELATED MODELS

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

See also Network Example, in the Code Examples section.

CREDITS AND REFERENCES

This model is based on:
Alex Fabrikant, Elias Koutsoupias, and Christos H. Papadimitriou. Heuristically Optimized Trade-offs: A New Paradigm for Power Laws in the Internet.

For a more technical treatment, see also:
Lun Li, David Alderson, Reiko Tanaka, John C. Doyle, Walter Willinger. Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications, Technical Report CIT-CDS-04-006, Engineering & Applied Sciences Division California Institute of Technology, Pasadena, CA, USA.

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.

HOW TO CITE

If you mention this model in a publication, we ask that you include these citations for the model itself and for the NetLogo software:
- Tomasini Marcello (2012). HOTnet model.
Student at University of Modena and Reggio Emilia.
- Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

COPYRIGHT AND LICENSE

CC BY-NC-SA 3.0

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

extensions [ nw ]
;; the number of hops from a fixed center of the tree
turtles-own [ nhop ]

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

to setup
  clear-all
  set-default-shape turtles "circle"
  ;; make the initial network of two turtles and an edge
  crt 1 
  [
    set color green
    set nhop 0 
  ] ;; first node unattached is the root of the tree

  crt 1 
  [ 
    setxy random-xcor random-ycor
    set color red
    create-link-with turtle 0 [ set color green ]
    set nhop 1
  ]
  
  reset-ticks
end 

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

to go
  ;; it takes a static picture of the network at the time you call it. 
  ;; All subsequent network operations will use this static picture, even if turtles or links have been created or died 
  ;; in the meantime, until you call set-snapshot again.
  nw:set-snapshot turtles links
  ;; new edge is green, old edges are gray
  ask links [ set color gray ]  
  ;; The behavior of the model depends crucially on the value of alfa:
  ;; if alfa is less than a particular constant depending on the shape of the region, 
  ;; then Euclidean distances are not important, and the resulting network is easily seen to be a star,
  ;; the ultimate in degree concentration, and, depending on how you look at it, the exact opposite, or absurd extreme, of a power law.
  ;; If alfa grows at least as fast as sqrt(n), where n is the final number of points, then Euclidean distance becomes too important, 
  ;; and the resulting graph is a dynamic version of the Euclidean minimum spanning tree, in which high degrees do occur, 
  ;; but with exponentially vanishing probability.
  ;; If, however, alfa is anywhere in between — is larger than a certain constant, but grows slower than sqrt(n) if at all —
  ;; then, almost certainly, the degrees obey a power law.
  ;;let alfa 100
  let x random-xcor
  let y random-ycor
  let partner nobody
  ;; Node i attaches itself to the node j that minimizes the weighted sum of the two objectives:
  ;; alfa * dij + hj
  ;; where dij is the /normalized/ Euclidean distance, and hj is some measure of the “centrality” of node j, such as 
  ;; (a) the average number of hops from other nodes; 
  ;; (b) the maximum number of hops from another node; 
  ;; (c) the number of hops from a fixed center of the tree;
  ;; all three measures result in similar power laws, in this case we use (a).
  set partner min-one-of turtles
  [ 
    alfa * 
    sqrt 
    ( 
      ;;( (x - min-pxcor + 0.5) / (max-pxcor - min-pxcor) - (xcor - min-pxcor + 0.5) / (max-pxcor - min-pxcor) ) ^ 2 + 
      ( (x - xcor) / (max-pxcor - min-pxcor) ) ^ 2 +
      ;;( (y - min-pycor + 0.5) / (max-pycor - min-pycor) - (ycor - min-pycor + 0.5) / (max-pycor - min-pycor) ) ^ 2 
      ( (y - ycor) / (max-pycor - min-pycor) ) ^ 2
    ) 
    + avg-distance self
  ]
  crt 1
  [
    setxy x y
    set color red
    if partner != nobody
    [ 
      create-link-with partner [ set color green ]
      set nhop 1 + [ nhop ] of partner
    ]
  ]
 
  tick
end 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Compute heuristic (a) ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to-report avg-distance [me]
  let avg-dist 0
  ask me
  [
    let dist n-values count turtles [ nw:distance-to turtle ? ]
    set avg-dist (sum dist) / count turtles 
  ]
  report avg-dist
end 
;;;;;;;;;;;;;;;;;;;;
;;; Compute s(g) ;;;
;;;;;;;;;;;;;;;;;;;;

to-report log-likelihood
  let s 0
  ;; for each link compute di*dj and sum it to s
  ask links 
  [ 
    set s s + [ count link-neighbors ] of end1 * [ count link-neighbors ] of end2 
  ]
  report s
end 
;;;;;;;;;;;;;;;;;;;;;;;;
;;; Compute S-metric ;;;
;;;;;;;;;;;;;;;;;;;;;;;; 

to-report relative-log-likelihood
  let smax 0
  let counter 0
  let di 0
  let child 0

  ;; D = { d1, d2, d3, ..., dn }, d1 >= d2 >= d3 >= ... >= dn
  let degree-sequence sort-by > [ count  link-neighbors ] of turtles
  set di item 0 degree-sequence
  set degree-sequence remove-item 0 degree-sequence
  foreach degree-sequence
  [
    set smax smax + di * ?
    set counter counter + 1
    if di = counter ;; we have iterated through all di's childs; if di = 0 select the highest degree.
    [
      set counter 1 ;; count the parent if it's not the root
      set di item child degree-sequence ;; select child; child = 0 is the root.
      set child child + 1
    ]
  ]

  report log-likelihood / smax
end 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Save Nodes Degrees to file ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to save-node-degree-to-file
  if file-exists? "NodeDegrees.txt" [ file-delete "NodeDegrees.txt" ]
  
  file-open "NodesDegree.txt"
  
  ;; save in descending orders
  ;; D = { d1, d2, d3, ..., dn }, d1 >= d2 >= d3 >= ... >= dn
  foreach sort-by > [ count link-neighbors ] of turtles
  [
    file-print ?
  ]
  file-close
end 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Export Graph Connectivity to txt ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to export-graph
  if file-exists? "HOTGraph.txt" [ file-delete "HOTGraph.txt" ]
  
  file-open "HOTGraph.txt"
  
  ;; write each linked couple of tourtles and their degree
  ask links 
  [ 
    file-type [who] of end1 ;; writes without blank spaces
    file-write [who] of end2 ;; write a space value space
    file-print "" ;; write carriage return
  ]
  file-close
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 with [ size >= 4 ] [ set color violet ]
  ]
  [
    ask turtles 
    [ 
      set size 1 
      set color red
    ]
  ]
end 

to layout
  ;; the number 3 here is arbitrary; more repetitions slows down the
  ;; model, but too few gives poor layouts
  repeat 2 [
    ;; 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 (3 / factor) (5 / factor) (0.5 / 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 

; Copyright 2012 Tomasini Marcello.
; See Info tab for full copyright and license.

There is only one version of this model, created over 12 years ago by Marcello Tomasini.

Attached files

File	Type	Description	Last updated
nw-ext-beta-0.02.zip	extension	new Network Extension	over 12 years ago, by Marcello Tomasini	Download

Parent: HOTnet

This model does not have any descendants.

Graph of models related to 'HOTnet (a)'

NetLogo