Matrizes Matrizes e inverso em Python

Question

Para um projeto que eu estou fazendo, eu decompor um gráfico que eu criei usando NetworkX em uma matriz de adjacência usando a função NetworkX adj_matrix (). No entanto, um dos problemas que se deparam é que cada gráfico único que eu decompor me dá o seguinte erro quando eu tento encontrar o inverso da matriz.

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

Eu tentei matrizes de adjacência de geração a partir de 5 gráficos diferentes e todos eles produziram o mesmo erro quando eu tentei encontrar o inverso da matriz de adjacência. A questão que eu coloco é se existe alguma maneira de ir de gráfico NetworkX a matriz. Qual é a minha melhor curso de ação a partir daqui? Sei que existem outras questões relativas a matriz inversa, mas o meu é um pouco limitado pelo fato de que eu preciso da matriz gráfico adjacência.

Answer 1

Adjacency matrices are not always invertible. There are papers on this subject; I'm not sure whether there is any simple characterization of the corresponding graphs. A pragmatic approach would be to catch the LinAlgError exception in your code (try… except…), and warn when the adjacency matrix is not invertible (and keep performing your calculations otherwise).

Answer 2

I don't know exactly how networkx produces the adjacency matrix, but there is absolutely no reason for it to be inversible. For example, consider the complete graph (all nodes are connected to every each other), its adacency matrix is full of ones, and the matrix has obviously 0 as an eigenvalue (as soon as the number of nodes is >= 2 of course...). Or the graph with N Nodes and no edges, its adjacency matrix is 0...

What do you want to do ? I never had to consider the inverse of the adjacency matrix, but very often the inverse of I - x A for some (small) value of x. Its inverse is

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

which is inversible for some value of x (in fact, as soon as |x| < max( |1/y| for y in eigenvalues of A) I think)... this is because you consider the number of paths in your graph, but putting some decay in it, so it is summable (Pagerank anyone ?)

Answer 3

are you asking for a method to generate graphs whose adjacency matrices are non-singular? it is no fault of networkx's or numpy's that the graphs you generated have adjacency matrices that do not have inverses.