We have just posted our experimental Social Graph application on Facebook. It offers Facebook users additional insight into their personal social networks, allowing them to identify different social clusters they belong to. In the work and life balancing game, the person with the biggest number of clusters, and not the person with the biggest number of friends, wins.

The most interesting part in developing this application is its use of the so called spring-electrical-graph. It utilises a simple yet powerful algorithm for laying out entity-relationship diagrams (or graphs in a mathematical sense of the word). Any well laid out graph should keep the unrelated entities far from each other while keeping the related ones close. The spring-electrical-graph does exactly this by simulating an environment where all entities are electrical particles of the same charge while the related entities are connected via springs. The rest is left up to physics. The electrical particles repel each other via Coulomb’s law while the related ones pull each other via Hooke’s law due to the springs that link them.

The actual simulation is implemented using the 4^th order Runge-Kutta method for solving ordinary differential equations. Other methods could be used as well but this one was particularly well suited for our use and I had the code available from my Binary Toys project.

While there are other social graphs applications already available on Facebook, Nexus being one of them, ours is a bit more interactive and fun to play with. But we are paying a heavy price for this interactivity in a form of performance degradation for users with a very large number of friends. As the repelling force acts between all entities all the time, for a user that has 1000 friends, we have to apply almost a million forces to our model. And we have to do that four times for the 4^th order Runge-Kutta computation. For everything to run smoothly we would like to do all that at least 25 times per second, which takes our hunger for CPU power up to 100 million computations per second. We soon learned the hard way why Action Script 3 is still just a script, even though we love it.

Click this link to add the SWAT Social Graph to your facebook account: Social Graph

Related Posts

1. In a Facebook world, what’s a social network to do?
2. The Mark Zuckerberg Effect
3. The Open Graph Protocol