使用 MATLAB 查找图中邻居的邻居

Question

我有一个矩阵A，它代表邻里关系。

A=[1 2
   1 4
   2 6
   4 5
   6 7
   6 8]

的行A已排序，意味着[1 2]和[2 1]被视为相同的邻域关系，并且 的行A按字典顺序升序排序。

在我们的示例矩阵中，节点1是节点 的邻居2，4节点2是 的邻居6，节点4是 的邻居5，依此类推。我想计算一个B表示邻居（非）关系的邻居的矩阵。如果两个节点都有一些它们都是邻居的节点，则这两个节点彼此互不存在。这意味着1不是5(via 4) 和6(via 2) 等。

 B=[1 5
    1 6
    2 4
    2 7
    2 8
    7 8]

我怎样才能计算矩阵B？

Answer 1

我们将您的图表称为G。G您可以使用 的图幂 来计算 的邻居，该图具有相同的节点，但其中两个顶点在距离最大为时相邻。G^kk=2Gk

您可以阅读维基百科文章上的详细信息，但最重要的部分是：

如果A是图的邻接矩阵，修改为在其主对角线上具有非零条目，则 的非零条目给出图A^k的 th 次方的邻接矩阵。k

（对于我们的情况k=2，我们不需要对角线上的非零条目，因为我们需要距离恰好为二，而不是距离小于或等于二，这将对角线设置为非零条目。）

因此，您只需通过以下方式构建邻接矩阵A：

edges = A;
n = max(edges(:));
A = sparse(edges(:,1),edges(:,2),1,n,n) + ...
    sparse(edges(:,2),edges(:,1),1,n,n); % Make graph undirected via symmetry.

G^2然后，您将生成viaA*A或的邻接矩阵A^2，然后使用它find来获取边：

[I,J] = find(A^2); % Edges of A^2

然后，您可以B通过删除不需要的元素（例如原始连接或自连接）来构建

B = setdiff(sort([I,J],2), [edges; [(1:n).',(1:n).'], 'rows')