Visualizing Link Communities

When YY Ahn, Jim Bagrow, and I published our paper on communities of links in complex networks, we did share the code for the algorithm, but one of the essentials missing from our package was a good way to visualize the highly overlapping link communities.

Link-communities Visualization

Thus, I’m delighted to report that Rob Spencer over at Scaled Innovation has done a great job of visualizing the detected link communities (including a new client-side implementation, I might add). The technical details are interesting and available.

The example displayed above is lifted from Scaled Innovation and shows the network of characters in The Wizard of Oz. In addition to the central visualization reproduced above (see below for details),  the page also shows the full link dendrogram and many other treats; everything is beautifully crafted. Note the community assignment matrix on the right, which is a neat way of probing the issue of nested communities. On the page, Rob has a number of interesting observations regarding visualization of the link communities and explains the layout above in further detail. I quote:

The good news is that the ABL method is powerful and flexible. The challenge is that the communities it reveals are of links, not nodes, and therefore not as obvious to portray and interpret. So far the literature method is to use a traditional force-based network diagram and color the lines between the dots, rather than color the dots. Not bad, but this has the limitations of force-directed network diagrams have always had: a big “wow factor” but of limited practical interpretive use because of the spaghetti of crossing lines. So here you’ll find outright experiments, and that means that some will be different!

In the upper circular graph the dots are the nodes and the polygons show community membership of those nodes (the colors match the table and dendrogram); line crossing is minimized by working around in cluster-joining order (same as the ROYGBIV color order). Communities are equally distributed around the circle with anchor points shown as black-centered dots; each node is placed as the weighted sum of its coordinates of each anchor to which it belongs, plus some random jitter to separate nodes with single community membership. The community ordering and coloring has an interesting result: the diagram gets simpler to see as the number of communities is increased, even far above the partition density “optimum”.

The method is fast because it’s completely deterministic and drawn in one pass, i.e. it’s not an iterative force-relaxation method.

Pervasive overlap and visualizations

While Rob’s visualization shows tremendous progress on a number of fronts (just compare it to our own – primitive – first stab at visualizing the network of characters in Les Miserables), I still think that node based visualizations of the link communities work best when we study ego-networks (a single person and her neighbors).

As we point out in the paper, we can visualize the ego-network precisely because the central node’s communities are largely non-overlapping. So in the example above, Dorothy is the Ego, placed in the center of the visualization, while the various non-overlapping story lines appear as communities surrounding her.

One of the consequences of pervasive overlap (when every node is a member of multiple communities), is that we can no longer display the communities as block structures in the network adjacency matrix. Roughly speaking, to form a block structure, we need a single block per node. Some overlap is possible within the framework of block modeling, but when we can have more communities than nodes, this approach breaks down.

A similar problem arises in visualization. My guess is that any strategy for visualizing pervasive overlap where nodes are the basis of the visualization will ultimately turn out to be problematic for a full network. One possible solution is to follow the example of CFinder and construct a visualization based on the network of communities but with the ability to zoom into each community. At the local level, Rob’s visualization would be perfect.

Comments/ideas are welcome. Note – this post can also be found at the Complexity and Social Networks Blog.

Published by

Sune Lehmann

I’m an Associate Professor at the Department of Applied Mathematics and Computer Science, at the Technical University of Denmark.

7 thoughts on “Visualizing Link Communities”

  1. It is impressive about the visualization of the networks, therefore I would like to ask whether it is also applicable for a biological information, like the involvement of certain protein in the biological pathway, as well as through its known interaction partner? It will be useful to know, whether this visualization method are available as software or online resources? do you use hypergraph theory and also category theory for the algorithm of networks visualization? It will be very useful for the biologist to be able to visualize a certain gene/protein of interest, because based on current available database it is very difficult to search or even visualize it from a messy and huge biological data information, therefore an overall view/map where biologist can see the complete networks of the particular protein or gene of interest would bring a great help or even reveal the unknown links between 2 communities. Thank you for your attention and I will appreciate if you could answer my questions.

      1. Thanks! You will need to do user-specified link layout for this particular problem. It can be a little obscure (this is release 1.0.0!), and not yet well documented. If you want to email me some sample data files, I can have a look.


Leave a Reply

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

You are commenting using your 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