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

Question

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

Answer 1

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

Answer 2

Я не знаю точно, как 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) я думаю)...это потому, что вы учитываете количество путей в вашем графе, но добавляете в него некоторое затухание, чтобы его можно было суммировать (кто-нибудь имеет рейтинг страниц?)

Answer 3

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