Random graph demo

What a random graph is, in practical terms

A random graph in this context is a graph of n vertices where each possible edge is included with some probability p. That is the textbook description and it is enough to read this page. If you want the formal version, Wolfram MathWorld covers it in proper notation.

For the demo, what matters is that you have a slider. On one end of the slider is a graph with almost no edges. On the other end is a graph with almost all possible edges. The viewer has to lay out everything in between, in three dimensions, while you move the slider.

What you actually see

A typical run looks like this:

1. Sparse end. The vertices spread out. Many of them have no edges at all. The few edges that exist look like loose threads. The picture is calm.
2. Mid range. Clusters start to form. Some vertices are noticeably more connected than others. The picture has structure you can describe.
3. Dense end. Almost every vertex is connected to almost every other vertex. The layout cannot maintain useful separation. The picture becomes a tight ball of edges.

The middle range is where the demo is most instructive. The picture at the dense end is similar across most viewers. The picture at the sparse end is almost trivial. The transition is the part that varies.

Why this demo exists

A graph viewer that handles 50 nodes can look great. A graph viewer that handles 500 nodes with a moderate edge probability is doing real work. The random graph demo is a quick way to find out where a viewer stops being useful and starts producing pictures that confuse rather than inform.

Three behaviours worth paying attention to:

• When does the viewer start collapsing the layout? The point at which the picture stops being readable says a lot about the layout under pressure.
• How does the viewer handle a sudden change in density? Push the slider quickly and watch the response.
• How quickly does the viewer settle? A viewer that takes a long time to find a stable layout under moderate density will struggle on real workloads.

A small parameter table

The way the demo behaves depends mostly on three values. They are worth keeping in your head while you read the picture.

If you are reimplementing this demo in a current library, those are the knobs to expose.

A conceptual sketch in pseudo-code

You do not need to run the original viewer to think about how this demo is built. The client side is roughly:

for each vertex v in 0..n-1:
    create_vertex(v)

for each pair (i, j) where i < j:
    if random() < p:
        create_edge(i, j)

That is the whole shape of the construction. The viewer takes over from there. Layout, redraw, and re-layout happen continuously while the program runs.

If you want to add a slider, the pattern looks like:

on slider change to new_p:
    if new_p > old_p:
        for each missing edge (i, j) with random() < (new_p - old_p) / (1 - old_p):
            create_edge(i, j)
    else if new_p < old_p:
        for each existing edge with random() < (old_p - new_p) / old_p:
            remove_edge(i, j)

That is not a perfect implementation. It is enough to show how the demo can stream changes into the viewer instead of rebuilding the graph each time.

Reading the picture honestly

A few cautions worth keeping in mind:

• A random graph picture should not be read as a structural diagram. There is no hidden meaning to a particular cluster. Re-running the demo will produce a different picture.
• The point at which density makes the picture useless is approximate. Different viewers reach it at different densities.
• A single still image of a random graph is mostly aesthetic. The demo earns its value in motion.
• A random graph is not the same as a real-world network. Real networks have heavier tails, more structure, and more correlation between neighbouring vertices.

Where this connects to layout theory

The random graph demo is also a small introduction to layout theory. The same forces that shape this demo - attraction along edges, repulsion between unrelated vertices, damping to keep the picture stable - are the same forces that drive force-directed layouts in general.

If you find yourself wanting to read more about that, the demo index keeps a short list of the layout mistakes that the demo set surfaces. The random graph layout lab note goes into a little more depth on the specific behaviours that random graphs expose in force-directed layouts.

A note on running the original demo today

Like most of the older Ubigraph examples, this demo was written against Python 2 and the older XML-RPC client library. The shape of the calls translates cleanly to current tooling. The docs index and the XML-RPC graph control lab note cover the translation.

Where to go from here

• Demo index
• Random binary tree demo
• Animation demo
• Docs index
• Random graph layout lab note

If you came in from an old link, nothing has been moved. The demo lives at the same path it has always lived at.