views:

523

answers:

3

For a project that I am doing, I decompose a graph that I created using NetworkX into an adjacency matrix using the NetworkX adj_matrix() function. However, one of the problems that I have come across is that every single graph that I decompose gives me the following error when I try to find the inverse of the matrix.

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

I tried generating adjacency matrices from 5 different graphs and all of them produced the same error when I tried to find the inverse of the adjacency matrix. The question that I pose is whether there is any way to go from NetworkX graph to matrix. What is my best course of action from here? I realize there are other questions pertaining to matrix inverses, but mine is somewhat limited by the fact that I need the graph adjacency matrix.

+1  A: 

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.

Autoplectic
I'm using Networkx standard Graph() object and then I slowly begin adding nodes to it using add_edges() and add_node(). BTW, awesome avatar.
rohanbk
+3  A: 

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).

EOL
The inverse of the adjacency list is required for what I am doing. I'm trying to find a sum of path ensembles in a graph (Katz measure) which can be found by utilizing the adjacency matrix of a graph. The formula is below. Katz= ((I-xA)^-1)-I
rohanbk
Interesting. If there is an infinite number of paths between two points (which happens when you have loops in your graph), then I would guess that you cannot perform the inversion (the result is infinite). Maybe this is the problem that you are encountering? You could try your routine with a non-cyclic graph, for instance.
EOL
+2  A: 

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 ?)

LeMiz
Incidentally, the formula that you provide is actually very similar to what I'm trying to do. I'm trying to find a sum of path ensembles in a graph (Katz measure) which can be found by utilizing the adjacency matrix of a graph. The formula is below. Katz= ((I-xA)^-1)-I (where I is the inverse matrix and 'x' is a small constant).
rohanbk
As I said, if your x is sufficiently low, It (I-xA) is inversible. To ensure it, you can class the eigenvalues of A, and choose x accordingly. Note that is really not the same thing as trying to inverse A itself...
LeMiz