Banish the Bipartite Blues!

I'm going to take a detour yet again from my bank network series to talk about an unrelated topic, which is the problem of using the default layout algorithm on a bipartite graph. To begin, let's say we want to load the bipartite graph that is described by this .sif file into BioFabric:

Click to enlarge

As a reminder, a bipartite graph is one where each and every node belongs to one, and only one, of two sets of nodes (e.g. A and B). Furthermore, every edge in the graph goes between a node in set A and a node in set B. In the above example, every node in A is connected to every node in B, and vice versa.

So if you just import the above .sif file into BioFabric, you get the following result:

Click on picture to enlarge

And if you turn shadow links and zone shading on, you get a clearer picture of what is going on:

Click on picture to enlarge

These views are probably not the way you want your bipartite network to look. This is a case where the default layout algorithm (remember: breadth-first search from the highest degree node, traversing neighbors in order of decreasing degree) does a substandard job. In this particular case, since all the nodes in the network have the same degree, the algorithm will choose the nodes in alphabetical order, i.e. A1 comes first. Then, since A1 is not connected at all to any of the other A nodes, the B nodes all get laid out next. Finally, when B1 gets its chance, the remaining A nodes will get assigned to the last rows. So the set of A nodes do not get assigned to a contiguous run of node rows.

The preferable arrangement will have all the A nodes show up before the B nodes. This is pretty easy to accomplish, using the Layout->Layout Using Node Attributes... feature from the main menu. First, you need to create a node attribute file, which looks like this:

Click on picture to enlarge

Note carefully that the count of rows starts at 0. Furthermore, all nodes need to be present, and there can be no omitted or duplicated row numbers. If a node that is not in the graph is specified, you will also get an error. Finally, the "Node Row" first line and the " = " tokens are required. My apologies, but errors are not called out with the offending line identified (a necessary future enhancement).

After creating that file in a plain text editor (i.e. not Word), just load it in using the aforementioned Layout->Layout Using Node Attributes... command, and the result will look like this, with a nice point symmetry and contiguous row assignments for both node sets:

Click on picture to enlarge

So if you find yourself working with a bipartite network, keep this technique in mind to get the best network arrangement!