Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm dealing with tables that show connectivity within a network. Can anyone point me toward a technique for ordering the rows and columns so that nodes that are connected tend to be close to each other in the table?

For example, if I had a network like this (connections are directional), the structure isn't immediately obvious; it just looks random.

  1 2 3 4 5
1     x   x
2   x   
3     x  x
4   x  x 
5        x 

But if you re-order the columns and rows this way, the structure is clear; you can see some organisation in the network.

  2 4 5 3 1
2 x    
4 x x   
5   x   
3     x x 
1     x x 

Of course, I'm dealing with larger tables, with ~1024 nodes. I could just code up something that tries to find the arrangement with the minimal average distance between connected nodes by some general-purpose method like gradient descent. But perhaps there's a technique that's particularly suited to this type of problem?

share|improve this question
1  
What all have you tried? I can think of some simple techniques like choosing the first entry such that it has the maximum number of neighbors and then proceed so on. However, I am not sure if it will give you the optimal bandwidth. –  user17762 Nov 14 '10 at 2:43
2  
Two thoughts: (1) This looks a lot like a graph layout problem restricted to one dimension. (2) If your network is acyclic, like your example, you can try topological sorting on the nodes. It'll probably look less random, but it may not find clusters if they exist in the network. –  Rahul Nov 14 '10 at 2:46
2  
@Sivaram: Probably not, because bandwidth minimization is NP-complete. –  Rahul Nov 14 '10 at 2:49
    
@ Rahul: Thought so. I was looking up if this was NP-complete. Thanks! –  user17762 Nov 14 '10 at 2:54
1  
@mhwombat: We know what you meant. Bandwidth is a term in graph theory that measures how close to the diagonal you can pack the connectivity in an adjacency matrix (i.e. your tables) by rearranging the ordering of nodes. This is definitely related to what you want. –  Rahul Nov 14 '10 at 5:35

1 Answer 1

up vote 1 down vote accepted

Rahul's link to the Wikipedia article on topological sorting led me to tsort, which is a Unix command to do topological sorting. The networks I'm dealing with might have some cycles, but it seems that tsort can deal with cycles gracefully, and report the cycles to stderr. It looks like that will do the job I need. Thank you, Rahul!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.