Какие проблемы масштабируемости связаны с NetworkX?

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

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

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

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

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

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

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

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

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

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

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