NetLogo 2.0: Graphs, and Nodes, and Edges Oh My!
by Owen Densmore
Related link: http://ccl.northwestern.edu/netlogo/
earlier look at NetLogo, we saw how to execute simple commands in the command center, how patches and turtles/agents work, and how to run models such as the Schelling Segregation model in the Models Library included with NetLogo.
latest release, the NetLogo team have added the ability to add graphs (collections of edges and nodes) to a model. (Note that NetLogo 2.0 requires Java 1.4) This opens up the possibility for more sophisticated models. For example, the agents can now live in a
graph, as described in
Duncan Watts, or in Power Law networks as described in
Albert-Laszlo Barabasi. See this
Power Law Study
for an overview of these networks.
One example is the
(TSP) route problem: how to choose an optimal route among several cities. To prove this new NetLogo facility worked for complex problems,
Seth Tisue, one of the NetLogo developers, converted a Repast TSP to run in NetLogo! Click on the image to the left to see a picture.
This TSP model was done using an
Ant Colony Optimization
algorithm, where several ants placed on home nodes (red nodes in the image) traverse the graph nodes, laying down pheromones which evaporate over time. The ants preferentially chose "warm" paths .. those with more pheromones. This evolutionary algorithm quickly evolves toward near-optimal solutions.
To learn how edges and nodes all worked in the new NetLogo, I wrote a simple
model, which uses springs and forces to take an initial random collection of nodes and edges, and have them evolve toward a more "pleasing" or understandable form.
The model used for edges is fascinating: an edge is simply a "turtle" that is very long and skinny, connecting two other turtles of type "node". This requires the "patch coorinate system" used by NetLogo to allow fractional values. Thus a node can be on patch 1.5, halfway between patch 1 and two. In the TSP images and the Graph Layout example, the edges are numbered at the edge turtle's patch position, the center of the edge. On the left, we see two nodes connected by an edge. The numbers are printed at the turtle's position, so the edge turtle is halfway between the two node turtles and is long enough to connect them and has the correct "heading" to do so.
Give NetLogo a try and let us know what you think, its fun to play with and getting more mature every day!