СетьX
 График, созданный с помощью NetworkX | |
| Оригинальный автор(ы) | Арик Хагберг Питер Сварт Дэн Шульт |
|---|---|
| Разработчик(и) | Многие другие |
| Первоначальный выпуск | 11 апреля 2005 г [1] [2] |
| Стабильная версия | 3.3 [3]  / 6 апреля 2024 г |
| Репозиторий | |
| Написано в | Питон |
| Операционная система | Кросс-платформенный |
| Тип | Библиотека программного обеспечения |
| Лицензия | BSD-новая лицензия |
| Веб-сайт | сетьx |
| Часть серии о | ||||
| Сетевая наука | ||||
|---|---|---|---|---|
| Типы сетей | ||||
| Графики | ||||
| ||||
| Модели | ||||
| ||||
| ||||
NetworkX — библиотека Python для изучения графов и сетей . NetworkX — бесплатное программное обеспечение , выпущенное под новой лицензией BSD .
История [ править ]
NetworkX начала разработку в 2002 году Арика А. Хагберга, Дэниела А. Шульта и Питера Дж. Сварта. [4] Его поддерживает Национальная администрация по ядерной безопасности Министерства энергетики США в Национальной лаборатории Лос-Аламоса .
Пакет был создан с целью создания инструментов для анализа данных и стратегий вмешательства для контроля эпидемического распространения заболеваний, а также изучения структуры и динамики более общих социальных, биологических и инфраструктурных систем. [4]
Вдохновленный эссе Гвидо ван Россума 1998 года о представлении графов Python, [5] NetworkX публично дебютировал на ежегодной конференции SciPy в 2004 году . В апреле 2005 года NetworkX стал доступен как программное обеспечение с открытым исходным кодом. [1]
несколько пакетов Python, посвященных теории графов , включая igraph , graph-tool Доступно и многие другие. По состоянию на апрель 2024 года NetworkX было скачано более 50 миллионов раз. [6] превзойдя количество загрузок второго по популярности пакета igraph более чем в 50 раз. [7] Столь значительный уровень внедрения потенциально можно объяснить ранним выпуском NetworkX и его продолжающимся развитием в экосистеме SciPy.
В 2008 году SageMath , математическая система с открытым исходным кодом, включила NetworkX в свой пакет и добавила поддержку большего количества алгоритмов и функций построения графиков. [4]
| Версия | Дата выпуска | Основные изменения |
|---|---|---|
| 0.22 | 17 июня 2005 г. | Топологическая сортировка для тестирования ориентированных ациклических графов (DAG). Интеграция алгоритма Дейкстры для поиска кратчайших путей во взвешенных графах . [8] |
| 0.99 | 18 ноября 2008 г. | Тип графика по умолчанию изменен на взвешенный график. Представлены MultiGraph, MultiDiGraph, LabeledGraph и LabeledDiGraph. [8] |
| 1.0 | 8 января 2010 г. | Добавление операторов разности и пересечения. Реализация алгоритма A* для оптимизированного поиска пути. Включение алгоритмов PageRank , HITS и [собственного вектора] для сетевого анализа. Интеграция алгоритма Краскала построения минимальных остовных деревьев . [8] |
| 2.0 | 20 сентября 2017 г. | Значительные изменения в методах классов MultiGraph и DiGraph. Обновление системы документации .Различные изменения качества жизни пользователей. [8] |
| 3.0 | 7 января 2023 г. | Улучшенная интеграция с SciPy пакетами экосистемы . Добавлена новая функция плагина, позволяющая пользователям использовать различные серверные программы ( GraphBLAS , CuGraph) для вычислений. [9] |
Особенности [ править ]
- Классы графов и орграфов .
- Преобразование графиков в несколько форматов и обратно.
- Возможность построения случайных графиков или построения их поэтапно.
- Умение находить подграфы , клики , k-ядра .
- Исследуйте смежность , степень , диаметр , радиус , центр , расстояние и т. д.
- Рисуйте сети в 2D и 3D.
типы Поддерживаемые графиков
Обзор [ править ]
Графы в этом контексте представляют собой наборы вершин (узлов) и ребер (соединений) между ними. NetworkX обеспечивает поддержку нескольких типов графиков, каждый из которых подходит для разных приложений и сценариев.
Ориентированные графы (DiGraph) [ править ]
Ориентированные графы, или диграфы, состоят из узлов, соединенных направленными ребрами. В ориентированном графе ребра имеют направление, указывающее поток или взаимосвязь между узлами. [10]
Неориентированные графики (График) [ править ]
Неориентированные графы, называемые в NetworkX просто графами, — это графы, ребра которых не имеют внутреннего направления. Соединения между узлами симметричны, то есть если узел A соединен с узлом B, то узел B также соединен с узлом A. [11]
Мультиграфы [ править ]
Мультиграфы допускают наличие нескольких ребер между одной и той же парой узлов. Другими словами, MultiGraph допускает параллельные ребра , когда между двумя узлами может существовать более одного ребра. [12]
Мультидиграфы [ править ]
MultiDiGraph — это ориентированные графы, которые допускают наличие нескольких направленных ребер между одной и той же парой узлов. Подобно MultiGraph, MultiDiGraphs позволяет моделировать сценарии, в которых между узлами существуют множественные направленные связи. [13]
Проблемы визуализации [ править ]
Хотя NetworkX предоставляет мощные инструменты для создания и анализа графиков, создание визуализации сложных графиков может оказаться сложной задачей. Для визуализации больших или плотно связанных графов могут потребоваться специальные методы и внешние библиотеки, выходящие за рамки возможностей только NetworkX.
Макеты графиков [ править ]
NetworkX предоставляет различные алгоритмы компоновки для визуализации графиков в двумерном пространстве. Эти алгоритмы компоновки определяют положения узлов и ребер в визуализации графа, стремясь эффективно раскрыть его структуру и взаимосвязи.
Весенний макет [ править ]
Макет Spring — это алгоритм принудительного макетирования, вдохновленный физическими системами. Он моделирует силы притяжения и отталкивания между узлами, рассматривая края как пружины, а узлы как заряженные частицы. В результате получается макет, в котором узлы с сильными связями располагаются ближе друг к другу, а узлы с более слабыми связями раздвигаются дальше друг от друга. [14]
Спектральный макет [ править ]
Спектральный макет основан на спектральных свойствах матрицы смежности графа. Он использует собственные значения и собственные векторы матрицы смежности для позиционирования узлов в низкомерном пространстве. Спектральная компоновка имеет тенденцию подчеркивать глобальную структуру графа, что делает ее полезной для идентификации кластеров и сообществ. [15]
Круглая компоновка [ править ]
В макете «Круговой» узлы располагаются равномерно по кругу, а края рисуются в виде прямых линий, соединяющих их. Этот макет особенно подходит для визуализации циклических или симметричных графов , где расположение узлов по кругу отражает основную топологию графа. [16]
Компоновка оболочки [ править ]
Макет «Оболочка» объединяет узлы в концентрические круги или оболочки в зависимости от их расстояния от указанного центра. Узлы внутри одной оболочки находятся на одинаковом расстоянии от центра, а края рисуются радиально между узлами в соседних оболочках. Макет оболочки часто используется для визуализации иерархических или древовидных структур. [17]
Макет только для Камады [ править ]
Алгоритм компоновки Камада-Каваи позиционирует узлы на основе их попарных расстояний, стремясь минимизировать общую энергию системы. Он учитывает как топологию графа, так и длину ребер, в результате чего создается макет, подчеркивающий геометрическую точность и удобочитаемость. [18]
Использование [ править ]
NetworkX предоставляет функции для применения различных алгоритмов компоновки к графикам и визуализации результатов с помощью Matplotlib или других библиотек построения графиков. Пользователи могут указать желаемый алгоритм компоновки при вызове функций рисования, что обеспечивает гибкую и настраиваемую визуализацию графиков.
Пригодность [ править ]
NetworkX подходит для работы с большими реальными графами: например, графами, имеющими более 10 миллионов узлов и 100 миллионов ребер. [ нужны разъяснения ] [19] Благодаря своей зависимости от структуры данных «словарь словаря» на чистом Python, NetworkX представляет собой достаточно эффективную, очень масштабируемую и легко переносимую среду для анализа сетей и социальных сетей . [4]
Приложения [ править ]
NetworkX был разработан как простой в использовании и обучении, а также как мощный и сложный инструмент для сетевого анализа. Он широко используется на многих уровнях: от обучения информатике и анализу данных до крупномасштабных научных исследований. [4]
NetworkX имеет приложения в любой области, изучающей данные в виде графиков или сетей, например в математике, физике, биологии, информатике и социальных науках. [20] Узлы графа NetworkX могут быть специализированы для хранения любых данных, а данные, хранящиеся в ребрах, являются произвольными, что делает их широко применимыми в различных областях. Он способен считывать данные в сетях и случайным образом генерировать сети с заданными качествами. Это позволяет использовать его для изучения изменений в большом количестве сетей. [4] На рисунке ниже показан простой пример способности программного обеспечения создавать и изменять варианты в большом количестве сетей.
NetworkX имеет множество алгоритмов анализа сетей и графов, помогающих решать широкий спектр задач анализа данных. Одним из важных примеров этого являются различные варианты алгоритмов кратчайшего пути. Следующие алгоритмы включены в NetworkX, временная сложность которых определяется количеством вершин (V) и ребер (E) в графе: [21]
- Dijkstra : O((V+E) log V)
- Bellman-Ford : O(V * E)
- Гольдберг-Радзик: O(V * E)
- Джонсон : O(V^2 log(V) + VE)
- Floyd Warshall : O(V^3)
- A* : O((V+E) log V)
Пример использования графовых алгоритмов NetworkX можно увидеть в исследовании 2018 года, в котором он использовался для анализа устойчивости сетей животноводства к распространению эпидемий. В исследовании использовалась компьютерная модель для прогнозирования и изучения тенденций эпидемий в американских сетях свиноводства с учетом всех ролей животноводческой отрасли. В исследовании NetworkX использовался для поиска информации о степени, кратчайших путях, кластеризации и k-ядрах, поскольку модель вводила инфекции и имитировала их распространение. Затем это было использовано для определения того, какие сети наиболее подвержены эпидемиям. [22]
Помимо создания и анализа сетей, NetworkX также имеет множество возможностей визуализации. Он предоставляет возможности подключения к Matplotlib и GraphViz для 2D-визуалок, а также VTK и UbiGraph для 3D-визуалок. [4] Это делает пакет полезным для простой демонстрации и составления отчетов сетевого анализа и данных, а также позволяет упростить сети для визуальной обработки.
Интеграция [ править ]
NetworkX интегрирован в SageMath . [23]
См. также [ править ]
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б Первый публичный выпуск NetworkX (NX-0.2) , От: Арик Хагберг, Дата: 12 апреля 2005 г., список рассылки Python-announce-list
- ^ Первоначальная версия NetworkX, NX-0.2 , Хагберг - 11 апреля 2005 г., Информация о проекте - NetworkX, Зарегистрировано: 21 октября 2004 г., SourceForge.net
- ^ «Выпуск 3.3» . 6 апреля 2024 г. Проверено 8 апреля 2024 г.
- ^ Jump up to: Перейти обратно: а б с д и ж г Арик А. Хагберг, Дэниел А. Шульт, Питер Дж. Сварт, Исследование сетевой структуры, динамики и функций с использованием NetworkX , Материалы 7-й конференции Python в науке (SciPy 2008) , Г. Варокво, Т. Воут, Дж. Миллман (Ред.), стр. 11–15.
- ^ ван Россум, Гвидо (февраль 1998 г.). «Шаблоны Python — реализация графов» . Питон .
- ^ "сетьx" . Статистика ПиПи . Апрель 2024 г.
- ^ «Играф» . Статистика ПиПи . Апрель 2024 г.
- ^ Jump up to: Перейти обратно: а б с д «Журнал старых выпусков» . СетьX . 22 августа 2020 г. Проверено 24 апреля 2024 г.
- ^ «СетьХ 3.0» . СетьX . 7 января 2023 г. Проверено 24 апреля 2024 г.
- ^ «DiGraph — Ориентированные графики с циклами — Документация NetworkX 3.3» . networkx.org . Проверено 24 апреля 2024 г.
- ^ «График — неориентированные графы с самоциклами — документация NetworkX 3.3» . networkx.org . Проверено 24 апреля 2024 г.
- ^ «MultiGraph — неориентированные графы с циклами и параллельными ребрами — документация NetworkX 3.3» . networkx.org . Проверено 24 апреля 2024 г.
- ^ «MultiDiGraph — Ориентированные графы с циклами и параллельными ребрами — Документация NetworkX 3.3» . networkx.org . Проверено 24 апреля 2024 г.
- ^ «spring_layout — документация NetworkX 3.3» . networkx.org . Проверено 2 мая 2024 г.
- ^ «spectral_layout — документация NetworkX 3.3» . networkx.org . Проверено 2 мая 2024 г.
- ^ «circular_layout — документация NetworkX 3.3» . networkx.org . Проверено 2 мая 2024 г.
- ^ «shell_layout — документация NetworkX 3.3» . networkx.org . Проверено 2 мая 2024 г.
- ^ «kamada_kawai_layout — документация NetworkX 3.3» . networkx.org . Проверено 2 мая 2024 г.
- ^ Арик Хагберг, Дрю Конвей, «Взлом социальных сетей с использованием языка программирования Python (Модуль II – Почему SNA в NetworkX)» , Sunbelt 2010: Международная сеть анализа социальных сетей .
- ^ Хададж, П.; Стшалка, Д.; Новак, М. (19 октября 2022 г.). «Использование PLANS и NetworkX при моделировании отказов энергосистемы» . Научный представитель . 12 .
- ^ «Кратчайшие пути — документация NetworkX 3.3» . networkx.org . Проверено 29 апреля 2024 г.
- ^ Уилтшир, Серж В. (9 марта 2018 г.). «Использование агентной модели для оценки влияния специализации производителей на эпидемиологическую устойчивость сетей животноводства» . ПЛОС ОДИН .
- ^ «Система математического программного обеспечения SageMath — Sage» .