Graph.get_adjacency () медленный, и выход странный

Рассмотрим объект графа G в pythonigraph 0.7. Если мне нужна матрица смежности A из G, я должен написать A=G.get_adjacency() , но есть две проблемы:

  1. Даже если G разрежен с 3000 узлами, A генерируется в течение длительного времени на моем коммерческом ноутбуке. Возможно ли, что создание матрицы смежности так дорого?
  2. Выход A является объектом Matrix, поэтому, если я хочу работать с модулем numpy на A, я должен сначала преобразовать его в список, а затем в numpy.matrix. Более того, если A разрежен, мне нужно третье преобразование в редкой scipy-матрице.

Есть ли в Igraph любой способ получить матрицу scipy.sparse разреженного графика в разумные сроки?

One Solution collect form web for “Graph.get_adjacency () медленный, и выход странный”

  1. Не имеет значения, является ли граф разреженным или нет, потому что igraph все равно будет создавать плотную матрицу, так что это O (n 2 ) операция. (Технически сама матрица создается в слое C, где инициализация матрицы ко всем нулям принимает O (n 2 ), а затем она заполняется единицами в O (m), где n – количество вершин, а m – количество ребер – но тогда матрица перенаправляется на уровень Python, где она преобразуется в объект Matrix, а слой Python не имеет представления о том, что матрица по существу разрежена, поэтому для ее преобразования требуется O (n 2 ), On мой ноутбук, создающий матрицу смежности для графика с 3000 узлами, составляет около 500 мс, и я думаю, что это, вероятно, нормально.

  2. Да, есть способ создать разреженную матрицу из графика графика, хотя это немного многословно:

     from scipy.sparse import coo_matrix from numpy import hstack, ones def graph_to_sparse_matrix(graph): xs, ys = map(array, zip(*graph.get_edgelist())) if not graph.is_directed(): xs, ys = hstack((xs, ys)).T, hstack((ys, xs)).T else: xs, ys = xs.T, ys.T return coo_matrix((ones(xs.shape), (xs, ys))) 

Эта версия преобразует один и тот же граф в разреженную матрицу SciPy в ~ 26 мс на моей машине.

  • Быстрый n-мерный разреженный массив в Python / Cython
  • Вычисление собственных значений очень больших разреженных матриц в python
  • Python - лучший язык программирования в мире.