WHAT IS IT?

A model of a random graph explaining why there is just one giant component.

HOW IT WORKS

Initially, if KEEP-SEPARATE? is on, edges will only be created between nodes of the same shape (this way we can artificially generate two separate giant components).
Then once KEEP-SEPARATE is turned off, edges can be added between any two nodes. How long does it take for the two giant components to merge?

HOW TO USE IT

The NUM-NODES slider determines the size of the network

Then click on SETUP to get the desired number of nodes (half of them will be circles,
half of them will be squares)

Make sure KEEP-SEPARATE? is ON.

Click on ADD-EDGES to start adding edges just between nodes of the same shape.
(remember that you can adjust the speed with the slider on top)

(Optional) Click on LAYOUT to use a spring layout algorithm to reposition the nodes

Click on ADD-EDGES again to stop the process

Now turn KEEP-SEPARATE? OFF.

How many clicks of ‘ADD ONE EDGE’ does it take to merge the two giant components?

THINGS TO NOTICE

Does it make sense that random graphs only generate one giant component?

COPYRIGHT AND LICENSE

This model was adapted by Lada Adamic from Uri Wilensky’s Giant Component model in NetLogo’s models library

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.

CODE

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
  ca
  crt (num-nodes / 2) [
    set shape "circle"
    set xcor (-1) * abs random-xcor
    set ycor random-ycor
  ]
  crt (num-nodes / 2) [
    set shape "square"
    set xcor abs random-xcor
    set ycor random-ycor
  ]
  ask turtles [set size 3]
end

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Network wiring procedures ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;



;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; 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] of end1 ]  ;; recolor all edges
end

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

;; pick a random missing edge and create it
to add-edge
  ask links [set color [color] of end1
    set thickness 0]
  if not any? turtles [
    print "Click on SETUP first to add nodes"
    stop
    ]
  ask one-of turtles [
    ifelse keep-separate? [ 
      if any? other turtles with [not link-neighbor? self and shape = [shape] of myself] [
        ask one-of other turtles with [not link-neighbor? self and shape = [shape] of myself] [
          create-link-with myself [set color green
            set thickness 1]
        ]
      ]
    ] [
         if any? other turtles with [not link-neighbor? self] [
        ask one-of other turtles with [not link-neighbor? self] [
          create-link-with myself [set color green
            set thickness 1]
        ]
      ]
    ]
  ]
  find-all-components
  color-giant-component
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.