powered by NetLogo
view/download model file: ErdosRenyiDegDist.nlogo
You can generate Erdös-Renyi random graphs, and observe the degree distribution, both on linear and log axes.
NUM-NODES are created, and wired according to either an edge probability or a desired average number of neighbors per node. The output is both visual (use the DO-LAYOUT? button to apply a spring layout algorithm), the giant component is highlighted in pink, and the degree distirbutions are shown in the plots.
The NUM-NODES slider determines the size of the network (the number of nodes)
The GC SIZE monitor box updates with the size of the largest component.
The AV. DEG monitor box reports on the average degree in the network.
The PROB-OR-NUM switch determines whether the network will be constructed with PROB-LINK probability of every pair of nodes being connected, or NUM-NEIGHBORS / 2 edges will be added for each node in the network.
ERDÖS-RENYI constructs a random graph by adding an edge between each pair of nodes with probability PROB-LINK or with NUM-NEIGHBORS edges per node (see switch explanation above).
REDO LAYOUT will repeatedly apply a spring-layout algorithm to the network. In the long run this can make your computer run hot, so remember to switch it off if you have NetLogo running and are not actively using it. There are also several parameters that you can adjust so that sparse networks get pulled together more tightly, but dense networks are spread out.
RESIZE-NODES will resize the nodes according to their degree (the scaling is logarithmic).
How evenly distributed is degree among the nodes. Are there some nodes with many times more edges than the median? How is this reflected in the linear scale bar plot, and in the
Try varying the probability of edges, or the number of neighbors. How does the distribution of degrees compare to each quantity?
This model was adapted by Lada Adamic from Uri Wilensky’s Giant Preferrential attachment in NetLogo’s models library
Copyright 2012 Lada Adamic.
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.
turtles-own
[
;; this is used to mark turtles we have already visited
explored?
]
globals
[
component-size ;; number of turtles explored so far in the current component
giant-component-size ;; number of turtles in the giant component
giant-start-node ;; node from where we started exploring the giant component
]
;;;;;;;;;;;;;;;;;;;;;;;;
;;; Setup Procedures ;;;
;;;;;;;;;;;;;;;;;;;;;;;;
to make-turtles
crt num-nodes [
set xcor random-xcor
set ycor random-ycor
]
end
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Network wiring procedures ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
to all-random
ca
let thiswho 0
RESET-TICKS
if (not any? turtles) [make-turtles]
ask turtles [
set shape "circle"
set size 2
]
ifelse prob-or-num? [
; either add links between every pair of nodes with
; probability prob-link
ask turtles [
set thiswho who
ask other turtles with [who > thiswho] [
if (random-float 1 < prob-link) [
create-link-with myself
]
]
]
] [
; or add (num-neighbors * num nodes / 2) edges at random
repeat (floor (num-neighbors * num-nodes / 2)) [
ask one-of turtles [
ask one-of other turtles with [not link-neighbor? myself] [
create-link-with myself
]
]
]
]
find-all-components
color-giant-component
; set the x-axis range for the linear bar-plot
set-current-plot "degree distribution"
let max-deg max [count link-neighbors] of turtles
set-plot-x-range 0 (max-deg + 1)
set-histogram-num-bars (max-deg + 1)
; set the x-axis range for log scale point plot
set-current-plot "degree dist (log-log)"
set-plot-x-range 0 precision (log ((max [count link-neighbors] of turtles) + 1) 10) 2
tick
; apply a spring layout algorithm to the network
repeat 100 [
do-layout
]
end
to resize-nodes
ask turtles [
set size 2 * (log ((count link-neighbors) + 1) 10)
]
end
;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Network Exploration ;;;
;;; code by Uri Wilensky ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; to find all the connected components in the network, their sizes and starting turtles
to find-all-components
set giant-component-size 0
ask turtles [ set explored? false ]
;; keep exploring till all turtles get explored
loop
[
;; pick a node that has not yet been explored
let start one-of turtles with [ not explored? ]
if start = nobody [ stop ]
;; reset the number of turtles found to 0
;; this variable is updated each time we explore an
;; unexplored node.
set component-size 0
;; at this stage, we recolor everything to light gray
ask start [ explore (gray + 2) ]
;; the explore procedure updates the component-size variable.
;; so check, have we found a new giant component?
if component-size > giant-component-size
[
set giant-component-size component-size
set giant-start-node start
]
]
end
;; Finds all turtles reachable from this node (and recolors them)
to explore [new-color] ;; node procedure
if explored? [ stop ]
set explored? true
set component-size component-size + 1
;; color the node
set color new-color
ask link-neighbors [ explore new-color ]
end
;; color the giant component red
to color-giant-component
ask turtles [ set explored? false ]
ask giant-start-node [ explore red ]
ask links [ set color [color + 3] of end1 ] ;; recolor all edges
end
;;;;;;;;;;;;;;;;;;;;;;;
;;; Edge Operations ;;;
;;;;;;;;;;;;;;;;;;;;;;;
;; pick a random missing edge and create it
to add-edge
let node1 one-of turtles
let node2 one-of turtles
ask node1 [
ifelse link-neighbor? node2 or node1 = node2
;; if there's already an edge there, then go back
;; and pick new turtles
[ add-edge ]
;; else, go ahead and make it
[ create-link-with node2 ]
]
end
;;;;;;;;;;;;;;
;;; Layout ;;;
;;;;;;;;;;;;;;
to layout
;; the number 10 here is arbitrary; more repetitions slows down the
;; model, but too few gives poor layouts
repeat 10 [
do-layout
display ;; so we get smooth animation
]
end
to do-layout
layout-spring (turtles with [any? link-neighbors]) links spring-constant spring-length repulsion-strength
end
; Original Copyright 2005 Uri Wilensky.
; Modified by Lada Adamic
; See Info tab for full copyright and license.