matlab - 使用 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 代表邻居(NON)关系的邻居。如果两个节点都有某个节点，它们都是彼此的邻居，则它们是彼此的 NON。这意味着 1 是 5(通过 4)和 6(通过 2), 等等

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

如何计算矩阵 B？

Answer 1

我们称您的图为 G。您可以使用 graph power 计算 G 的邻居的邻居G^k for k=2，这是具有相同节点的图，但其中两个顶点相邻时它们在G中的距离> 最多为 k。

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

If A is an adjacency matrix for the graph, modified to have nonzero entries on its main diagonal, then the nonzero entries of A^k give the adjacency matrix of the kth power of the graph.

(对于我们的情况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.

然后，您将通过 A*A 或 A^2 生成 G^2 的邻接矩阵，然后使用 找到以获得边缘:

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

然后您可以通过删除其中不需要的元素(例如原始连接或自连接)来构建 B

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