algorithm - Sorting rows and columns of adjacency matrix to reveal cliques -

i'm looking reordering technique group connected components of adjacency matrix together.

for example, i've made illustration 2 groups, blue , green. '1's entries distributed across rows , columns of matrix. reordering rows , columns, '1''s can located in 2 contiguous sections of matrix, revealing blue , green components more clearly.

i can't remember reordering technique called. i've searched many combinations of adjacency matrix, clique, sorting, , reordering.

the closest hits i've found are

1. symrcm moves elements closer diagonal, not make groups.

2. is there way reorder rows , columns of matrix create dense corner, in r? focuses on removing empty rows , columns

please either provide common name technique can google more effectively, or point me in direction of matlab function.

i don't know whether there better alternative should give direct results, here 1 approach may serve purpose.

your input:

>>  =   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 , first column column-mask(maskcol) , row-mask(maskrow) respectively.

get mask of values contains ones in both first row, , first column

maskrow = a(:,1)==1; maskcol = a(1,:)~=1; 

rearrange rows (according row-mask)

out = [a(maskrow,:);a(~maskrow,:)]; 

gives 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 column-mask)

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

gives 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 check whether indices supposed or if want 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 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 don't know matrix beforehand, here procedure find maskrow , maskcol

logic used:

1. take first row. consider column mask (maskcol).

2. for 2nd row last row, following process repeated.

3. compare current row maskcol.

4. if 1 value matches maskcol, find element wise logical or , update new maskcol

5. repeat process till last row.

6. same process finding maskrow while column used iterations instead.

code:

%// if have square matrix, can combine both these loops single loop. maskcol = a(1,:); ii = 2:size(a,1)     if sum(a(ii,:) & maskcol)>0          maskcol = maskcol | a(ii,:);     end end  maskcol = ~maskcol;  maskrow = a(:,1); ii = 2:size(a,2)     if sum(a(:,ii) & maskrow)>0          maskrow = maskrow | a(:,ii);     end end 

here example try that:

%// here removed 'ones' first, last rows , columns. %// compare original example. = [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 procedure followed before:

out = [a(maskrow,:);a(~maskrow,:)];        %// same code used out = [out(:,maskcol),out(:,~maskcol)];    %// same code used 

here 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: approach may work of cases still may fail rare cases.

here, example:

%// works well. = [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];  %// may not %// second col, last row changed 0 1 = [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 fail?

as loop through each row (to find column mask), eg, when move 3rd row, none of cols match first row (current maskcol). information carried 3rd row (2nd element) lost.

this may rare case because other row might still contain same information. see first example. there none of elements of third row matches 1st row since last row has same information (1 @ 2nd element), gave correct results. in rare cases, similar might happen. still know disadvantage.

method 3

this 1 brute-force alternative. applied if think previous case might fail. here, use while loop run previous code (finding row , col mask) number of times updated maskcol, finds correct mask.

procedure:

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

previous example taken (where previous method fails) , run , 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 correct results may vary. safe have number.

good luck!