Forces of attraction

by

Peter Boothe and I are building a software tool for visualizing the Gnutella peer-to-peer network topology. Our dataset is huge, and comes from Dan Stutzbach’s PhD work. (Click here for publications by Dan).

Anyway, Peter and I designed a physics model to automatically layout the graph. Each node is a magnet, which repels other nodes. Each edge is a spring, which attracts conjoined nodes. I tip my hat to Peter for implementing an efficient quad-tree and N-body engine. Unfortunately, the Gnutella data contains 150,000+ nodes per snapshot. (That’s a really big graph!) Even on a quad-core PC with 4 GB RAM, our physics engine runs like a snail.

So, today I parallelized the code. . . but the improvement was only about 15%.

The bad news is that our software needs a lot of work before we can effectively visualize Gnutella data. However, the good news is that our software works really well for small graphs (like Internet AS data). We might not be accomplishing science, but at least we have a cool toy!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: