layout

created with NetLogo

view/download model file: layout.nlogo

WHAT IS IT? ----------- This is a dynamic graph layout model using springs and repulsion forces to create a pleasing layout. HOW IT WORKS ------------ The model uses two parameters (number-of-nodes and edge-ratio) to create the graph. For example, if the number of nodes is 10 and the edge ratio is 1.2, then the target graph would have 10 nodes and 12 edges. We currently provide two graph types: random and power-law. The random graph simply connects random pairs of nodes together until the graph is fully connected and the number of edges is equal to or greater than the desired number. Three parameters are used to adjust the layout while the model runs. The spring-force is how strongly the spring pushes/pulls the nodes. The spring-length is the 0-force length of the spring. Greater lengths attract, lesser repel. The total force is the spring-force times the amount the spring differs from its spring-length. Finally, there is a general repulsion between all nodes, specified by the mutual-repulsion parameter. It uses an inverse-square calculation rather than the spring's linear one. HOW TO USE IT ------------- Click on setup to initialize the graph. Click on go to start the model. While the model is running, you can change the three spring/repulsion parameters. You also can grab a node with the mouse and move it around to help untangle the graph. THINGS TO NOTICE ---------------- This is a fairly simple model. The main thing to notice is that such a simple layout algorithm does a reasonable job of making the graph untangled. The power-law graph uses the Barab�si method (Google for his group's papers) which creates fairly "bush-y" power-law graphs. His work helped us understand why web and internet graphs are often power-law by noting that these nets grow 1) progressively from small networks, and 2) link probabilistically to nodes according to "popularity" .. i.e. by number of links. THINGS TO TRY ------------- Try various settings for number of nodes and edge ratio. Grab nodes with the mouse while the model is running. Change the spring and repulsion settings while the model is running. Try changing the graph type (power-law switch) between random and power-law. What are the differences that you see? Try this: set the number of nodes to max and the edge ratio to 1.2 or so. Click setup several times in succession, first with powerlaw? on, then off. What differences does the edge histogram show? Movies: (Use this with local models, not via the web) You can make a sequence of images for creating a movie of the model. To do this, type 'set filename "movie"' in the command center immediately after clicking "setup". When the model sees the filename has been set to a non-null value while running ("go"), it will take a picture every step of the model. The filenames will look like movie0001.png movie0002.png ... etc. You can stop the process by clicking on "go" when you have enough images. Alternatively, the model can be stopped by "set stoptick 100" or some similar value, again using the command center. UI Changes: The size of the graph world can be changed by editing the graphics window. Try changing the patch size to a smaller number (5, say) and making the graph larger (35 x 35). Just click the "more" button on the graphics window. You can change the max number of nodes too by selecting its slider and editing it. I've tried 100, with small edge ratio and it worked fine. Programming changes: You could modify or replace the two graph construction algorithms, or add additional ones. It would be interesting to see how a small world cluster would evolve under springs and repulsion. The "go" procedure can be modified to use other layout algorithms. Research: Modify the step procedure to periodically look for edge crossings and try to eliminate them. EXTENDING THE MODEL ------------------- Other kinds of graphs would be interesting to add. See http://backspaces.net/PLaw/index.html for a discussion on creating and exploring power-law and small worlds graphs and their searching properties. NETLOGO FEATURES ---------------- This uses the generalizations NetLogo introduced which allow agents to be of any size and to use fractional coordinates. Amazingly enough, the edges in the model are really a breed of turtle whose shape is a line, whose heading is the direction of the edge and whose midpoint is halfway between the nodes. This is genius and works beautifully with the NetLogo concept of agents and patches. I never would have thought this could have worked, especially with such outstanding ease of programming and good performance. RELATED MODELS -------------- The PLaw work above prompted my looking into NetLogo implementations like this. And the models Seth Tisue showed me while the edge/node development was underway were essential. The GraphVis graph drawing suite from ATT were used extensively in the power law study, for example: http://backspaces.net/PLaw/html/graphs-TdS+.html Their site is: http://www.graphviz.org/ The pioneering work by Caida (http://www.caida.org/) and kc claffy (http://www.caida.org/home/seniorstaff/kclaffy.xml) to study the web's "shape" are central to any interesting computer graph investigations. The Santa Fe Institute's graph theoretic work is fascinating, including models of the internet, virus propagation, small worlds. This work has spawned a huge diversity of investigations world wide. Contact me (owen@backspaces.net) if you are interested in further pointers and potential projects. CREDITS AND REFERENCES ---------------------- Seth Tisue showed me the basic ideas behind how to use fractional coordinates and arbitrary shapes for creating nodes and edges. Thanks! Arthur VonHoff created a similar layout demo for the Java SDK. Steve Guerin suggested the repulsive force idea. See his Redfish.com site for great demos of this and other visualization and modeling ideas.