Графы применяются во множестве отраслей — от программирования до социологии. Рассматриваем две библиотеки Python для работы с графами — NetworkX и Graph-tool, а также их преимущества и недостатки.
В математике и программировании графы — это структурированная группа данных, которые представляют собой связанные элементы. Благодаря гибкости этих элементов и их способности сохранять данные в удобной для использования форме, они широко применяются в программировании и сфере технологий. В настоящее время одна из самых популярных отраслей, в которых используются графы — машинное обучение.
Для работы с графами созданы библиотеки Python, наиболее востребованные из них — это NetworkX и Graph-tool. В нашем обзоре мы расскажем об этих продуктах, а также выясним практические аспекты работы с графами в программировании.
Что такое графы и как они используются в программировании
Графы — это связанные между собой элементы, называемые узлами или вершинами. Это узлы содержат определенную информацию и соединяются с помощью ребер, что делает каждый граф определенной структурой данных.
Что должен знать каждый Python-разработчик: библиотеки и фреймворкиtproger.ru
На практике любые массивы информации можно разложить на простые графы. Даже картинки на экране — это сетка связанных друг с другом пикселей, а текст — последовательность букв и слов. Несмотря на относительно простую структуру графов, некоторые задачи решить без них невозможно.
Наглядный пример: бизнесмену нужно посетить несколько городов в ходе деловой поездки. Известны расстояния между населенными пунктами, затраты на проезд на различных видах транспорта. Так, пользователю необходимо построить оптимальный маршрут — потратить минимум денег либо проехать минимальное расстояние, то есть провести как можно меньше времени в пути.
Такая задача выглядит простой, но представьте, если узлов (городов) несколько десятков, а стоимость проезда на одном том же виде транспорта зависит от размера багажа, времени суток и других факторов.
Подобные задачи ежедневно приходится решать логистическим компаниям, и без графов разобраться с ними крайне непросто. Как ни пытайся представить эти данные, в итоге получится структурированный граф с ребрами, имеющими обозначенную ценность (в нашем случае в виде расстояния и/или стоимости проезда). При этом могут быть и дополнительные условия — например, посетить каждый город можно только один раз. С помощью графов решаются задачи, в которых количество узлов и связей между ними может быть огромным.
На улице ML-специалистов праздник: состоялся крупнейший апдейт NumPy за последние 18 летtproger.ru
Сами по себе графы — один из наиболее древних способов структурирования информации. С помощью кружочков и линий проще всего представить связь между объектами. При этом на основании существующих связей пользователь может прогнозировать вероятные взаимодействия узлов друг с другом. Например, если объект А знаком с объектами В и С, есть высокая вероятность, что В и С тоже знакомы или познакомятся в будущем.
Собственно теория графов была сформулирована еще в 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 удобно изучать смежные дисциплины — например, теорию вероятности, комбинаторику. Библиотека востребована и в социологических исследованиях — инструмент используется для аналитики сообществ и поиска взаимосвязей в них.