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.
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)
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: |
| |
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.