Sorting rows and columns of adjacency matrix to reveal cliques

Question

I'm looking for a reordering technique to group connected components of an adjacency matrix together.

For example, I've made an illustration with two groups, blue and green. Initially the '1's entries are distributed across the rows and columns of the matrix. By reordering the rows and columns, all '1''s can be located in two contiguous sections of the matrix, revealing the blue and green components more clearly.

I can't remember what this reordering technique is called. I've searched for many combinations of adjacency matrix, clique, sorting, and reordering.

The closest hits I've found are

1. symrcm moves the elements closer to the diagonal, but does not make groups.

2. Is there a way to reorder the rows and columns of matrix to create a dense corner, in R? which focuses on removing completely empty rows and columns

Please either provide the common name for this technique so that I can google more effectively, or point me in the direction of a Matlab function.

Answer 1

I don't know whether there is a better alternative which should give you direct results, but here is one approach which may serve your purpose.

Your input:

>> A

A =

 0     1     1     0     1
 1     0     0     1     0
 0     1     1     0     1
 1     0     0     1     0
 0     1     1     0     1

Method 1

Taking first row and first column as Column-Mask(maskCol) and Row-Mask(maskRow) respectively.

Get the mask of which values contains ones in both first row, and first column

maskRow = A(:,1)==1;
maskCol = A(1,:)~=1;

Rearrange the Rows (according to the Row-mask)

out = [A(maskRow,:);A(~maskRow,:)];

Gives something like this:

out =

 1     0     0     1     0
 1     0     0     1     0
 0     1     1     0     1
 0     1     1     0     1
 0     1     1     0     1

Rearrange columns (according to the column-mask)

out = [out(:,maskCol),out(:,~maskCol)]

Gives the desired results:

out =

 1     1     0     0     0
 1     1     0     0     0
 0     0     1     1     1
 0     0     1     1     1
 0     0     1     1     1

---

Just a check whether the indices are where they are supposed to be or if you want the corresponding re-arranged indices ;)

Before Re-arranging:

idx = reshape(1:25,5,[])

idx =

 1     6    11    16    21
 2     7    12    17    22
 3     8    13    18    23
 4     9    14    19    24
 5    10    15    20    25

After re-arranging (same process we did before)

outidx = [idx(maskRow,:);idx(~maskRow,:)];
outidx = [outidx(:,maskCol),outidx(:,~maskCol)]

Output:

outidx =

 2    17     7    12    22
 4    19     9    14    24
 1    16     6    11    21
 3    18     8    13    23
 5    20    10    15    25

---

Method 2

For Generic case, if you don't know the matrix beforehand, here is the procedure to find the maskRow and maskCol

Logic used:

1. Take first row. Consider it as column mask (maskCol).

2. For 2nd row to last row, the following process are repeated.

3. Compare the current row with maskCol.

4. If any one value matches with the maskCol, then find the element wise logical OR and update it as new maskCol

5. Repeat this process till the last row.

6. Same process for finding maskRow while the column are used for iterations instead.

Code:

%// If you have a square matrix, you can combine both these loops into a single loop.
maskCol = A(1,:);
for ii = 2:size(A,1)
    if sum(A(ii,:) & maskCol)>0 
        maskCol = maskCol | A(ii,:);
    end
end

maskCol = ~maskCol;

maskRow = A(:,1);
for ii = 2:size(A,2)
    if sum(A(:,ii) & maskRow)>0 
        maskRow = maskRow | A(:,ii);
    end
end

Here is an example to try that:

%// Here I removed some 'ones' from first, last rows and columns.
%// Compare it with the original example.
A = [0     0     1     0     1
     0     0     0     1     0
     0     1     1     0     0
     1     0     0     1     0
     0     1     0     0     1];

Then, repeat the procedure you followed before:

out = [A(maskRow,:);A(~maskRow,:)];        %// same code used
out = [out(:,maskCol),out(:,~maskCol)];    %// same code used

Here is the result:

>> out

out =

 0     1     0     0     0
 1     1     0     0     0
 0     0     0     1     1
 0     0     1     1     0
 0     0     1     0     1

Note: This approach may work for most of the cases but still may fail for some rare cases.

Here, is an example:

%// this works well.
A = [0     0     1     0     1    0
     1     0     0     1     0    0
     0     1     0     0     0    1
     1     0     0     1     0    0
     0     0     1     0     1    0
     0     1     0     0     1    1];

%// This may not
%// Second col, last row changed to zero from one
A = [0     0     1     0     1    0
     1     0     0     1     0    0
     0     1     0     0     0    1
     1     0     0     1     0    0
     0     0     1     0     1    0
     0     0     0     0     1    1];

Why does it fail?

As we loop through each row (to find the column mask), for eg, when we move to 3rd row, none of the cols match the first row (current maskCol). So the only information carried by 3rd row (2nd element) is lost.

This may be the rare case because some other row might still contain the same information. See the first example. There also none of the elements of third row matches with 1st row but since the last row has the same information (1 at the 2nd element), it gave correct results. Only in rare cases, similar to this might happen. Still it is good to know this disadvantage.

Method 3

This one is Brute-force Alternative. Could be applied if you think the previous case might fail. Here, we use while loop to run the previous code (finding row and col mask) number of times with updated maskCol, so that it finds the correct mask.

Procedure:

 maskCol = A(1,:);
 count = 1;
 while(count<3)
     for ii = 2:size(A,1)
         if sum(A(ii,:) & maskCol)>0
             maskCol = maskCol | A(ii,:);
         end
     end
     count = count+1;
 end

Previous example is taken (where the previous method fails) and is run with and without while-loop

Without Brute force:

>> out

out =

 1     0     1     0     0     0
 1     0     1     0     0     0
 0     0     0     1     1     0
 0     1     0     0     0     1
 0     0     0     1     1     0
 0     0     0     0     1     1

With Brute-Forcing while loop:

>> out

out =

 1     1     0     0     0     0
 1     1     0     0     0     0
 0     0     0     1     1     0
 0     0     1     0     0     1
 0     0     0     1     1     0
 0     0     0     0     1     1

The number of iterations required to get the correct results may vary. But it is safe to have a good number.

Good Luck!