Обзор библиотек для работы с графами в Python: NetworkX и Graph-tool

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

Для работы с графами созданы библиотеки Python, наиболее востребованные из них — это NetworkX и Graph-tool. В нашем обзоре мы расскажем об этих продуктах, а также выясним практические аспекты работы с графами в программировании.

Что такое графы и как они используются в программировании

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

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

Наглядный пример: бизнесмену нужно посетить несколько городов в ходе деловой поездки. Известны расстояния между населенными пунктами, затраты на проезд на различных видах транспорта. Так, пользователю необходимо построить оптимальный маршрут — потратить минимум денег либо проехать минимальное расстояние, то есть провести как можно меньше времени в пути.

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

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

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

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

Графы в программировании

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

Работу с графами специалисты рассматривают на трех основных уровнях:

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

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

Сведения в базе можно визуализировать, выявляя связи между между узлами одного порядка — историческими событиями, географическими объектами и другими фактами.

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

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

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

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

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

На базе языка программирования Python созданы библиотеки для работы с графами. Рассмотрим наиболее востребованные из них, изучим их преимущества и ограничения.

NetworkX: введение и основные возможности

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

NetworkX предоставляет следующие возможности:

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

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

Для визуализации используют совместимую библиотеку Matplotlib, а также стороннюю программу для создания графиков Graphviz, которая позволяет работать со сложными сетевыми структурами.

Основные преимущества NetworkX в Python:

• Высокая производительность. Библиотека предоставляет возможность без проблем манипулировать крупными графами с числом вершин до 10 млн и ребер до 100 млн. Это позволяет работать с массивами данных — например, выгрузкой из соцсетей с многочисленной аудиторией. 
• Удобство в работе. Продуктом пользуются как профессиональные разработчики, так и любители. Встроенные модули визуализации отвечают за наглядность результатов, при этом коррекция возможна в реальном времени. 
• Эффективность. Поскольку библиотека написана на низкоуровневой структуре, аппаратные и программные ресурсы оборудования расходуются в оптимальном режиме. У пользователя есть дополнительные возможности по масштабированию, он менее зависим от технических ограничений.   
• Открытый исходный код. Разработчик может настраивать библиотеку NetworkX и расширять ее функционал в соответствии с конкретными задачами. Кроме того, пакет легко интегрируется с другим ПО.  
• Поддержка. У NetworkX есть подробная документация, в которой хорошо описаны все функции и ограничения библиотеки. В обновляемых репозиториях собраны готовые решения для программистов, значительно упрощающие работу. 
• Обширное комьюнити. Поскольку библиотека находится в свободном доступе, вокруг продукта сформировалось многочисленное сообщество пользователей — если возникнут сложности, у них всегда можно попросить помощи. 

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

Graph-tool: введение и основные возможности

Библиотека Graph-tool предназначена для операций с графами и статистического анализа сетей. В отличие от большинства аналогичных модулей Python, часть алгоритмов и структур пакета реализована на C++ с обширным использованием шаблонного метапрограммирования. Эта особенность делает библиотеку крайне производительной, что по использованию памяти и скорости вычислений приближает ее к показателям чистых библиотек на C++.

Функционал Graph-tool довольно разнообразен:

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

Несмотря на то, что библиотека Graph-tool создана около 15 лет назад, она до сих пор востребована в научных разработках и программировании. Популярность пакета обусловлена его преимуществами:

• Высокая производительность благодаря реализации основных алгоритмов на C++. По этому показателю Graph-tool на порядок превосходит другие библиотеки. 
• Мощная визуализация. С этой библиотекой легко создавать графики, используя разные алгоритмы и форматы вывода, в том числе непосредственно на экран. У Graph-tool собственные методы компоновки и интерактивные процедуры рисования. 
• Полная документация. Каждая функция библиотеки описана в открытой документации. Здесь же приведено множество примеров использования Graph-tool на практике.  
• Открытый исходный код. Программисты могут модифицировать модуль в зависимости от своих целей и задач. 

Сообщество Graph-tool не так велико, как у NetworkX, поскольку первым пользуются преимущественно профессиональные разработчики.

Сравнение NetworkX и Graph-tool

Сравним две популярные библиотеки по основным критериям:

• Производительность. По этому показателю Graph-tool опережает NetworkX, особенно если задача связана с большими графами. Преимущество Graph-tool обусловлено реализацией на C++ и поддержкой OpenMP для параллельного запуска нескольких алгоритмов.
• Простота применения. Освоить NetworkX гораздо проще, поэтому библиотека подходит для начинающих программистов. Graph-tool — продукт для более опытных разработчиков. 
• Функциональность. Оба пакета обладают внушительным функционалом, однако Graph-tool ориентирован на более сложные вычислительные задачи.
• Визуализация. NetworkX предлагает простые и понятные инструменты визуализации, при этом у Graph-tool — более требовательные и продвинутые решения. 
• Документация и сообщество. У NetworkX более обширная база пользователей и более подробная документация. Это объясняется востребованностью библиотеки среди любителей. 

Как видите, по ряду параметров Graph-tool превосходит NetworkX, однако это не значит, что она лучше. Все зависит от целей применения — в разных ситуациях пригодятся разные инструменты.

Когда использовать NetworkX, а когда Graph-tool

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

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

Graph-tool будет предпочтительным решением для работы с крупномасштабными сетями и графами в фундаментальных научных исследованиях. Если нужно обрабатывать огромные массивы данных, вычисления будут более быстрыми.

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

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