如何将边列表转换为邻接矩阵

Question

我有这个代码

function adj=edgeL2adjj(e)
    Av = [e; fliplr(e)];
    nodes = unique(Av(:, 1:2)); % get all nodes, sorted
    adj = zeros(numel(nodes));   % initialize adjacency matrix
    % across all edges
    for i=1:size(Av,1)
        adj(nodes==Av(i,1),(nodes==Av(i,2))) = 1;
    end
end

将边列表转换为邻接矩阵，但如果我输入 u=[8 5;1 4;3 5;6 7] 然后我将 u 分成两组 [8 5;1 4]、[3 5,6 7] 并将之前的代码应用到 [3 5;6 7] 我将得到一个 7 x 7 矩阵。
但我想要一个 8 x 8 矩阵到任何输入。

Answer 1

你有一个 7x7 矩阵，因为 numel(nodes)=7。事实上，节点 #2 不存在于 u 中。我建议您为该函数提供第二个输入，即网络中的最大节点数（在本例中为 8），并使用此类输入参数而不是 numel(nodes) 预分配邻接矩阵。或者，您可以通过输入不是 numel(nodes) 而是输入 u 中的最大值来预分配 zeros() 方阵。第一个选项将使您的代码更健壮，第二个选项将使您的代码健壮，只要第 8 个节点在输入中 u.

此外，不需要 fliplr()：如果您的图形是无向的（即，邻接矩阵是对称的），您可以在 for 循环中依赖这种结构，而无需在 Av.

这样的函数确实可以简化为：

function adj=edgeL2adjj(e)

adj=zeros(max(max(e)));   % initialize adjacency matrix

% across all edges
for i=1:size(e,1)
    adj(e(i,1),e(i,2))=1;
    adj(e(i,2),e(i,1))=1;
end
end

如果输入 e 是您的矩阵：

e= [8 5;1 4;3 5;6 7];

这样的代码returns

adj =

     0     0     0     1     0     0     0     0
     0     0     0     0     0     0     0     0
     0     0     0     0     1     0     0     0
     1     0     0     0     0     0     0     0
     0     0     1     0     0     0     0     1
     0     0     0     0     0     0     1     0
     0     0     0     0     0     1     0     0
     0     0     0     0     1     0     0     0

如您所见，您只需利用输入 e。最大值为 8，因此您构建了一个 8x8 方形矩阵。同样在 for 循环内，通过交换 e 中的列索引 1 和 2，您会自动处理邻接矩阵的对称结构。最后，此代码会在缺少节点的情况下自动对您进行排序：实际上，如您所见，adj 中的第二行和第二列全为零，因为边缘列表中不存在节点 #2 e.

注意：我不建议拆分您的输入边列表。通过这种方式，您将丢失有关您网络的所有全局信息。事实上，你将有（比方说）两个 "sub-networks" ，你稍后必须连接它们（就邻接矩阵而言）。也就是说，如果您将 e 拆分为两个子矩阵，您将拥有两个邻接矩阵。考虑到我现在的答案中的代码，第一个矩阵将是 8x8，而第二个矩阵将是 7x7，因为 max(max([3 5;6 7]))=7.

Answer 2

如果可以的话，我想为您的问题提供一个完全不同的解决方案，它避免遍历所有边（在 MATLAB 中避免循环总是一个好主意！）。

因为你有所有的行和列索引，你的边缘列表基本上已经指定了一个（尽管是稀疏的）矩阵。您可以像这样简单地分配矩阵：

function adj = edgeL2adjj(e)

    r = e(:,1);
    c = e(:,2);
    vals = ones(size(r));

    % maximum node index determines matrix dimensions
    n_nodes = max(e(:));

    % create sparse matrix
    adj = sparse(r, c, vals, n_nodes, n_nodes);

    % if really necessary, you can just convert it to a full matrix
    adj = full(adj);

end

如果您知道您总是希望图形具有相同的维度，即使您只使用部分边作为函数的输入，您也可以只传递 n_nodes 作为输入而不是确定来自 e:

function adj = edgeL2adjj(e, n_nodes)

如何将边列表转换为邻接矩阵

how to convert edge list to adjacency matrix

matlab

adjacency-matrix