使用具有稀疏和密集输入的 Scipy 最小生成树时结果不一致

Question

我将图的邻接矩阵存储为稀疏 scipy scr 矩阵。当我调用 scipy.sparse.csgraph.minimum_spanning_tree 函数时，我生成的稀疏数组的非零值太少（小于 V-1）。 使用较小的数据集进行一些测试（仅用于测试），我注意到当我将稀疏输入矩阵转换为密集矩阵时，该函数会计算一棵树。

这是我重现行为的代码和 我的输入稀疏矩阵 :

import scipy as sp
from scipy.sparse.csgraph import  minimum_spanning_tree
from scipy.sparse import csr_matrix
sparse_matrix = sp.sparse.load_npz('sparse_matrix.npz')

MST = minimum_spanning_tree(sparse_matrix)
print(f"weight of MST: {MST.data.sum()}")

print(f'non-zero edges {MST.size}')

dense_matrix = sparse_matrix.todense()

MST2 = minimum_spanning_tree(dense_matrix)

print(f"weight of MST2: {MST2.data.sum()}")

print(f'non-zero edges {MST2.size}')

sparse_from_dense = csr_matrix(dense_matrix)
MST3 = minimum_spanning_tree(sparse_from_dense)

print(f"weight of MST3: {MST3.data.sum()}")

print(f'non-zero edges {MST3.size}')

输出为：

weight of MST: 1399.3271604776382 
non-zero edges 459 
weight of MST2: 1653.5667477846146 
non-zero edges 698 
weight of MST3: 1653.5667477846146 
non-zero edges 698

有谁知道发生了什么事以及如何解决它？由于预期的顶点数确实是 698，我相信密集输出是正确的。

我尝试寻找其他方法来稀疏地表示矩阵并根据稀疏输入计算 MST，但我没有找到任何其他替代方法。

Answer 1

让我们首先查看此函数的文档，并尝试确定它处理稠密矩阵与稀疏矩阵的不同方式。

在注释部分，它这样说：

该例程使用无向图作为输入和输出。也就是说，如果 graph[i, j] 和 graph[j, i] 都为零，则节点 i 和 j 没有连接它们的边。如果其中一个非零，则两者通过两者中的最小非零值连接。

当用户输入密集矩阵时，此例程会失去精度。小元素< 1E-8 of the dense matrix are rounded to zero. All users should input sparse matrices if possible to avoid it.

一种可能性是这个稀疏矩阵包含小于1E-8的数据值。让我们检查一下：

>>> sparse_matrix = sp.sparse.load_npz('sparse_matrix.npz')
>>> print(sparse_matrix.data[sparse_matrix.data < 1e-8])
[0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]

确实如此 - 事实上它包含一堆零。在稀疏矩阵中，隐式零点和显式零点之间存在差异。隐式零是任何未出现的矩阵元素。显式零是存在且设置为零的矩阵元素。

对于 SciPy 稀疏矩阵中的大多数用途，这两件事是等效的。对于

minimum_spanning_tree()

，显式零点和隐式零点之间存在差异。

• 隐式零表示两个节点之间没有边。
• 显式零表示两个节点之间具有权重为零的边。

这为我们提供了解决问题的方法：使用 eliminate_zeros() 将显式零更改为隐式零。

import scipy as sp
from scipy.sparse.csgraph import  minimum_spanning_tree
sparse_matrix = sp.sparse.load_npz('sparse_matrix.npz')

sparse_matrix.eliminate_zeros()

MST = minimum_spanning_tree(sparse_matrix)
print(f"weight of MST: {MST.data.sum()}")
print(f'non-zero edges {MST.size}')

这给出了您预期的答案，无需先转换为密集。