NetworkX для удобной работы с сетевыми структурами


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


    Возможности библиотеки


    Библиотека networkX создана на языке Python и предназначена для работы с графами и другими сетевыми структурами. Это свободное ПО распространяемое под новой BSD лицензией.
    Основные возможности библиотеки:
    • Классы для работы с простыми, ориентированными и взвешенными графами;
    • Узлом может быть практически что угодно: time-series, текст, изображение, XML;
    • Сохранение / загрузка графов в/из наиболее распространённых форматов файлов хранения графов;
    • Встроенные процедуры для создания графов базовых типов;
    • Методы для обнаружения подграфов, клик и К-дольных графов (K-core) ( максимальный подграф в котором каждая вершина имеет по крайней мере уровень К ).
    • Получение таких характеристик графа как степени вершин, высота графа, диаметр, радиус, длинны путей, центр, промежуточности, и т. д.;
    • Визуализировать сети в виде 2D и 3D графиков;
    • И многое другое…


    Производительность


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

    Основные структуры данных


    Библиотека организована в виде иерархии пакетов. Верхний уровень в каждом пакете предоставляет общие методы по манипуляции его структурами, более нижние приобретают бóльшую и бóльшую специализацию.
    Во всех далее идущих примерах, networkX подключен следующей директивой:
     >>> import networkx as nx


    Класс граф


    Поддерживаются следующие основные типы графов:
    • Graph – реализация простого неориентированного графа. Дополнительные вершины между двумя узлами игнорируются, возможны узлы соединённые с самим собой.
    • DiGraph — ориентированный граф, добавлены функции и ограничения специфические для этого типа графов.
    • MultiGraph — реализация мультиграфов, в таких графах граф, возможно существование пар вершин, которые соединены более чем одним ребром (ненаправленным), либо более чем двумя дугами противоположных направлений.
    • MultiDiGraph — соответственно ориентированный мультиграф.

    Примеры создания пустых графов различного типа:
    
    >>> G=nx.Graph()
    >>> G=nx.DiGraph()
    >>> G=nx.MultiGraph()
    >>> G=nx.MultiDiGraph()
    


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

    Узлы и дуги


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

    Создание графа


    На данный момент граф может быть создан с использованием одного из трёх методов:
    • 1. Генератор графов — предопределённые классы для создания графов общих топологий, таких как полные графы различных уровней, сбалансированные деревья, циклические графы, графы Дороговцева — Гольтцева — Мендеса, случайные биномиальные и многих других типов. Подробнее в документации: networkx.lanl.gov/reference/generators.html
    • 2. Загрузка данных и формирование графа на основе файла или потока данных одного из поддерживаемых форматов:
      1. Матрица смежности
      2. Матрица инцидентности
      3. GEXF
      4. GML
      5. Pickle
      6. GraphML
      7. LEDA
      8. YAML
      9. SparseGraph6
      10. Pajek
      11. GIS Shapefile

    • 3. Последовательное добавление узлов и дуг.

    Созданный граф имеет как общие, так и специфические для своего типа методы.
    
    >>> import networkx as nx
    >>> G=nx.Graph()
    >>> G.add_edge(1,2)  # значение по умолчанию для дуги задаётся = 1
    >>> G.add_edge(2,3,weight=0.9) # задаётся значение атрибута
    

    В качестве добавляемых значений могут служить данные разнообразных типов:
    
    >>> import math
    >>> G.add_edge('y','x',function=math.cos)
    >>> G.add_node(math.cos) # любой объект типа hashable может быть узлом
    

    Дуги могут быть добавлены также и из массивов и котрежей данных:
    
    >>> elist=[('a','b',5.0),('b','c',3.0),('a','c',1.0),('c','d',7.3)]
    >>> G.add_weighted_edges_from(elist)
    


    Получение информации о графе


    Кроме создания графа обычно нужно получать информацию о его узлах, дугах, путях и пр. Основными методами для этого является получение массивов узлов и дуг (edges() и nodes() соответственно), а также получение итератора по узлам и дугам (edges_iter() и nodes_iter() соответственно).
    Дополнительно существует большое количество функций получения более специфической информации о графе, к примеру nx.triangles(G,n) вернёт количество треугольников в графе G в которых вершина n является одним из узлов.
    Все доступные функции описаны в разделе документации по адресу networkx.lanl.gov/reference/algorithms.

    Предопределённые алгоритмы


    В библиотеке реализовано большое количество типичных для работы над графами алгоритмов. Реализованы такие алгоритмы как нахождение кратчайшего пути, поиска в высоту и ширину, кластеризация, нахождение изоморфизма графов и многое другое.
    К примеру, алгоритм Дейкстры нахождения минимального пути на взвешенном графе реализуется следующим образом:
    
    >>> G=nx.Graph()
    >>> e=[('a','b',0.3),('b','c',0.9),('a','c',0.5),('c','d',1.2)]
    >>> G.add_weighted_edges_from(e)
    >>> print(nx.dijkstra_path(G,'a','d'))
    ['a', 'c', 'd']
    


    Визуализация графов


    Основной целью библиотеки является работа с графами, и их визуальное отображение вторично, но реализовано, так-как является важным инструментом анализа.
    Предоставлены удобные методы для отображения графов с использованием Python библиотеки Matplotlib или внешнего модуля Graphviz для боле сложных случаев. Полная документация о возможностях визуализации приведена по адресу networkx.lanl.gov/reference/drawing.html.
    Простой пример визуализации графа:
    
    >>> G=nx.cubical_graph()
    >>> nx.draw(G)   # тип по умолчанию spring_layout
    >>> nx.draw(G,pos=nx.spectral_layout(G), nodecolor='r',edge_color='b')
    


    Визуализация с использованием Matplotlib


    Визуализация с использованием Graphviz


    Структуры данных


    Всё внутреннее представление графов использует словарь словарей в качестве основного типа данных. Такой подход имеет много преимуществ. К примеру удобный доступ к узлам использованием нотации доступа к элементам многомерного массива:
    
    >>> G=nx.Graph()
    >>> G.add_edge(1,2,color='red',weight=0.84,size=300)
    >>> print(G[1][2]['size'])
    300
    


    Более подробная документация расположена по адресу http://networkx.lanl.gov/reference/index.html
    Мне очень понравилось работать с этой библиотекой. Использовал в паре мелких скриптов и надеюсь успешно внедрить в одно небольшое исследование.
    Успешных проектов!
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 35

      +1
      Спасибо. Весьма кстати.
        +1
        Если блуждать взглядом по второй картинке ДПВ, мне одному кажется, что они шевелятся?
        Это потомучто 2 ночи или всётаки какой-то оптический эффект?
          0
          Просто глаз выпуклый, а картинка плоская, вот при перемещении зрачка окружающие фокус мелкие детали получают иллюзию движения.
          На этом некоторые оптические иллюзии построены.
            0
            вроде бы для подобной иллюзии должен быть определённый дрифт контраста цвета у «движущихся» элементов: www.michaelbach.de/ot/mot_snakeAdLib/index.html
            а тут этого явно нету.
              0
              Возможно конечно усталость глаз после рабочего дня также делает своё дело. Одно скажу, это не спец-эффект, там простой цикл генерации всевозможных графов до шести узлов включительно.
              networkx.lanl.gov/examples/drawing/atlas.html
            0
            У меня всего 12 ночи, а они шевелятся.
              0
              Нет. Идите спать )
              0
              Ещё б классно посмотреть визуализацию в 3d. И может ли оно подписывать дуги/вершины?
              PS Ссылочку на networkx.lanl.gov/reference/drawing.html подправьте пожалуйста
                0
                Подправил. Подписывать конечно может. И дуги и вершины. Вот к примеру орграф
                  0
                  Ещё возможности по настройке шрифта, размера и цвета как текста, так и формы и заливки узла. Плюс можно добавлять неограниченное количество своих свойств. Вот только как сказано ниже, с уникодом проблемы пока
                  0
                  В 3d это выглядит примерно так: .
                  Вот ссылка на проект:
                    +1
                    Сорри, кармы не хватает для отображения ссылок. Проект называется ostis.net. Видео можно найти на ютюбе.
                      0
                      Там точно NetwokX используется? Нашёл на youtube только это видео с трёхмерным графом и ostis.net www.youtube.com/watch?v=kRCE6_tmdso&feature=related
                        0
                        Нет, не NetworkX. Потрогать можно здесь: sourceforge.net/projects/ostis/
                  +1
                  А по существу:
                  там уже починили проблемы с хранением юникода в качестве меток узлов/дуг и выводом этого в dot, или положились на питон 3.x?
                    0
                    С уникодом всё ещё проблемы, да
                      0
                      да уж.
                      причом во всех доступных рисовалках.
                    +1
                    Как глянул на рисунок — топологии простых графов, к-а-а-а-а-к представил себе такую рабочую сеть — сразу захотелось повеситься.
                    А за либу мерси — можно поиграться на досуге.
                      0
                      Полезно. Для некоторых задач не нужно будет выдумывать велосипеды.
                      Хотя иногда графы приятно самому «прочувствовать».
                        0
                        Скажите, а как можно по-нормальному нарисовать дерево заданное в виде ориентированного графа?
                          0
                          Что Вы подразумеваете под «нормально»?
                          Graphviz даёт больше контроля, но и чуть сложней в использовании. По умолчанию для визуализации используется matplotlib, которая имеет своё представление как надо лучше. В принципе можно получить что-то похожее на это:
                            0
                            Извините, что не уточнил сразу.
                            Я хочу рисовать планарный граф, у которого все вершины одного яруса лежат на одной прямой.
                            Например вот так:
                            image
                              0
                              Готовой функции для такого дерева я там не видел. Меня вполне устроило дерево из моего предыдущего коммента и я просто глубже не копал.
                              Уверен, можно настроить и для вывода планарного графа. NetworkX заточен под работу с данными и визуализация вторична.
                              Вот документация
                              networkx.lanl.gov/reference/drawing.html
                              Также никто не мешает использовать другие либы для вывода изображений.

                              Возможно кто-нибудь другой сталкивался и отпишется
                            +1
                            dot сам рисует деревья «нормально», хотя строгое выравнивание не гарантируется.
                              0
                              Действительно, похоже как раз, что нужно jmistx
                              en.wikipedia.org/wiki/DOT_language
                                0
                                Насколько я понимаю, DOT — это язык и сам он ничего не рисует, есть программы для визуализации.
                                Дело в том, что есть готовый набор скриптов на python, которые уже юзают networkx в данный момент.
                                И если использовать dot для python, то для этого видел только одну либу: python-graph, а значит нужно либо переходить на него, либо писать модуль для экспорта networkx графов в DOT. Оба варианта достаточно затратные по времени.

                                Спасибо за информацию по DOT
                                  0
                                  В статье на вики о DOT упоминается Graphviz, так-что networkx.lanl.gov/pygraphviz/ вполне должен работать с ним. Я так понимаю его разрабатывают те же, кто и NetworkX
                                    0
                                    в пакет graphviz входит несколько утилит для рисования, реализующих разные алгоритмы расклада:
                                    dot, neato, circo, итп

                                    вот тот, который /usr/bin/dot — рисует «нормально»
                                      +1
                                      в networkx есть функция write_dot которая выводит граф в формате dot
                                        0
                                        И делает это она используя pygraphviz, который в свою очередь является обёрткой над graphviz
                                          0
                                          Да вот только что во время написания скрипта на неё наткнулся, пошёл сюда написать, а вы уже ответили.

                                          Спасибо, буду юзать.
                                            0
                                            имейте ввиду — юникод не поддерживается, никак.
                                            если метки с русскими буквами, то придётся писать свою функцию выгрузки в dot.
                                            0
                                            networkx.write_dot завязан на pygraphviz, который под windows в чистом виде не поставляется.
                                            После правок инсталяционного файла и компиляции нужной библиотеки при помощи Visual Studio ничего не заработало.

                                            Ждём пока у разработчика pygraphviz появится девелоперская машина под windows. К слову говоря, времени, потраченного на попытки установить pygraphviz под windows хватило бы на реализацию визуализации networkx дерева на matplotlib.

                                            В любом случае спасибо за советы.
                                      0
                                      Доброго времени суток! Пытаюсь написать автотест, основанный на рохождении орграфа. В вашей статье написано про встраивание функции в ребро. Можете показать чуть более развернутый пример с обходом графа и выполнением функций на рёбрах? Доки курятся с трудом, а сроки горят. Заранее спасибо
                                        0
                                        Доброго дня. К сожалению, давно не заходил на Хабр, не увидел Вашего вопроса во время.
                                        Насколько я понял Вашу задачу, Вы строите граф Вашей проблемы и при переходе от теста к тесту хотите выполнять ещё какие-то функции зависимые именно от этих двух тестов: текущего и следующего. Если это так, то, в принципе, всё просто, при создании дуги между узлами 2 и 3 просто добавляете нужные Вам параметры, и затем, при обходе вызываете нужную Вам функцию с параметрами сохранёнными в дуге.
                                        Если Вам нужно ещё и разные функции вызывать, то предлагаю записывать параметр в виде JSON строки, как-то так: "{'function_name':'func_1','param_1':'p1','param_2':'p2'}". Тогда парсите эту строку в объект, и вызываете то, что нужно с требуемыми параметрами.

                                        G.add_edge(2,3,weight=0.9) # задаётся значение атрибута weight

                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                      Самое читаемое