globals [x-max y-max diam friction tot-edges filename my-tick stoptick
init-power-edges total-infected total-immune]
turtles-own
[
virus? ; does the turtle have the virus
immune? ; is the virus immune to the virus
num-neighbors ; number of (link) neighbors
]
to setup-globals ; separate procedure for setting globals
set diam 1
set x-max max-pxcor - (diam / 2) + 1; 0.5
set y-max max-pycor - (diam / 2) + 1; 0.5
set filename "" ; change to collect images (or just use command center after setup)
set stoptick 0 ; set to some number to stop, generally for image collections
set-default-shape turtles "circle"
set friction .25
set init-power-edges 2
set tot-edges min list round (number-of-nodes * edge-ratio)
((number-of-nodes ^ 2 - number-of-nodes) / 2)
end
to setup ; Setup the model for a run, build a graph.
;; (for this model to work with NetLogo's new plotting features,
;; __clear-all-and-reset-ticks should be replaced with clear-all at
;; the beginning of your setup procedure and reset-ticks at the end
;; of the procedure.)
clear-all
setup-globals
setup-patches
setup-turtles
set my-tick 0
ifelse powerlaw? [setup-power-graph] [setup-random-graph]
; ask turtles [ set color 5 + 10 * count link-neighbors ]
ask turtle 0 [ setxy 0 0 ]
if set-size
[ ask turtles [ set size max ( list 1 (round (count link-neighbors) / 3 )) ] ]
setup-plot
graph-edges
ask turtles [ set num-neighbors count link-neighbors ]
reset-ticks
end
to setup-patches
ask patches [set pcolor white]
; ask patches with [pxcor = 0 or pycor = 0][set pcolor gray]
end
to setup-turtles
crt number-of-nodes [
set color yellow
set label-color black
set size diam
; set label who
setxy (random-float (x-max)) * (1 - 2 * random 2)
(random-float (y-max)) * (1 - 2 * random 2)
set virus? false
set immune? false
]
end
to setup-power-graph ; Build a powerlaw graph
let n 0
let prob 0
let p 0
let elist 0
let t1 0
let t2 0
set prob (list turtle 0)
repeat min list init-power-edges (floor number-of-nodes / 3) [
ask last prob [connect-edge turtle (length prob)]
set prob lput turtle (length prob) prob
]
set elist n-values (number-of-nodes - length prob) [1]
while [reduce [ [?1 ?2] -> ?1 + ?2 ] elist < (tot-edges - count links)] [
set n random length elist
set elist replace-item n elist (1 + item n elist)
]
while [length elist > 0] [
set t1 turtle (number-of-nodes - length elist)
set p prob
repeat min list [who] of t1 first elist [
set t2 one-of p
ask t1 [connect-edge t2]
set p remove t2 p
set prob lput t1 prob
set prob lput t2 prob
]
set elist but-first elist
]
end
to setup-random-graph ; Build a random graph
let t 0
let t1 0
let g 0
set g (list turtle 1)
while [length g < number-of-nodes] [
set t1 one-of turtles with [not member? self g]
set t item random length g g
ask t1 [connect-edge t]
set g subgraph turtle 1
]
while [count links < tot-edges] [
set t one-of turtles
set t1 one-of turtles with [self != t ]
if t1 != nobody [ask t1 [connect-edge t]]
]
end
to-report subgraph [n] ; report the complete connected subgraph containing n1
let stack 0
let graph 0
set graph (list n)
set stack (list n)
while [length stack > 0] [
ask [link-neighbors] of first stack [
if not member? self graph [
set graph lput self graph
set stack lput self stack
]
]
set stack but-first stack
]
report graph
end
to go
ask turtles with [ virus? and (count (link-neighbors with [ (not immune?) and (not virus?) ]) > 0) ]
[ if (count (link-neighbors with [ (not immune?) and (not virus?) ]) > 0)
[ ask one-of link-neighbors with [ not immune? and not virus? ]
[ set virus? true
set color magenta
]
]
]
set my-tick my-tick + 1
plot-counts
end
to immunize
ifelse only-top
[ let top []
let sorted sort-by [ [?1 ?2] -> [num-neighbors] of ?1 > [num-neighbors] of ?2 ] turtles
repeat round (percent-immune * number-of-nodes / 100)
[ set top lput first sorted top
set sorted but-first sorted
]
ask turtle-set top
[ set immune? true
set color blue
]
]
[ ifelse friends
[ ask n-of round (percent-immune * number-of-nodes / 100) turtles
[ ask one-of link-neighbors
[ set immune? true
set color blue
]
]
]
[ ask n-of round (percent-immune * number-of-nodes / 100) turtles
[ set immune? true
set color blue
]
]
]
set total-immune count turtles with [ immune? ]
end
to infect
ask n-of round (number-of-nodes * percent-infected / 100) turtles with [ not immune? and not virus? ]
[ set virus? true
set color magenta
]
set total-infected count turtles with [ virus? ]
end
to layout ; The run procedure which makes the model take one step
let t 0
if filename = 0 [setup] ; an attempt to work even tho user forgets setup
if stoptick = -1 [stop]
;no-display
do-layout
set my-tick my-tick + 1
;display
if mouse-down? [
set t closest-xy mouse-xcor mouse-ycor turtles ;
while [mouse-down?] [
ask t [setxy mouse-xcor mouse-ycor]
; no-display
display
]
]
check-movie
if (stoptick = my-tick) [stop]
end
to do-layout
repeat 10 [ layout-spring turtles links spring-force spring-length mutual-repulsion ]
end
to step1 ; Adjust the edges and nodes for one step of the model
let delta 0.1
ask links [
set delta (spring-force * (link-length - spring-length)) / 2.0
ask turtles with [(member? self [both-ends] of myself)]
[face [other-end] of myself
forward delta]
]
ask turtles [
ask turtles with [self != myself] [
set delta distance myself
set delta mutual-repulsion / (delta * delta)
set heading towards myself
myjump (- delta)
]
]
ask turtle 0 [ setxy 0 0]
end
to graph-edges ; Make a simple edge histogram
set-current-plot "edge-distribution"
set-plot-x-range 1 1 + max [count link-neighbors] of turtles
histogram [count link-neighbors] of turtles
end
to plot-counts
set-current-plot "Number infected"
set total-infected count turtles with [ virus? ]
set-current-plot-pen "infected"
plot total-infected
end
to setup-plot
set-current-plot "Number infected"
clear-plot
set-plot-y-range 0 number-of-nodes
end
to check-movie ; if filename is non-empty, make another snapshot
if length filename > 0 [
; export-view filename + (round log my-tick 10) + my-tick + '.png'
]
end
;;;; Edge & Node utilities
to connect-edge [other-node] ; node proc: attach an edge between self and other
ask other-node [ create-link-with myself
[
set color gray
]
]
end
;;;; Utilities
to-report sign [num]
ifelse num < 0 [report -1][report 1]
end
to-report closest-xy [x y agent-set] ; Return closest agent to x, y
report min-one-of agent-set [distancexy x y]
end
to myjump [dist] ; turtle proc: jump but don't wrap, bounce w/ friction instead
let x 0
let y 0
set x xcor + dist * dx
set y ycor + dist * dy
if (abs x) > x-max [set x sign x * (x-max - (1 - friction) * ((abs x) - x-max))]
if (abs y) > y-max [set y sign y * (y-max - (1 - friction) * ((abs y) - y-max))]
setxy x y
end
@#$#@#$#@
GRAPHICS-WINDOW
204
10
563
370
-1
-1
9.0
1
10
1
1
1
0
1
1
1
-19
19
-19
19
0
0
1
ticks
30.0
BUTTON
7
10
62
43
NIL
setup
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL
1
BUTTON
65
10
120
43
NIL
go
T
1
T
OBSERVER
NIL
NIL
NIL
NIL
1
BUTTON
124
10
179
43
step
go
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL
1
SLIDER
5
119
183
152
number-of-nodes
number-of-nodes
2
500
200.0
1
1
NIL
HORIZONTAL
SLIDER
2
281
178
314
spring-force
spring-force
0
2
0.6
0.1
1
NIL
HORIZONTAL
SLIDER
2
317
178
350
spring-length
spring-length
0
10
2.75
0.25
1
NIL
HORIZONTAL
SLIDER
2
353
178
386
mutual-repulsion
mutual-repulsion
0
10
1.75
0.25
1
NIL
HORIZONTAL
SLIDER
5
156
99
189
edge-ratio
edge-ratio
0.8
2.5
1.2
0.1
1
NIL
HORIZONTAL
SWITCH
100
156
204
189
powerlaw?
powerlaw?
0
1
-1000
MONITOR
573
13
633
58
NIL
my-tick
3
1
11
PLOT
597
71
757
191
edge-distribution
edges/node
count
1.0
1.0
0.0
1.0
true
false
"" ""
PENS
"default" 1.0 1 -16777216 true "" ""
MONITOR
632
13
689
58
edges
count links
3
1
11
SWITCH
6
195
96
228
set-size
set-size
0
1
-1000
BUTTON
8
45
100
78
NIL
immunize
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL
1
BUTTON
105
45
171
78
NIL
infect
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL
1
SWITCH
101
195
191
228
friends
friends
0
1
-1000
BUTTON
9
82
79
115
NIL
layout
T
1
T
OBSERVER
NIL
NIL
NIL
NIL
1
SLIDER
7
234
179
267
percent-infected
percent-infected
0
100
3.0
1
1
NIL
HORIZONTAL
PLOT
582
265
782
415
Number infected
time-step
number infected
0.0
10.0
0.0
10.0
true
false
"" ""
PENS
"infected" 1.0 0 -5825686 true "" ""
MONITOR
578
211
675
256
NIL
total-infected
0
1
11
SLIDER
11
396
183
429
percent-immune
percent-immune
0
100
10.0
1
1
NIL
HORIZONTAL
MONITOR
691
210
788
255
NIL
total-immune
0
1
11
SWITCH
86
82
185
115
only-top
only-top
1
1
-1000
@#$#@#$#@
## WHAT IS IT?
This is a dynamic graph layout model using springs and repulsion forces to create a pleasing layout.
## HOW IT WORKS
The model uses two parameters (number-of-nodes and edge-ratio) to create the graph. For example, if the number of nodes is 10 and the edge ratio is 1.2, then the target graph would have 10 nodes and 12 edges.
We currently provide two graph types: random and power-law. The random graph simply connects random pairs of nodes together until the graph is fully connected and the number of edges is equal to or greater than the desired number.
Three parameters are used to adjust the layout while the model runs. The spring-force is how strongly the spring pushes/pulls the nodes. The spring-length is the 0-force length of the spring. Greater lengths attract, lesser repel. The total force is the spring-force times the amount the spring differs from its spring-length. Finally, there is a general repulsion between all nodes, specified by the mutual-repulsion parameter. It uses an inverse-square calculation rather than the spring's linear one.
## HOW TO USE IT
Click on setup to initialize the graph. Click on go to start the model. While the model is running, you can change the three spring/repulsion parameters. You also can grab a node with the mouse and move it around to help untangle the graph.
## THINGS TO NOTICE
This is a fairly simple model. The main thing to notice is that such a simple layout algorithm does a reasonable job of making the graph untangled.
The power-law graph uses the Barab�si method (Google for his group's papers) which creates fairly "bush-y" power-law graphs. His work helped us understand why web and internet graphs are often power-law by noting that these nets grow 1) progressively from small networks, and 2) link probabilistically to nodes according to "popularity" .. i.e. by number of links.
## THINGS TO TRY
Try various settings for number of nodes and edge ratio. Grab nodes with the mouse while the model is running. Change the spring and repulsion settings while the model is running. Try changing the graph type (power-law switch) between random and power-law. What are the differences that you see?
Try this: set the number of nodes to max and the edge ratio to 1.2 or so. Click setup several times in succession, first with powerlaw? on, then off. What differences does the edge histogram show?
Movies: (Use this with local models, not via the web) You can make a sequence of images for creating a movie of the model. To do this, type 'set filename "movie"' in the command center immediately after clicking "setup". When the model sees the filename has been set to a non-null value while running ("go"), it will take a picture every step of the model. The filenames will look like movie0001.png movie0002.png ... etc. You can stop the process by clicking on "go" when you have enough images. Alternatively, the model can be stopped by "set stoptick 100" or some similar value, again using the command center.
UI Changes: The size of the graph world can be changed by editing the graphics window. Try changing the patch size to a smaller number (5, say) and making the graph larger (35 x 35). Just click the "more" button on the graphics window. You can change the max number of nodes too by selecting its slider and editing it. I've tried 100, with small edge ratio and it worked fine.
Programming changes: You could modify or replace the two graph construction algorithms, or add additional ones. It would be interesting to see how a small world cluster would evolve under springs and repulsion. The "go" procedure can be modified to use other layout algorithms.
Research: Modify the step procedure to periodically look for edge crossings and try to eliminate them.
## EXTENDING THE MODEL
Other kinds of graphs would be interesting to add. See
http://backspaces.net/PLaw/index.html
for a discussion on creating and exploring power-law and small worlds graphs and their searching properties.
## NETLOGO FEATURES
This uses the generalizations NetLogo introduced which allow agents to be of any size and to use fractional coordinates. Amazingly enough, the edges in the model are really a breed of turtle whose shape is a line, whose heading is the direction of the edge and whose midpoint is halfway between the nodes. This is genius and works beautifully with the NetLogo concept of agents and patches. I never would have thought this could have worked, especially with such outstanding ease of programming and good performance.
## RELATED MODELS
The PLaw work above prompted my looking into NetLogo implementations like this. And the models Seth Tisue showed me while the edge/node development was underway were essential. The GraphVis graph drawing suite from ATT were used extensively in the power law study, for example:
http://backspaces.net/PLaw/html/graphs-TdS+.html
Their site is: http://www.graphviz.org/
The pioneering work by Caida (http://www.caida.org/) and kc claffy (http://www.caida.org/home/seniorstaff/kclaffy.xml) to study the web's "shape" are central to any interesting computer graph investigations.
The Santa Fe Institute's graph theoretic work is fascinating, including models of the internet, virus propagation, small worlds. This work has spawned a huge diversity of investigations world wide. Contact me (owen@backspaces.net) if you are interested in further pointers and potential projects.
## CREDITS AND REFERENCES
Seth Tisue showed me the basic ideas behind how to use fractional coordinates and arbitrary shapes for creating nodes and edges. Thanks! Arthur VonHoff created a similar layout demo for the Java SDK. Steve Guerin suggested the repulsive force idea. See his Redfish.com site for great demos of this and other visualization and modeling ideas.
@#$#@#$#@
default
true
0
Polygon -7500403 true true 150 5 40 250 150 205 260 250
circle
false
0
Circle -7500403 true true 35 35 230
line
true
0
Line -7500403 true 150 0 150 301
@#$#@#$#@
NetLogo 6.0
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@
default
0.0
-0.2 0 0.0 1.0
0.0 1 1.0 0.0
0.2 0 0.0 1.0
link direction
true
0
Line -7500403 true 150 150 90 180
Line -7500403 true 150 150 210 180
@#$#@#$#@
0
@#$#@#$#@