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