This page was automatically generated by NetLogo 5.0.1.

The applet requires Java 5 or higher. Java must be enabled in your browser settings. Mac users must have Mac OS X 10.4 or higher. Windows and Linux users may obtain the latest Java from Oracle's Java site.

In order for this to work, this file, your model file (RandomGraphs.nlogo), and the files NetLogoLite.jar and NetLogoLite.jar.pack.gz must all be in the same directory. (You can copy NetLogoLite.jar and NetLogoLite.jar.pack.gz from the directory where you installed NetLogo.)

The applet will also need access to the network extension. Copy the entire directory for each required extension into the same directory as the applet.

On some systems, you can test the applet locally on your computer before uploading it to a web server. It doesn't work on all systems, though, so if it doesn't work from your hard drive, please try uploading it to a web server.

You don't need to include everything in this file in your page. If you want, you can just take the HTML code beginning with <applet> and ending with </applet>, and paste it into any HTML file you want. It's even OK to put multiple <applet> tags on a single page.

If the NetLogoLite files and your model are in different directories, you must modify the archive= and value= lines in the HTML code to point to their actual locations. (For example, if you have multiple applets in different directories on the same web server, you may want to put a single copy of the NetLogoLite files in one central place and change the archive= lines of all the HTML files to point to that one central copy. This will save disk space for you and download time for your users.)

powered by NetLogo

view/download model file: RandomGraphs.nlogo

You can generate networks using several different models, starting with the Erdös-Renyi (the “randomest”) network model, and a few variations that might represent

e.g. meeting people through your friends (INTRODUCTION model), linking houses or cities with roads (STATIC GEO model), literally running into people and becoming friends (RAND ENCOUNTER model), and adding new nodes to the network (GROWTH).

All except for the GROWTH model start with a fixed number of nodes (detemined by the NUM-NODES). Then edges are added, but just how depends on the model you choose.

The NUM-NODES

Click on LAYOUT to use a spring layout algorithm to reposition the nodes (you will typically want to keep this off while applying the network construction algorithms).

With the NUM-NODES slider you determine the number of nodes in the network.

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 ASP monitor reports on the average shortest path between nodes in the largest connected component only.

The following are the network construction algorithms:

ERDÖS-RENYI constructs a random graph by adding an edge between each pair of nodes with probability PROB-LINK.

INTRODUCTION similar to ERDÖS-RENYI, however, random edges are added only with probability (1 - PROB-INTRO). The rest of the time the nodes try to get one of their friends to introduce them to someone they know.

STATIC-GEO randomly places nodes on a 2-D square area. Keep Layout? OFF so that node positions don’t change while network is being built. Each node tries to connect to its NUM-NEIGHBORS closest neighbors. This means that some nodes end up with more neighbors, because they are the closest choice to some other node even though they already have plenty of closer neighbors.

RAND-ENCOUNTER places nodes randomly on a 2D square area. Keep Layout? OFF so that nodes are moving independently of the links they have (you don’t want them tied down to their friends :) ).They move around randomly until they occupy the same “patch” as another node, at which point they connect.

