2

对于我正在做的一个项目，我使用 NetworkX adj_matrix() 函数将使用 NetworkX 创建的图分解为邻接矩阵。但是，我遇到的一个问题是，当我尝试找到矩阵的逆时，我分解的每个图都会给我以下错误。

str: Traceback (most recent call last):
  File "C:\eclipse\plugins\org.python.pydev.debug_1.4.7.2843\pysrc\pydevd_resolver.py", line 179, in _getPyDictionary
    attr = getattr(var, n)
  File "C:\Python26\lib\site-packages\numpy\core\defmatrix.py", line 519, in getI
    return asmatrix(func(self))
  File "C:\Python26\lib\site-packages\numpy\linalg\linalg.py", line 355, in inv
    return wrap(solve(a, identity(a.shape[0], dtype=a.dtype)))
  File "C:\Python26\lib\site-packages\numpy\linalg\linalg.py", line 254, in solve
    raise LinAlgError, 'Singular matrix'
LinAlgError: Singular matrix

我尝试从 5 个不同的图生成邻接矩阵，当我试图找到邻接矩阵的逆时，它们都产生了相同的错误。我提出的问题是是否有任何方法可以从 NetworkX 图到矩阵。从这里我最好的行动方案是什么？我意识到还有其他关于矩阵逆的问题，但我的问题是我需要图邻接矩阵这一事实。

4

3 回答 3

4

邻接矩阵并不总是可逆的。有关于这个主题的论文；我不确定相应的图表是否有任何简单的特征。一种实用的方法是在您的代码中捕获 LinAlgError 异常（尝试...除...），并在邻接矩阵不可逆时发出警告（否则继续执行您的计算）。

于 2009-12-04T08:25:41.890 回答
2

我不知道 networkx 是如何产生邻接矩阵的，但是绝对没有理由让它是可逆的。例如，考虑完整的图（所有节点相互连接），它的 adacency 矩阵全是 1，并且矩阵显然有 0 作为特征值（当然，只要节点数 >= 2。 ..)。或者有N个节点且没有边的图，它的邻接矩阵是0...

你想让我做什么 ？我从来不必考虑邻接矩阵的逆矩阵，但通常I - x A是 x 的某个（小）值的逆矩阵。它的倒数是

(I - x A) ^(-1) = I + xA + x^2 A2 + ...

这对于 x 的某些值是可逆的（事实上，我认为只要 |x| < max( |1/y| for y in eigenvalues of A) 我认为）...这是因为您考虑了路径的数量图表，但在其中添加了一些衰减，因此它是可总结的（Pagerank 任何人？）

于 2009-12-04T08:33:14.457 回答
1

您是否要求一种生成邻接矩阵非奇异图的方法？您生成的图具有没有逆矩阵的邻接矩阵，这不是 networkx 或 numpy 的错。

于 2009-12-04T07:02:37.243 回答