Матрицы и обратные матрицы в Python

Для проекта, который я делаю, я разлагаю график, созданный с помощью NetworkX, в матрицу смежности, используя функцию NetworkX adj_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

Я попытался сгенерировать матрицы смежности из 5 разных графиков, и все они выдали одну и ту же ошибку, когда я попытался найти обратную матрицу смежности. Вопрос, который я задаю, заключается в том, есть ли способ перейти от графа NetworkX к матрице. Каков мой лучший план действий отсюда? Я понимаю, что есть и другие вопросы, относящиеся к обратным матрицам, но мой несколько ограничен тем фактом, что мне нужна матрица смежности графа.


python matrix networkx matrix-inverse
person GobiasKoffi    schedule 04.12.2009    source источник

Ответы (3)


arrow_upward
4
arrow_downward

Матрицы смежности не всегда обратимы. На эту тему есть статьи; Я не уверен, существует ли какая-либо простая характеристика соответствующих графиков. Прагматическим подходом было бы перехватывать исключение LinAlgError в вашем коде (попробуйте… кроме…) и предупреждать, когда матрица смежности необратима (и продолжать выполнять вычисления в противном случае).

person Eric O Lebigot    schedule 04.12.2009
comment
Для того, что я делаю, требуется обратный список смежности. Я пытаюсь найти сумму ансамблей путей в графе (мера Каца), которую можно найти, используя матрицу смежности графа. Формула ниже. Кац= ((I-xA)^-1)-I - person GobiasKoffi; 04.12.2009
comment
Интересно. Если существует бесконечное количество путей между двумя точками (что происходит, когда у вас есть петли в вашем графе), то я предполагаю, что вы не можете выполнить инверсию (результат бесконечен). Может быть, это проблема, с которой вы столкнулись? Например, вы можете попробовать свою процедуру с нециклическим графиком. - person Eric O Lebigot; 05.12.2009

arrow_upward
2
arrow_downward

Я точно не знаю, как networkx создает матрицу смежности, но нет абсолютно никаких причин для того, чтобы она была обратимой. Например, рассмотрим полный граф (все узлы связаны друг с другом), его матрица быстродействия заполнена единицами, а матрица имеет очевидное 0 в качестве собственного значения (если количество узлов >= 2, конечно. ..). Или граф с N узлами и без ребер, его матрица смежности равна 0...

Что ты хочешь делать ? Мне никогда не приходилось рассматривать обратную матрицу смежности, но очень часто обратную I - x A для некоторого (небольшого) значения x. Его инверсия

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

который является обратимым для некоторого значения x (на самом деле, как только |x| ‹ max (я думаю, |1/y| для y в собственных значениях A))... это потому, что вы учитываете количество путей в вашем график, но в него добавлено некоторое затухание, чтобы его можно было суммировать (Pagerank кто-нибудь?)

person LeMiz    schedule 04.12.2009
comment
Кстати, формула, которую вы предоставляете, на самом деле очень похожа на то, что я пытаюсь сделать. Я пытаюсь найти сумму ансамблей путей в графе (мера Каца), которую можно найти, используя матрицу смежности графа. Формула ниже. Katz= ((I-xA)^-1)-I (где I — обратная матрица, а «x» — малая константа). - person GobiasKoffi; 04.12.2009
comment
Как я уже сказал, если ваш x достаточно мал, оно (I-xA) обратимо. Чтобы гарантировать это, вы можете классифицировать собственные значения A и выбрать x соответственно. Обратите внимание, что на самом деле это не то же самое, что пытаться инвертировать сам A... - person LeMiz; 05.12.2009

arrow_upward
1
arrow_downward

вы просите метод для создания графов, матрицы смежности которых не являются сингулярными? нет вины networkx или numpy в том, что сгенерированные вами графики имеют матрицы смежности, которые не имеют инверсий.

person Autoplectic    schedule 04.12.2009
comment
Я использую стандартный объект Networkx Graph(), а затем медленно начинаю добавлять к нему узлы, используя add_edges() и add_node(). Кстати, крутая аватарка. - person GobiasKoffi; 04.12.2009