NetworkX

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

Что такое граф

В самом общем смысле граф — это математическая модель (абстракция) взаимосвязанных друг с другом объектов какой-либо природной или искусственной системы. Визуально она представляет собой вершины, соединенные друг с другом ребрами. Типичный пример подобной системы — авиатранспортное сообщение, в котором роль узлов выполняют города, а ребрами являются соединяющие их маршруты авиаперелетов. Таким образом, с помощью графов можно описать как структуру какой-либо системы, так и происходящие в ней процессы. 

Теория графов, помимо собственно изучения их самих как математических объектов, используется в различных областях:

• в фундаментальных научных исследованиях. Графы используются для описания различных явлений в химии, физике, социологии, антропологии, математике, теории вероятности, лингвистике и т.д. В частности, с помощью них изучается структура и взаимодействие внутри молекул, природных экосистем, человеческих сообществ, крупных астрофизических объектов. 
• в решении прикладных задач. Активно используются графы в программировании и компьютерных технологиях, связи, урбанистике, энергетике, навигации и т.д. Например, она помогает оптимизировать электрические и информационные сети, маршруты грузовых и пассажирских перевозок, алгоритмы работы поисковых систем, структуры сайтов, базы данных, рекомендации в соцсетях.

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

Возможности NetworkX

Библиотека NetworkX специально разработана для удобного изучения графов и манипулирования ими. К ее основным возможностям относятся:

• создание, изучение и работа с различными типами графов — в частности, с простыми, ориентированными и взвешенными;
• описание и манипуляция с различными видами данных, составляющих вершины графов — например, текстами, изображениями, электронными таблицами, временными рядами и т.д.;
• получение таких характеристик графов, как высота, степени вершин, длины путей, диаметр, радиус, промежуточности и т.д.;
• визуализация сетевых структур в виде двух-, трехмерных графиков (диаграмм);
• преобразование графов в распространенные форматы для их сохранения, передачи или загрузки, и другие функции.

Библиотека позволяет исследовать или начертить графы следующих типов:

• Простые неориентированные — в таких графах вершины соединяются одиночными ребрами, не имеющими вектора направленности (типичный пример — двухполосная дорожная система);
• Ориентированные — в графах этого типа связи между узлами имеют направление (примером такой структуры является река с притоками);
• Мультиграфы — в них парные вершины соединены более чем одним ребром, также допускается наличие петель (ребер, замыкающихся на один и тот же узел);
• Ориентированные мультиграфы — в таких графах соседние узлы соединяются несколькими направленными ребрами.

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

Для визуализации сетевых структур в библиотеке используются:

• Библиотека Matplotlib, написанная на языке Python и тоже распространяемая по свободной BSD-лицензии. Она применяется в основном для визуализации достаточно простых графов с относительно небольшим количеством вершин и ребер.

• Внешняя программа для построения графов Graphviz с открытым исходным кодом, разработанная компанией AT&T и распространяемая по лицензии EPL. C его помощью графы, заданные на специализированном языке описания DOT, визуализируются в виде графического или векторного файла. Graphviz позволяет обрабатывать более сложные сетевые структуры.

Визуализация графов на Python в NetworkX может быть двух- и трехмерной. Также пользователь имеет возможность подписывать вершины и ребра, выделять их цветом, задавать направление связей между узлами и т.д. 

Преимущества NetworkX

Производительность. Библиотека NetworkX способна свободно оперировать крупными сетевыми системами, содержащими до 10 миллионов вершин и 100 миллионов ребер между ними. Это особенно полезно при анализе больших данных — например, выгрузки из социальных сетей, объединяющих миллионы пользователей. 

Простота использования. Так как библиотека написана на языке Python, работа с ней не составляет особого труда как для профессиональных программистов, так и для любителей. А модули визуализации графов обеспечивают наглядность полученного результата, который можно корректировать в режиме реального времени. 

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

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

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

Применение NetworkX

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

В обучении. NetworkX отлично подходит для освоения самой математической теории графов. Библиотека позволяет работать с ними на уровне алгебраических формул или геометрической визуализации, что очень удобно для новичков. Также с помощью NetworkX можно изучать смежные математические дисциплины, такие как комбинаторика, теории вероятности, множеств, групп и т.д. 

В научных исследованиях. С помощью этой библиотеки можно изучать структуру и внутренние процессы, протекающие в различных микро- и макросистемах: от атомов и молекул до звездных систем и галактик. Особую популярность NetworkX получила в социологических исследованиях — для анализа человеческих сообществ и взаимосвязей в них.

В решении прикладных задач. NetworkX активно используется в следующих направлениях:

• в компьютерных технологиях — для построения информационных сетей, структур баз данных, файловых хранилищ и каталогов, проектирования систем искусственного интеллекта (нейросетей);
• в интернет-технологиях — для разработки структур сайтов, алгоритмов, используемых в социальных сетях и поисковых системах, а также анализа данных, выгружаемых с веб-ресурсов (например, информации о пользователях) и т.д.;
• в логистике — для построения оптимальных маршрутов, составления навигационных и дорожных карт;
• в финансовой сфере — для аудита банковских транзакций, денежных потоков, в биржевом анализе;
• в урбанистике — для эффективного планирования транспортной структуры городов, распределения электричества, воды и прочих ресурсов и т.д.

В целом, NetworkX может использоваться в любой области, где применяется теория графов. Ограничением является только масштаб исследуемой системы — из-за лимитированного числа вершин и ребер, доступных для анализа с помощью этой библиотеки.