2

私が行っているプロジェクトでは、NetworkX を使用して作成したグラフを、NetworkX adj_matrix() 関数を使用して隣接行列に分解します。ただし、私が遭遇した問題の 1 つは、行列の逆数を見つけようとすると、分解するすべてのグラフで次のエラーが発生することです。

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 が隣接行列をどのように生成するかは正確にはわかりませんが、それが逆になる理由はまったくありません。たとえば、完全なグラフ (すべてのノードが互いに接続されている) を考えてみましょう。そのアダセンシー行列は 1 でいっぱいで、行列の固有値は明らかに 0 です (もちろん、ノードの数が >= 2 になるとすぐに. ..)。または、N 個のノードとエッジのないグラフ、その隣接行列は 0 です...

何をしたいですか ？I - x A隣接行列の逆数を考慮する必要はありませんでしたが、x のある (小さい) 値の逆数を考えることがよくあります。その逆は

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

これは x のある値に対して可逆です (実際、すぐに |x| < max( |1/y| A の固有値の y の場合) と思います)...これは、パスの数を考慮するためですグラフですが、減衰を入れているので、集計可能です (Pagerank 誰ですか?)

于 2009-12-04T08:33:14.457 に答える
1

隣接行列が特異でないグラフを生成する方法を求めていますか? 生成したグラフに逆数を持たない隣接行列があるのは、networkx または numpy のせいではありません。

于 2009-12-04T07:02:37.243 に答える