Matrices et matrices inverses en Python

Pour un projet que je suis en train de faire, je décomposerai un graphe que j'ai créé en utilisant NetworkX dans une matrice d'adjacence en utilisant la fonction network_ adj_matrix(). Cependant, un des problèmes que j'ai rencontré est que chaque graphique que je décomposais me donne l'erreur suivante quand j'essaie de trouver l'inverse de la matrice.Matrices et matrices inverses en Python

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

J'ai essayé de générer des matrices de contiguïté de 5 graphiques différents et tous les a produits la même erreur quand j'ai essayé de trouver l'inverse de la matrice de contiguïté. La question que je pose est de savoir s'il est possible de passer du graphe NetworkX à la matrice. Quel est mon meilleur plan d'action à partir d'ici? Je me rends compte qu'il y a d'autres questions relatives aux matrices inverses, mais la mienne est quelque peu limitée par le fait que j'ai besoin de la matrice d'adjacence du graphe.

Source

2009-12-04 GobiasKoffi

Les matrices d'adjacence sont not always invertible. Il y a papers sur ce sujet; Je ne suis pas sûr qu'il y ait une simple caractérisation des graphiques correspondants. Une approche pragmatique consisterait à attraper l'exception LinAlgError dans votre code (essayez ... sauf ...), et à avertir lorsque la matrice d'adjacence n'est pas inversible (et continuez à effectuer vos calculs dans le cas contraire).

Source

2009-12-04 08:25:41 EOL

L'inverse de la liste d'adjacence est nécessaire pour ce que je fais. J'essaie de trouver une somme d'ensembles de chemins dans un graphe (mesure de Katz) que l'on peut trouver en utilisant la matrice d'adjacence d'un graphe. La formule est ci-dessous. Katz = ((I-xA)^- 1) -I – GobiasKoffi

Intéressant. S'il y a un nombre infini de chemins entre deux points (ce qui arrive quand vous avez des boucles dans votre graphe), alors je suppose que vous ne pouvez pas effectuer l'inversion (le résultat est infini). Peut-être que c'est le problème que vous rencontrez? Vous pourriez essayer votre routine avec un graphique non-cyclique, par exemple. – EOL

demandez-vous une méthode pour générer des graphes dont les matrices d'adjacence sont non-singulières? ce n'est pas la faute de networkx ou numpy que les graphiques que vous avez générés ont des matrices d'adjacence qui n'ont pas d'inverses.

Source

2009-12-04 07:02:37 Autoplectic

J'utilise l'objet Graph() standard de Networkx et je commence lentement à y ajouter des nœuds en utilisant add_edges() et add_node(). BTW, avatar génial. – GobiasKoffi

Je ne sais pas exactement comment networkx produit la matrice d'adjacence, mais il n'y a absolument aucune raison pour qu'elle soit inversible. Par exemple, considérons le graphe complet (tous les nœuds sont connectés les uns aux autres), sa matrice d'adacence est pleine de uns, et la matrice a évidemment 0 comme valeur propre (dès que le nombre de nœuds est> = 2 bien sûr. ..). Ou le graphe avec N Nœuds et sans bords, sa matrice d'adjacence est 0 ...

Que voulez-vous faire? Je n'ai jamais eu à considérer l'inverse de la matrice d'adjacence, mais très souvent l'inverse de I - x A pour une (petite) valeur de x. Son inverse est

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

qui est inversible pour une valeur de x (en fait, dès que | x | < max (| 1/y | pour y en valeurs propres de A) je pense) ... ce est-ce parce que vous considérez le nombre de chemins dans votre graphique, mais y mettez de la désintégration, donc c'est sommable (Pagerank n'importe qui?)

Source

2009-12-04 08:33:14 LeMiz

Incidemment, la formule que vous fournissez est en fait très similaire à ce que j'essaie de faire. J'essaie de trouver une somme d'ensembles de chemins dans un graphe (mesure de Katz) que l'on peut trouver en utilisant la matrice d'adjacence d'un graphe. La formule est ci-dessous. Katz = ((I-xA)^- 1) -I (où I est la matrice inverse et 'x' est une petite constante). – GobiasKoffi

Comme je l'ai dit, si votre x est suffisamment bas, It (I-xA) est inversible. Pour l'assurer, vous pouvez classer les valeurs propres de A et choisir x en conséquence. Notez que ce n'est vraiment pas la même chose que d'essayer d'inverser A lui-même ... – LeMiz

Matrices et matrices inverses en Python

Répondre

Questions connexes