Balancing Graphs in O(n*log(n))

The Barnes-Hut algorithm is used to model N-body systems more efficiently, at the expense of precision. However, the improvement in performance is tremendous: from O( n² ) to O( n*log(n) ). For reference, this is what that looks like:

Since our force-based approach to computing graph layout is essentially nothing other than an N-body simulation, and we don't require great precision anyway, this algorithm seems perfect for us to use. The way it works is basically this:

• The set of nodes is sorted into a quadtree, which is essentially a binary tree, but with an added dimension
• Each of the quadtree sectors keeps track of its mass and center of mass
• To compute the forces, the tree is traversed and for points that are "far" from a certain center of mass, only the force from the node to that center of mass is calculated, as opposed to each force between all nodes

This leads to a significant decrease in overall calculations that needs to be done, since distant nodes no longer need to interact directly. There is some overhead on creating the quadtree every frame, but the growth of this is also O(n*log(n)). If you want to learn more, here is a very good explanation of the algorithm complete with pseudocode (in German, but the code is understandable anyway). 

I haven't had time to implement this algorithm in our Qt application to graph Wikipedia, however I managed to code up the basic algorithm in Python. The improvement is tremendous, before I was never able to reasonably run a simulation with more than 80 or so nodes in Python, now even systems up to 350 nodes run at a reasonable framerate.

Illustration of the quadtree (unbalanced)

The same graph after balancing

The algorithm can also be parallelized very well, so the potential of this is tremendous, with good implementation and appropriate hardware we could realistically graph all of the German Wikipedia (~1.3 million articles), maybe more. 

The full Python code is here.

A little Preview

So, there haven't been many posts on here the last few days, but certainly not because I've gotten lazy. Robert and I have been coding like crazy on the WikiGraph project this week, with a few sessions of 6+ hours at times.
We're coming along quite well, we've managed to implement multithreading on all of the force calculations, which has given us a speedup factor of 4 on my machine, but the implementaton allows for an arbitrary number of threads and automatically creates as many as the machine it runs on has cores (or virtual cores, with hyperthreading). Along with that comes the improved algorithm, which again about doubles performance.
This allows us to display some really large graphs - by really large, I mean up to around 6000 nodes at the moment, and that limit is mostly due to some unexpected behavior (nodes flying off to infinity), which we suspect is a result of the parameters we use in our algorithm. I expect that by the time we're releasing a beta version (which at current development speed would be sometime next week), we can display graphs of maybe 15000 nodes, which is around 3 levels deep of pagelinks if all links are loaded.
OpenGL support is also something we're implementing at the moment, since CPU rendering of these graphs actually takes up more resources and time than calculating a single iteration of forces, so outsourcing that to a graphics card will definitely help performance.
Apart from that, other changes will mostly be in UI and design, adding options for users to alter the graph and such.

Even though we aren't ready to put out a stable and usable release yet, we've already created some pretty neat visualizations:

Close up of an earlier version, 2 levels centered around Quicksort

3 levels deep (German Wikipedia), also centerd around Quicksort I believe. We're actually displaying over 5000 nodes here.

3 levels around Mathematics, over 6000 nodes. This one is not quite stable, the Mathematics article needs to be fixed otherwise it flies off. Looking into why it does that, all other nodes seem to behave as expected.

An improved algorithm for N-body simulations

TL;DR: A simple algorithm that speeds up force calculations for n-body systems by a factor of nearly 2.

So the last post on here was about graph balancing using a spring-electrical model, in which each node exerts a repulsion on each other node according to Coulomb's law, and each edge attracts adjacent nodes according to the spring equation.
This is a good example of an N-body problem - the most well-known one is that of planetary/gravitational systems - and one unfortunate thing about these is that modeling them can be quite slow.
Intuitively, the first algorithm that comes to mind is simply iterating through all the bodies, and for each one iterate through each other body and calculating the force they exert on each other. For n bodies (nodes), this results in (n-1)^2 for the whole system - (n-1) because the body does not exert a force on itself. This is of course is a growth rate of O(n^2), not very efficient.
But there's an easy improvement that can improve on this quite a bit making only minimal changes to the algorithm:

• We start with the first body, and iterate through all the other body, calculating each force and adding it to the nodes net force
• Since the forces between each two bodies will be equal and opposite, we now subtract this force (or add it negatively) from the other bodies' net forces, and then add a reference to the original body to a list (or in Qt a QSet, which is faster) that keeps track of all the bodies that have already been calculated
• We go to the next body, and again iterate through all other bodies, except now we skip any bodies already in our list of calculated bodies. This results in one less calculation being performed with each body we iterate through

And that's about it. With each node, we have one less calculation to perform, so our total number of operations is now:

This is significantly better, in fact:

 

For very large systems, this algorithm approaches to be twice as fast.

I implemented this algorithm in our Wikipedia grapher, and it's working quite nicely. Here's one of the graphs I made with it today(554 nodes, zoomed out):

There are also n log(n) algorithms for these systems, but frankly I don't understand how they work well enough to write about or implement one yet, so I'll call it a night for now and get to those another time.

Graphing wikipedia - update

I fixed up the crosslinking on our wiki grapher, so now each expanding node checks the list of existing nodes and connects them rather than creating a new node for every page it finds. A next step would be to use Wikipedias incoming links feature and also check node links in the other direction, however this would probably impact performance as a full web request needs to be made for every single node at creation, not just after it is clicked/expanded. Anyway, this fix already makes the resulting graph a lot more interesting:

By the way, this is centered around Mergesort and outgoing links are limited to 10 for testing purposes. I might keep it that way and then decide on a way to display the 10 (or so) most important links, although it'll be difficult to decide how to judge link importance.

