Sunday, June 1, 2014

I Think That I Shall Never See...

....A graph lovely as a tree. (With apologies to poet Joyce Kilmer.)

A couple of months ago on Stack Overflow, a questioner asked: How to visualize a large network in R? The example uses the R igraph function:

set.seed(123)
g <- barabasi.game(1000)

Now, with Barabási-Albert, a value of m = 1 creates a network that is a tree, and m = 1 is the default value for the igraph barabasi.game() function. So the questioner's network was a tree, which is actually not obvious from the Fruchterman-Reingold layout the questioner applied to the network.

Since there is a simple implementation of BioFabric for R called RBioFabric, I provided an answer to the question. But as a Stack Overflow newbie, I could not originally post an image. But last week, I finally had enough reputation to add a figure, so I added an image of the questioner's network laid out using the BioFabric default layout. The inset shows a detail of the upper left corner:

Network Visualization with BioFabric
Click on image for larger picture
Now, BioFabric's default layout allows us to immediately conclude that this network is a tree, by simply looking carefully at the lower edge of the network. That edge is at an absolutely uniform 45 degrees, and a quick scan along the edge reveals no gaps or hiccups. You can also see that the graph only has one connected component. This 45-degree rule means that every edge has a 1:1 association with a node in the network, starting with the second node. So the network has n nodes and (n - 1) edges, and thus it is a tree.

So if you are looking a BioFabric network and think that you never see anything but a uniform, unbroken 45-degree lower edge, you can be sure your graph is lovely as a tree.

No comments:

Post a Comment