Python
8 August 2011

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
Мне очень понравилось работать с этой библиотекой. Использовал в паре мелких скриптов и надеюсь успешно внедрить в одно небольшое исследование.
Успешных проектов!

+53
39.3k 171
Comments 35
Top of the day