Visualizing Pagelinks

In this blog's last post I talked about force graph balancing and some of the things it can be used for, more specifically visualizing networks such as links between webpages. Robert Brünig and I are currently working on a small projects that does just that, by scraping pages (currently Wikipedia articles) for links and then representing them graphically. It's written in C++ using the Qt framework. This would've been fairly simple in Python, however for larger networks the program becomes very computationally intensive, and we wanted to get good performance. Besides, using C++/Qt allows for much more stable deployment, and Qt has a lot to offer in terms of modules (widgets, graphics, web access and such). Screenshot below.

As you can see, the graph quickly grows quite large for wikipedia pages due to the high number of pagelinks on each article. We're thinking of focusing on Youtube instead, visualzing a gives clips related videos - perhaps we might even be able to embed the videos in the nodes, so that they can be watched directly in the program.

There are also still some issues with the graph balancing algorithm, we still need to find a good combination of attraction/repulsion/weighting parameters that produces a smooth and stable graph that balances quickly.

Automating Graph Layout

When working with graphs (the nodes and edges kind) on a computer, good arrangement and layout of the nodes is an interesting problem. To us, there is usually an obvious or at least visually appealing way to draw a graph, but a computer has no intuition (yet?) so finding a good layout for the graph can be difficult. It isn't hard to represent a graph as such in a computer, in fact things like adjacency matrices are probably much easier for a computer to read than a human, especially as you add more nodes.

There's also the problem of deciding what sort of layout is the right one for a given graph in the first place: Say you want to plot three things: A mesh network, a tree graph and a import/export relations between countries. Should each be laid out according to the same rules? Probably not - in a mesh network, we do not expect edges that reach far from one side of the graph to the other, so we can generally just place adjecent(in the sense that they are connected) nodes adjacent(location) to each other. A tree graph has a much different structure, in fact as the name implies, we would choose a tree-like layout. Import/export routes would of course be graphed according to actual geographical location, and even if not, the nodes are connected much differently. You might also want to assign a heavier weight or larger size to some nodes (according to GDP, for example).

For all of these, one can create different algorithms that find a good, or even optimal layout. Wikipedia actually has a page about some of them. 

You may remember that I briefly wrote about a project I was considering, namely an interactive Wikipedia (or other webpages, for that matter) grapher. The idea is this: you give the program a starting page, and it then represents this page as a single node. When you then click it, the page is parsed for links to other Wikipedia articles, and each is added as a node on the graph, with an edge to the original article. You can repeat this process for each new node, and edges are added whenever one article links to another one on the graph. 

I've started working on this project recently, and have found a good (but unfortunately somewhat slow - about O(n^3) ) algorithm to draw this graph. Force-based layout creates a layout by treating each edge as a spring that pulls adjacent nodes together, while simultaneously repulsing all nodes from each other using something resembling Coulomb's law, and then iterating until an equilibrium of forces is found. For now, I've only implemented a rough version of this algorithm in Python, but for the final program I'll be using C++, mainly to get better performance for the graphing, but also to gain a bit more experience with it. The drawing will probably be done in SDL, it seems simple enough to use. 

Source code of the above animation's algorithm (graph was generated randomly):

Project Ideas

Doing is the best way to learn, and since learning is what we're here for, let's do some stuff. I've had a number of different ideas for projects recently and not so recently, so to offer you some inspirations and perhaps for me to see if any of these still make sense when you see them typed out, I've compiled a little list of them. (Some of these are actually projects I've already started working on)

• "Multiplayer" Paint. Basically, this would be like a chat program that lets two (or more?) people draw on the same canvas as one would in mspaint. I would implement this in C++, just because I want to learn more about it (and graphics / network programming) but also because most people don't have Python interpreters with pygame on their machine. It might be time for something different :)
• Javascript multiplayer Paint! Use a JS canvas for client side, and save the changes to canvas stored server side (maybe use php, or node.js for serverside scripting?) Then, everyone who visits the page can draw on it for everyone else to see. Obvious downsides of this however are the fact that this is still the internet, and I suspect sooner or later (sooner) it will meet a similar fate tot that of Chatroulette
  
• A 3-4 DoF Robotic arm. It doesn't have to be a very good one either, just to keep costs down. Forward and inverse kinematics are pretty interesting, and this would be a good way to learn and practice both. Servos can be picked up pretty cheaply as well, and the whole thing could be run from an Arduino - the only real difficulty in this would be the mechanical parts, I have no good way of making them properly. I got this idea from...
  
• .. building a hexapod. 3DoF would be minimum for each leg to be able tog et decently smooth motion, the problem is that this would be a rather costly product (for me, at least)
• A simple webcrawler. I don't know what you would use it for, but my ideas were perhaps a Reddit bot (find/keep track of reposts, produce statistics based on comments, find most used pun of the day, etc.), or a Wikipedia crawler (create a graph of pagelinks, those are always neat)
• On a similar note, implementing a graphing layout algorithm - finding a good layout for graphs (graph meaning a set of nodes connected by edges) automatically. There are different ways to implement this, the spring model seems like the simplest: each edge is like a spring that pulls two connected nodes together, or pushes them apart based on their distance from each other. One could also base the pushing/pulling force on the "weight" of each node (weight could be number of incoming edges, for example)
• implement quantitative stock trading algorithms. This is something I personally find really interesting, though I haven't worked on it much. Wikipedia has a nice page about the different algorithms that are used today. A technical problem that needs to be solved first is getting a decent sample of historical data for a given stock, as this is very often necessary for such algorithms.

Of course these all aren't new ideas, but I've found that I usually have good ideas while working on something else, and these are just inspirations for you anyway. Potentially all of these are good for learning something new!