对包含 +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 的 "wings" 当在所有其他过滤器之后还剩下一个时（即如果 [=12= 的数量] 是奇数然后要保持对称，元素必须在对角线上）。

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

对包含 +1 和 -1 元素的对称邻接矩阵重新排序以获得团

reordering the symmetric adjacency matrix including +1 and -1 elements to get cliques

matlab

clique-problem

adjacency-matrix