A student in my ICPSR ABM workshop was having trouble creating a networked interaction structure with particular properties and asked for my help. The problem was actually quite sophisticated. She needed a tree graph wherein she could specify both the total number of nodes and the number of terminal nodes for graphs of different depths (layers) but she wanted the overall structure to be as random as possible within those constraints. The problem was non-trivial, but I did manage to write a procedure to create precisely the graphs she needed…and now I'm sharing the method with the world. In addition to the examples and explanations below you can download my personal parameterized tree graph code example and use that to freely steal my code for your own use.

This code was written in Netlogo version 4.0.2 and should work without alteration in 4.1 versions as well. The first thing is that you're going to need some specific breeds and a turtles-own variable in your code, so add these to the top of your procedures:

breed [terminal-nodes terminal-node]
breed [intermediate-nodes intermediate-node]
breed [centrums centrum]
turtles-own [level]

To generate a graph parameterized in the desired way you need to enter the required parameters. You need the total number of nodes, the percent of those which should be terminal nodes, and the number of desired levels of the graph. The levels go like this: the centrum is level 1, direct connectors are level 2 etc, their connectors are level 3, etc. The minimum number of level that a graph could have with this construction is 3 (because if there were two then every non-centrum node would be terminal and there is no need to use such a fancy generating method). The picture here has four levels and the one at the top has 6. There is no maximum number of levels that this technique can handle.

After your parameters are set (e.g. from the interface, but you'll need different names for the global variables defined there) you put in the following line of code in your setup procedure (or wherever you want to create the tree graph).

create-random-tree population layers %-actors

This will create a mostly random tree graph corresponding to those parameters as long as one is possible (more on possibility later). Here is the method that you need to copy and paste into your procedures tab somewhere.


to create-random-tree [number-of-nodes levels %-terminals]
   set-default-shape turtles "circle"
   create-centrums 1 [
       set color gray
       set level 1
   ]
   create-intermediate-nodes (number-of-nodes - (number-of-nodes * %-terminals) - 1) [
       set color green
       set level 2 + random (levels - 2)
   ]
   ask turtles with [breed != centrums] [
       ifelse any? turtles with [level = ([level] of myself - 1)]
            [ create-link-with one-of (turtles with [level = ([level] of myself - 1)]) ]
            [ create-link-with one-of centrums
               set level 2 ]
   ]
   if count intermediate-nodes with [count link-neighbors = 1] > number-of-nodes * %-terminals [
        user-message (word "That's not enough terminal nodes for this graph.")
       stop
   ]
    ask intermediate-nodes with [count link-neighbors = 1] [
        hatch-terminal-nodes 1 [
           set color red
           create-link-with myself
           set level ([level] of myself + 1)
       ]
   ]
   let remaining-terminal-nodes number-of-nodes * %-terminals - count terminal-nodes
    repeat remaining-terminal-nodes [
        ask one-of turtles with [breed != terminal-nodes] [
           hatch-terminal-nodes 1 [
                set color red
               create-link-with myself
           set level ([level] of myself + 1)
           ]
       ]
   ]
   layout-radial turtles links one-of turtles with [breed = centrums]
end


This could probably be done more generally (e.g. without the need to create breeds) but it works well as is and beyond this the cost for me to clean it up further is probably more than the added benefit to anybody.

As mentioned earlier the parameterization puts some restrictions on the graph construction and vice versa. The main restriction is that since the number of terminal nodes and total nodes are both specified the graph construction must force a certain number of nodes to be non-terminating. As a result, for a given number of total nodes and layers there is a minimum number of nodes which must be terminal nodes. For example, if there are three layers and 100 nodes then at least 50 must be terminal nodes, because there can be at most 49 intermediate nodes (plus the centrum). Why? Because if there were 50 intermediate nodes and 49 terminal nodes then there would be an intermediate node without a terminal node to attach to it...thereby making it terminal contrary to the specification. But note that if there are more layers then there can be intermediate nodes connected to other intermediate nodes so the percentage of terminal nodes can be pushed smaller.

But also notice that there is a minimum number of intermediate nodes that can produce a graph of a desired depth. Specifically, there must be at least (layers – 2) intermediate nodes to create a path from the centrum to the terminal node of length layers. And because the graph is randomly generated it's very unlikely that the intermediate nodes would arrange themselves in a line to achieve that number of layers. So if the exact number of layers is important you then you need to be cognizant of this and/or change the code appropriately.