Эффективные способы представления (возможно большой) граф с неизвестной структурой, используя NumPy?

Question

Мои настройки в основном следующие:

• У меня есть набор узлов (представленных в виде целых чисел 0, ...). Возможно, несколько миллионов из них.

• Эти узлы связаны в неориентированном графе без весов.

• Структура графа неизвестна, возможны как разреженные, так и плотные графы, хотя плотныеГрафики с несколькими миллионами узлов маловероятны.

• Я хотел бы максимально использовать numpy для обеспечения совместимости с другими частями проекта. Я надеюсь, что смогу реализовать все операции на графе как numy ufuncs.

Проблема в том, что при работе с графиком поиск ребер, создание и удаление ребер будут происходить часто. Моя идея состоит в том, чтобы использовать отсортированный список смежности, однако я не совсем уверен, как эффективно реализовать его, используя массивы numpy.

Есть ли эффективный способ реализовать его, используя только массивы numpy, или мне придется использовать некоторые из них? вместо другой структуры данных?

Answer 1

Использование numpy.ndarray представляется невозможным для ваших спецификаций, поскольку вы описываете более 1 000 000 узлов, т. Е. Соответствующая матрица будет иметь 1e12 + записей.

Вместо этого вы можете использовать один из scipy.sparseматрицы , которые распределяют данные по мере необходимости. В обзоре они описывают плюсы и минусы различных реализаций. Для вашего приложения, в котором, как представляется, часто создаются и удаляются ребра, реализация словаря ключей представляется хорошим выбором:

Это эффективная структура для постепенного построения разреженных матриц.

Матрица разреженного списка может быть другим вариантом, но производительность может быть хуже, если вставка происходит случайным образом.

Операции с этими матрицами в основном аналогичныNumpy, но использование numpy функций не рекомендуется, как объяснено в документации:

Несмотря на их сходство с массивами NumPy, настоятельно рекомендуется использовать функции NumPy непосредственно в этих матрицах, поскольку NumPyможет неправильно преобразовать их для вычислений, что приведет к неожиданным (и неправильным) результатам.

Поэтому вам нужно проверить библиотеку scipy на эквивалентную функцию. В модуле scipy.sparse.csgraph доступно множество доступных для выполнения операций над графами.

Кстати, пакет networkx также является популярным выбором. для работы с графиками.