Community-based sorting of Table/Matrix data (Visual Role Mining)

Question

I'm looking for a way to sort a two dimensional binary matrix so that we can visually identify "communities" in the data. My data-set is based on group membership (i.e a list of people and the groups to which they belong). For example:

   G1 G2 G3 G4
P1 1     1  
P2 1     1  
P3    1     1
P4    1     1

I'm looking for a sorting algorithm that will give me this:

   G1 G3 G2 G4
P1 1  1     
P2 1  1    
P3       1   1
P4       1   1

Another example of "sorted" data can be found here: http://mbostock.github.com/protovis/ex/matrix.html In this example, the creators reference a "community-detection algorithm" used for sorting. My data is different since there will be no memberships between dimensions (i.e. the first dimension (persons) are members of the second dimension (groups).

I've found a paper that discusses this in great detail: http://ricerca.mat.uniroma3.it/users/colanton/docs/visual.pdf (warning: PDF)

So in summary I'm taking membership data, trying to find "communities" within the data, and representing that visually.

I've found similar discussions that may be of some help here: Sorting a binary 2D matrix? Are there implementations of algorithms for community detection in graphs?

Answer 1

The best solution I've seen so far is here: http://matthewlincoln.net/2014/12/20/adjacency-matrix-plots-with-r-and-ggplot2.html

To summarize the approach:

One good alternative is to visualize an adjacency matrix encoding the network relationship data, where, for example, cell AB describes an edge connecting node A to node B. Mike Bostock has implemented this in D3, using Jacques Bretin’s Les Misérables co-occurrence network dataset. It is also fairly easy to generate an adjacency matrix visualization using ggplot2, but it does require that you bite the bullet and finally figure out how to work with ordered factors.

It's able to take a matrix plot that looks like this:

and sorts it to this: