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