NetLogo 2.0: Graphs, and Nodes, and Edges Oh My!

by Owen Densmore

Related link: http://ccl.northwestern.edu/netlogo/




In our

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.







In this

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

Small World

graph, as described in

Six Degrees

by

Duncan Watts
, or in Power Law networks as described in

Linked

by

Albert-Laszlo Barabasi
. See this

Power Law Study

for an overview of these networks.




One example is the

Travelling Salesman

(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

Graph Layout

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!