LJGraph: Graph Visualization Using Physical Simulation

Abstract

LJGraph is a graph visualization system written using PyCUBE. Given a "graph" - that is, a set of vertices and a set of edges connecting those vertices - the question arises how a computer can draw this graph in a way that is aesthetically pleasing and brings out any internal structure the graph my have. LJGraph accomplishes this by modeling the graph's vertices as charged particles and the graph's edges as damped springs. When the system is set into motion, the springs tend towards their natural length, and the particles tend to push each other apart.

To demonstrate whether this type of graph drawing will work, LJGraph uses the graph of LiveJournal users' friends networks as samples of real-world data. When a user creates a LiveJournal online weblog, the user creates a list of his or her friends who also have journals. LiveJournal publishes this data in machine-readable format, making it easy to retrieve a user's friend data. Mathematically, users can be represented as vertices of a graph and friend relationships as directed edges in the graph.

The source code to LJGraph is available and released into the Public Domain.

LJGraph was written by Jacob Lee for Math 198: Hypergraphics, Spring 2005. This page last modified May 8th, 2005 by Jacob Lee.

Usage

ljgraph.py [username]

The following special usernames are recognized:

  circle [n] - n vertices connected in a circle
  complete [n] - n vertices with all possible connections
  cube - a 3x3x3 cube
  hypercube - a 2x2x2x2 hypercube
  random [v] [e] - v vertices connected with e random edges

Keystrokes inside the program:

  i - enable/disable ion forces
  s - enable/disable spring forces
  n - show/hide LiveJournal usernames
  p - perturb the graph (change every vertex's velocity by a random amount)

Examples

In LJGraph, vertices start out randomly placed. The following are screenshots taken at the start of the simulation and after the simulation has achieved an equilibrium.

A LiveJournal user's friends
Before:After:
A circularly connected graph
Before:After:

Possible Improvements

It is possible to run the simulation in two dimensions without any problems by changing a constant, although some new terms would need to be added to the energy calculations to make the results in 2D look good. Generalizing the simulation to four or more dimensions requires the changing of surprisingly few hard-coded values, but one would have to both come up with a 3D projection and determine how higher-dimensional simulations would be more useful or interesting.

The helper classes (the graph and LiveJournal code) are well-constructed, but some of the PyCUBE code is messy and less object-oriented than it could be. Spending a day cleaning it up would make it easier for others to extend the simulation.

References

Di Battista, Eades, Tamassia, Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall. 1999.
This book provides the ions and springs algorithm used in LJGraph.
Cruz, Tamassia. "Tutorial On Graph Drawing". http://www.cs.brown.edu/people/rt/papers/gd-tutorial/gd-constraints.pdf
This tutorial provides a nice general overview of the problems involved in graph visualization.