GROWTH starts out with (NUM-NEIGHBORS + 1) nodes forming a fully connected clique. After this, nodes are added one by one. As nodes are added NUM-NEIGHBORS / 2 edges are added as well (with some randomness so that one ends up with approximately the correct average degree for the entire graph when NUM-NEIGHBORS is odd.

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.

Try looking at how evenly the edges are distributed among the nodes in the different models. Are some nodes better connected than others? How does this come about.

How many closed traids do you see in each network? Which models promote closed triads and in which are they rare? Can you explain why?

Observe differences in the size of the giant connected component for the ER graph and one of the other models using the same average number of neighbors or probability of linking.

Try varying the density of the network. How is the size of the giant component affected? Is the transition gradual or sudden as a function of the network density?

In the INTRODUCTION model, try varying the probability of introductions as opposed to random encounters. How does this affect the eveneness of the degree distribution and the number of closed triads formed?

This model was adapted by Lada Adamic from Uri Wilensky’s Giant Component model 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.

extensions [network] 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 asp ;; average shortest path ] ;;;;;;;;;;;;;;;;;;;;;;;; ;;; Setup Procedures ;;; ;;;;;;;;;;;;;;;;;;;;;;;; to setup clear-all set-default-shape turtles "circle" make-turtles set asp false reset-ticks end to make-turtles crt num-nodes layout-circle turtles max-pxcor - 1 end ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; Network wiring procedures ;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; to all-random setup let thiswho 0 set asp false if (not any? turtles) [make-turtles] ask links [ die ] ask turtles [ set shape "circle" set size 3 ] ifelse prob-or-num? [ ask turtles [ set thiswho who ask other turtles with [who > thiswho] [ if (random-float 1 < prob-link) [ create-link-with myself ] ] ] ] [ 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-current-plot "degree distribution" set-plot-x-range 0 (max [count link-neighbors] of turtles) ; set asp network:mean-link-path-length (turtles with [color = red]) links tick end to introduction setup let friend nobody let thiswho 0 let num-links-want 0 set asp false if not any? turtles [make-turtles] ask links [ die ] ask turtles [ set shape "face happy" set size 3 set color pink ] ifelse prob-or-num? [ set num-links-want prob-link * ((count turtles) * (count turtles - 1) / 2) ][ set num-links-want (floor (num-nodes * num-neighbors / 2)) ] let num-have 0 while [num-have < num-links-want] [ ask one-of turtles [ set friend self set thiswho who ifelse ((random-float 1.0 < prob-intro) and (any? link-neighbors))[ ask one-of link-neighbors [ if any? link-neighbors with [who != thiswho] [ ask one-of link-neighbors with [who != thiswho] [ if not link-neighbor? friend [ create-link-with friend set num-have (num-have + 1) ] ] ] ] ] [ ask one-of other turtles with [not link-neighbor? self] [ create-link-with friend set num-have (num-have + 1) ] ] ] ] find-all-components color-giant-component set-current-plot "degree distribution" set-plot-x-range 0 (max [count link-neighbors] of turtles) ; set asp network:mean-link-path-length (turtles with [color = red]) links tick end to static-geo setup let thiswho 0 set asp false if not any? turtles [make-turtles] ask links [ die ] ask turtles [ set shape "house" set color white set xcor random-xcor set ycor random-ycor set size 5 ] ask turtles [ set thiswho who ask min-n-of num-neighbors other turtles [distance myself] [ if not (link-neighbor? myself) [ create-link-with myself ] ] ] find-all-components color-giant-component set-current-plot "degree distribution" set-plot-x-range 0 (max [count link-neighbors] of turtles) ; set asp network:mean-link-path-length (turtles with [color = red]) links tick end to growth ca reset-ticks crt (num-neighbors + 1) [ set shape "person" set size 5 ] ask turtles [ ask other turtles with [not link-neighbor? myself] [ create-link-with myself ] repeat 3 [do-layout] ] repeat (num-nodes - num-neighbors - 1) [ crt 1 [ set shape "person" set size 5 set xcor random-xcor set ycor random-ycor repeat 50 [do-layout] ] ask n-of (floor (num-neighbors / 2)) turtles [ create-link-with one-of other turtles with [not link-neighbor? self] ] if (random-float 1 < (num-neighbors / 2 - floor (num-neighbors / 2))) [ ask one-of turtles [ create-link-with one-of other turtles with [not link-neighbor? self] ] ] ] repeat 500 [do-layout] find-all-components color-giant-component set-current-plot "degree distribution" set-plot-x-range 0 (max [count link-neighbors] of turtles) tick ; set asp network:mean-link-path-length (turtles with [color = red]) links end to rand-encounter setup let thiswho 0 if not any? turtles [make-turtles] ask links [ die ] ask turtles [ set shape "person" set size 5 set xcor random-xcor set ycor random-ycor set color (gray + 2) ] let links-wanted num-nodes * num-neighbors / 2 while [(count links) < links-wanted] [ ask turtles [ rt random 360 forward 1 ask other turtles-on patch-here [ if not link-neighbor? myself [ create-link-with myself ] ] ] ] find-all-components color-giant-component set-current-plot "degree distribution" set-plot-x-range 0 (max [count link-neighbors] of turtles) ; set asp network:mean-link-path-length (turtles with [color = red]) links tick end to calc-asp set asp network:mean-link-path-length (turtles with [color = red]) links 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] 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.