6

（使用MATLAB）我有一个大的坐标矩阵和一个大的稀疏邻接矩阵，它们的坐标相互连接。我之前在 SO 上问过，如何在这个 SO question中有效地计算这些距离，但我现在遇到了内存问题，这是一个更严重的问题。

我使用这个 MATLAB 函数来计算距离矩阵Dists = pdist2(fruchterman_graph(:,:),fruchterman_graph(:,:),'euclidean');，但它在大型网络上无论是速度还是内存都失败了。

这是仅在小图（不是数十万）上运行的代码：

coordinate = kamada_graph;
    [n, d] = size(kamada_graph);
    assert(d == 2);
    resi = sparse(adj*  spdiags((1:n)',0,n,n));
    resj = sparse(spdiags((1:n)',0,n,n) * adj);
    res = sparse(n,n);
    f = find(adj);  
    res(f) = sqrt((coordinate(resi(f), 1) - coordinate(resj(f), 1)) .^ 2 +...
                          (coordinate(resi(f), 2) - coordinate(resj(f), 2)) .^ 2);

这在大图上创建

？？？错误使用 ==> 查找矩阵太大而无法返回线性索引。
用于[i,j] = find(S)稀疏矩阵。
==> modulesize_graphs 中的错误在 49 [f] = find(adj)；

我改变了被称为的行：

[i,j] = find(ajd);    
res(i,j) = sqrt((coordinate(resi(i,j), 1) - coordinate(resj(i,j), 1)) .^ 2 +...
    (coordinate(resi(i,j), 2) - coordinate(resj(i,j), 2)) .^ 2);

现在在小型网络（约500个顶点）上出现错误：

？？？内存不足。
键入 HELP MEMORY 作为您的选项。
==> modulesize_graphs 中的错误为 50
res(i,j) = sqrt((coordinate(resi(i,j), 1) - coordinate(resj(i,j), 1)) .^ 2 +...

无论如何，有没有使用邻接矩阵和坐标矩阵计算距离矩阵(N,2)，值x，y而不会陷入内存问题并且可能也不会太慢？

Adj所需的输出是距离矩阵，即根据邻接矩阵连接的所有点之间的距离。

4

1 回答 1

3

要使用最少的内存计算逐点距离，您始终可以逐个元素地遍历邻接矩阵：

%# assuming a square and symmetric adjacency matrix
nCoords = size(adjMat,1);

%# there are at most (n^2-n) distances 
%# if this runs out of memory already, there 
%# is a way to only store existing distances to save 
%# even more memory
distances = NaN((nCoords^2-nCoords)/2,1);

ct = 0;
for row = 1:nCoords
   for col = 1:row-1
     ct = ct+1;
     if adjacencyMatrix(row,col)
        distances(ct) = sum( (coordinate(row,:)-coordinate(col,:)).^2 );
     end
   end
end

distances = sqrt(distances);

使用稀疏方法，您可能想尝试以下方法（我认为您不需要resiand resj，除非我完全误解了您的问题）。

[row,col]=find(adjacencyMatrix);

distances = sqrt(sum( (coordinate(row,:) - coordinate(col,:)).^2 ,2));

sparseDistanceMatrix = sparse(row,col,distances);
于 2013-04-04T15:28:40.783 回答