Переупорядочение симметричной матрицы смежности, содержащей +1 и -1 элементов для получения кликов

Question

У меня есть симметричная матрица смежности с нулевым значением по ее диагонали. теперь я ищу метод переупорядочения, чтобы показать сообщество, которое делит матрицу на два клика с значениями +1 и -1 соответственно. было бы полезно, если бы кто-то мог мне помочь в этом отношении.

, например: матрица (10,10)

0  1 -1  1  1 -1  1  1 -1 -1 
    1  0 -1  1  1 -1  1 -1 -1 -1 
-1 -1  0 -1 -1  1  1  1  1 -1 
    1  1 -1  0  1 -1  1 -1 -1 -1 
    1  1 -1  1  0 -1  1  1 -1 -1 
-1 -1  1 -1 -1  0 -1  1  1  1 
    1  1  1  1  1 -1  0  1  1  1 
    1 -1  1 -1  1  1  1  0 -1 -1 
-1 -1  1 -1 -1  1  1 -1  0  1 
-1 -1 -1 -1 -1  1  1 -1  1  0 

выход должен быть:

1  1  1  1  1 -1 -1 -1 -1 -1 
    1  1  1  1  1 -1 -1 -1 -1 -1 
    1  1  1  1  1  1 -1 -1 -1 -1 
    1  1  1  1  1 -1 -1 -1 -1 -1 
    1  1  1  1  1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1  1  1  1  1  1 
-1 -1 -1 -1 -1  1  1  1  1  1 
-1 -1 -1 -1 -1  1  1  1  1  1 
-1 -1 -1 -1 -1  1  1  1  1  1 
-1 -1 -1 -1 -1  1  1  1  1  1 

нулевые элементы можно рассматривать как 1

Answer 1

Из примера, я не знаю, как бороться с большинством случаев, поэтому я догадался.

a = round(3*rand(10) - 1.5); 
a(logical(eye(size(a)))) = 0; 
b = cliques(a); 

Это поддерживает требование симметрии и только должен освободиться от «крыльев» -1-х, когда есть один оставшийся после всех остальных фильтров (то есть, если число -1-х нечетно, то для поддержания симметрия элемент должен идти по диагонали).

function b = cliques(a) 
    a(a == 0) = 1; 
    n = sum(a(:) == -1); 

    s = floor(sqrt(n/2)); 

    b = ones(size(a)); 
    b(end - s + 1:end, 1:s) = -1; 
    b(1:s, end - s + 1:end) = -1; 

    n = n - 2*s^2; 

    bands = floor(n/4); 
    b(s+1, end - bands + 1:end) = -1; 
    b(end - bands + 1:end, s+1) = -1; 

    b(end - s, 1:bands) = -1; 
    b(1:bands, end - s) = -1; 

    n = n - 4*bands; 

    dots = floor(n/2); 
    if dots 
     b(end - s, s + 1) = -1; 
     b(s + 1, end - s) = -1; 
    end 

    n = n - 2*dots; 

    if n 
     b(1,1) = -1; 
    end 

    contourf(b, 'LevelList', [-1,1]); 
    set(gca,'Ydir','reverse') 

    sum(a(:)) == sum(b(:)) 
end