Блог

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

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

В недавней презентации (слайды доступны на github здесь) утверждалось, что:

В отличие от многих других инструментов, NX предназначен для обработки данных в масштабе, соответствующем современным задачам…Большинство основных алгоритмов в NX полагаются на чрезвычайно быстрый устаревший код.

В презентации также говорится, что базовые алгоритмы NetworkX реализованы на C / Fortran.

Однако, глядя на исходный код, кажется, что NetworkX в основном написан на python. Я не слишком знаком с исходным кодом, но мне известно о паре примеров, когда NetworkX использует numpy для выполнения тяжелой работы (которая, в свою очередь, использует C / Fortran для выполнения линейной алгебры). Например, файл networkx/networkx/algorithms/centrality/eigenvector.py использует numpy для вычисления собственных векторов.

Кто-нибудь знает, действительно ли эта стратегия вызова оптимизированной библиотеки, такой как numpy, распространена во всем NetworkX, или это делают всего несколько алгоритмов? Также кто-нибудь может описать другие проблемы масштабируемости, связанные с NetworkX?

Ответ ведущего программиста NetworkX Я задал этот вопрос в списке рассылки NetworkX, и Арик Хагберг ответил:

Структуры данных, используемые в NetworkX, подходят для масштабирования больших задач (например, структура данных представляет собой список смежности). Алгоритмы имеют различные свойства масштабирования, но некоторые из тех, которые вы упомянули, можно использовать (например, PageRank, подключенные компоненты, линейная сложность по количеству ребер).

На данный момент NetworkX — это чистый код на Python. Структура смежности кодируется словарями Python, что обеспечивает большую гибкость за счет памяти и скорости вычислений. Большие графики будут занимать много памяти, и вы в конечном итоге исчерпаете ее.

NetworkX использует NumPy и SciPy для алгоритмов, которые в основном основаны на линейной алгебре. В этом случае граф представляется (копируется) в виде матрицы смежности с использованием либо NumPy-матриц, либо SciPy-разреженных матриц. Эти алгоритмы могут извлечь выгоду из устаревшего кода на C и FORTRAN, который используется в NumPy и SciPY.

Это старый вопрос, но я думаю, стоит упомянуть, что graph-tool обладает очень похожей функциональностью на NetworkX, но он реализован на C с помощью шаблонов (с использованием библиотеки Boost Graph) и, следовательно, намного быстрее (до двух порядков) и использует гораздо меньше памяти.

Отказ от ответственности: Я автор graph-tool.

Вашей большой проблемой будет память. Python просто не может обрабатывать десятки миллионов объектов, не перепрыгивая через обручи в реализации вашего класса. Нагрузка на память многих объектов слишком высока, вы набираете 2 ГБ, и 32-битный код не будет работать. Есть способы обойти это — с помощью слотов, массивов или NumPy. Все должно быть в порядке, потому что networkx был написан для повышения производительности, но если есть несколько вещей, которые не работают, я проверю использование вашей памяти.

Что касается масштабирования, алгоритмы — это, по сути, единственное, что имеет значение для графиков. Графовые алгоритмы, как правило, имеют действительно уродливое масштабирование, если они выполнены неправильно, и они с такой же вероятностью будут выполнены правильно в Python, как и в любом другом языке.

Тот факт, что NetworkX в основном написан на python, не означает, что он не масштабируется и не претендует на совершенство. Всегда есть компромисс. Если вы вложите больше денег в свои «машины», у вас будет столько масштабируемости, сколько вы хотите, плюс преимущества использования библиотеки pythonic graph.

Если нет, то есть другие решения ( здесь и здесь ), которые могут потреблять меньше памяти (сравните и посмотрите, я думаю, что igraph полностью поддерживается на C, так и будет), но вы можете пропустить pythonic ощущение NX.