Giant Component

1 collaborator

Uri Wilensky (Author)

WHAT IS IT?

In a network, a "component" is a group of nodes that are all connected to each other, directly or indirectly. So if a network has a "giant component", that means almost every node is reachable from almost every other. This model shows how quickly a giant component arises if you grow a random network.

HOW IT WORKS

Initially we have nodes but no connections (edges) between them. At each step, we pick two nodes at random which were not directly connected before and add an edge between them. All possible connections between them have exactly the same probability of occurring.

As the model runs, small chain-like "components" are formed, where the members in each component are either directly or indirectly connected to each other. If an edge is created between nodes from two different components, then those two components merge into one. The component with the most members at any given point in time is the "giant" component and it is colored red. (If there is a tie for largest, we pick a random component to color.)

HOW TO USE IT

The NUM-NODES slider controls the size of the network. Choose a size and press SETUP.

Pressing the GO ONCE button adds one new edge to the network. To repeatedly add edges, press GO.

As the model runs, the nodes and edges try to position themselves in a layout that makes the structure of the network easy to see. Layout makes the model run slower, though. To get results faster, turn off the LAYOUT? switch.

The REDO LAYOUT button runs the layout-step procedure continuously to improve the layout of the network.

A monitor shows the current size of the giant component, and the plot shows how the giant component's size changes over time.

THINGS TO NOTICE

The y-axis of the plot shows the fraction of all nodes that are included in the giant component. The x-axis shows the average number of connections per node. The vertical line on the plot shows where the average number of connections per node equals 1. What happens to the rate of growth of the giant component at this point?

The model demonstrates one of the early proofs of random graph theory by the mathematicians Paul Erdos and Alfred Renyi (1959). They showed that the largest connected component of a network formed by randomly connecting two existing nodes per time step, rapidly grows after the average number of connections per node equals 1. In other words, the average number of connections has a "critical point" where the network undergoes a "phase transition" from a rather unconnected world of a bunch of small, fragmented components, to a world where most nodes belong to the same connected component.

THINGS TO TRY

Let the model run until the end. Does the "giant component" live up to its name?

Run the model again, this time slowly, a step at a time. Watch how the components grow. What is happening when the plot is steepest?

Run it with a small number of nodes (like 10) and watch the plot. How does it differ from the plot you get when you run it with a large number of nodes (like 300)? If you do multiple runs with the same number of nodes, how much does the shape of the plot vary from run to run? You can turn off the LAYOUT? switch to get results faster.

EXTENDING THE MODEL

Right now the probability of any two nodes getting connected to each other is the same. Can you think of ways to make some nodes more attractive to connect to than others? How would that impact the formation of the giant component?

NETWORK CONCEPTS

Identification of the connected components is done using a standard search algorithm called "depth first search." "Depth first" means that the algorithm first goes deep into a branch of connections, tracing them out all the way to the end. For a given node it explores its neighbor's neighbors (and then their neighbors, etc) before moving on to its own next neighbor. The algorithm is recursive so eventually all reachable nodes from a particular starting node will be explored. Since we need to find every reachable node, and since it doesn't matter what order we find them in, another algorithm such as "breadth first search" would have worked equally well. We chose depth first search because it is the simplest to code.

The position of the nodes is determined by the "spring" method, which is further described in the Preferential Attachment model.

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 Preferential Attachment.

See also Network Example, in the Code Examples section.

CREDITS AND REFERENCES

This model is adapted from: Duncan J. Watts. Six Degrees: The Science of a Connected Age (W.W. Norton & Company, New York, 2003), pages 43-47.

Watts' website is available at: http://smallworld.columbia.edu/

The work Watts describes was originally published in: P. Erdos and A. Renyi. On random graphs. Publ. Math. Debrecen, 6:290-297, 1959.

This paper has some additional analysis: S. Janson, D.E. Knuth, T. Luczak, and B. Pittel. The birth of the giant component. Random Structures & Algorithms 4, 3 (1993), pages 233-358.

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:

Wilensky, U. (2005). NetLogo Giant Component model. http://ccl.northwestern.edu/netlogo/models/GiantComponent. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.
Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, 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.

Commercial licenses are also available. To inquire about commercial licenses, please contact Uri Wilensky at uri@northwestern.edu.

Comments and Questions

Click to Run Model

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 setup
  clear-all
  set-default-shape turtles "circle"
  make-turtles
  ;; at this stage, all the components will be of size 1,
  ;; since there are no edges yet
  find-all-components
  color-giant-component
  reset-ticks
end 

to make-turtles
  crt num-nodes
  layout-circle turtles max-pxcor - 1
end 

;;;;;;;;;;;;;;;;;;;;;;
;;; Main Procedure ;;;
;;;;;;;;;;;;;;;;;;;;;;

to go
  ;; if the below condition is true then we have a fully connected network and we need to stop
  if ( (2 * count links ) >= ( (count turtles) * (count turtles - 1) ) ) [
    display
    user-message "Network is fully connected. No more edges can be added."
    stop
  ]
  add-edge
  find-all-components
  color-giant-component
  ask links [ set color [color] of end1 ]  ;; recolor all edges
  layout
  tick
end 

;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Network Exploration ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; to find all the connected components in the network, their sizes and starting turtles

to find-all-components
  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 ]
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
  if not layout? [ stop ]
  ;; 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 0.4 6 1
end 


; Copyright 2005 Uri Wilensky.
; See Info tab for full copyright and license.

There are 11 versions of this model.

Uploaded by	When	Description	Download
Uri Wilensky	over 11 years ago	Updated to NetLogo 5.0.4	Download this version
Uri Wilensky	about 12 years ago	Updated version tag	Download this version
Uri Wilensky	about 12 years ago	Updated to version from NetLogo 5.0.3 distribution	Download this version
Uri Wilensky	over 12 years ago	Updated to NetLogo 5.0	Download this version
Uri Wilensky	almost 13 years ago	Updated to NetLogo 5.0	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Updated from NetLogo 4.1	Download this version
Uri Wilensky	over 14 years ago	Model from NetLogo distribution	Download this version
Uri Wilensky	over 14 years ago	Giant Component	Download this version

Attached files

File	Type	Description	Last updated
Giant Component.png	preview	Preview for 'Giant Component'	over 11 years ago, by Uri Wilensky	Download

This model does not have any ancestors.

This model does not have any descendants.

NetLogo