Наука о графических данных с помощью Python/NetworkX

Опубликовано: 2022-03-11

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

Мы часто используем таблицы для общего представления информации. Но графы используют специализированную структуру данных: вместо строки таблицы узел представляет элемент. Ребро соединяет два узла, чтобы указать их отношения.

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

Слева — график взаимодействия белков с множеством точек разного размера и цвета и линиями разных цветов между ними. Большинство точек (узлов) образуют большой центральный кластер, но некоторые точки соединены только парами, тройками или четверками на краях, не связанных с основным кластером. Справа — граф взаимодействия в Твиттере, где узлы имеют субпиксельный размер и делятся на три группы: плотный центральный кластер с несколькими нечеткими пятнами разных цветов и размеров, соединенными нечеткими потоками разных цветов; светлое облако, состоящее из мелких пятен и вкраплений преимущественно серого цвета; и буфер белого цвета перед внешним серым нечетким кольцом, окружающим первые два набора. — Левое изображение предоставлено: TITZ, Bjorn и др. «Интерактом бинарного белка бледной трепонемы…» PLoS One, 3, no. 5 (2008).

Право на изображение предоставлено: ALBANESE, Federico, et al. «Прогнозирование смены людей с помощью интеллектуального анализа текста и графического машинного обучения в Twitter». (24 августа 2020 г.): arXiv: 2008.10749 [cs.SI]

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

Начало работы с графами «Теория графов» в Python

Разработчикам Python доступно несколько библиотек графических данных, таких как NetworkX, igraph, SNAP и graph-tool. Помимо плюсов и минусов, у них очень похожие интерфейсы для обработки и обработки структур данных графа Python.

Мы будем использовать популярную библиотеку NetworkX. Он прост в установке и использовании и поддерживает алгоритм обнаружения сообщества, который мы будем использовать.

Создать новый график с помощью NetworkX очень просто:

 import networkx as nx G = nx.Graph()

Но G еще не является графом, так как не имеет узлов и ребер.

Как добавить узлы в график

Мы можем добавить узел в сеть, объединив возвращаемое значение Graph() с .add_node() (или .add_nodes_from() для нескольких узлов в списке). Мы также можем добавить к узлам произвольные характеристики или атрибуты, передав словарь в качестве параметра, как показано на node 4 и node 5 :

 G.add_node("node 1") G.add_nodes_from(["node 2", "node 3"]) G.add_nodes_from([("node 4", {"abc": 123}), ("node 5", {"abc": 0})]) print(G.nodes) print(G.nodes["node 4"]["abc"]) # accessed like a dictionary

Это выведет:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5'] 123

Но без ребер между узлами они изолированы, и набор данных ничем не лучше простой таблицы.

Как добавить ребра к графику

Подобно технике для узлов, мы можем использовать .add_edge() с именами двух узлов в качестве параметров (или .add_edges_from() для нескольких ребер в списке) и дополнительно включать словарь атрибутов:

 G.add_edge("node 1", "node 2") G.add_edge("node 1", "node 6") G.add_edges_from([("node 1", "node 3"), ("node 3", "node 4")]) G.add_edges_from([("node 1", "node 5", {"weight" : 3}), ("node 2", "node 4", {"weight" : 5})])

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

NetworkX перечисляет все ребра при использовании G.edges , но не включает их атрибуты. Если нам нужны атрибуты ребра, мы можем использовать G[node_name] , чтобы получить все, что подключено к узлу, или G[node_name][connected_node_name] , чтобы получить атрибуты определенного ребра:

 print(G.nodes) print(G.edges) print(G["node 1"]) print(G["node 1"]["node 5"])

Это выведет:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5', 'node 6'] [('node 1', 'node 2'), ('node 1', 'node 6'), ('node 1', 'node 3'), ('node 1', 'node 5'), ('node 2', 'node 4'), ('node 3', 'node 4')] {'node 2': {}, 'node 6': {}, 'node 3': {}, 'node 5': {'weight': 3}} {'weight': 3}

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

Как создавать изображения из графиков (и взвешенных графиков)

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

Быстрый вызов nx.draw(G) — это все, что нужно:

Шесть красных точек с черными линиями, соединяющими их. Четыре образуют четырехугольник, один угол которого соединяется с двумя оставшимися.

Давайте сделаем более тяжелые ребра соответственно толще с помощью нашего nx.draw() :

 weights = [1 if G[u][v] == {} else G[u][v]['weight'] for u,v in G.edges()] nx.draw(G, width=weights)

Мы указали толщину по умолчанию для невесомых краев, как видно из результата:

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

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

Наука о графических данных с использованием данных из фильма «Звездные войны: Эпизод IV»

Чтобы упростить интерпретацию и понимание наших результатов, мы будем использовать этот набор данных. Узлы представляют важные персонажи, а ребра (которые здесь не взвешиваются) означают совместное появление в сцене.

Примечание. Набор данных взят у Габасовой Э. (2016). Социальная сеть Звездных войн. DOI: https://doi.org/10.5281/zenodo.1411479.

Во-первых, мы визуализируем данные с помощью nx.draw(G_starWars, with_labels = True) :

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

Персонажи, которые обычно появляются вместе, такие как R2-D2 и C-3PO, кажутся тесно связанными. Напротив, мы видим, что Дарт Вейдер не делится сценами с Оуэном.

Макеты визуализации Python NetworkX

Почему каждый узел находится там же, где и на предыдущем графике?

Это результат алгоритма spring_layout по умолчанию. Он имитирует силу пружины, притягивающей соединенные узлы и отталкивающей разъединенные. Это помогает выделить хорошо связанные узлы, которые оказываются в центре.

В NetworkX есть и другие макеты, которые используют другие критерии для позиционирования узлов, например, circular_layout :

 pos = nx.circular_layout(G_starWars) nx.draw(G_starWars, pos=pos, with_labels = True)

Результат:

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

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

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

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

У этого есть специальная функция рисования:

 nx.draw_kamada_kawai(G_starWars, with_labels = True)

Вместо этого получается эта форма:

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

Без какого-либо специального вмешательства алгоритм поместил главных персонажей (таких как Люк, Лея и C-3PO) в центр, а менее заметных (таких как Кейми и генерал Додонна) — на границу.

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

Анализ узла: степень и PageRank

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

Одной из основных метрик узла является его степень: сколько у него ребер. Степень узла персонажа « Звездных войн » измеряет, со сколькими другими персонажами они делили сцену.

Функция degree() может вычислить степень персонажа или всей сети:

 print(G_starWars.degree["LUKE"]) print(G_starWars.degree)

Вывод обеих команд:

 15 [('R2-D2', 9), ('CHEWBACCA', 6), ('C-3PO', 10), ('LUKE', 15), ('DARTH VADER', 4), ('CAMIE', 2), ('BIGGS', 8), ('LEIA', 12), ('BERU', 5), ('OWEN', 4), ('OBI-WAN', 7), ('MOTTI', 3), ('TARKIN', 3), ('HAN', 6), ('DODONNA', 3), ('GOLD LEADER', 5), ('WEDGE', 5), ('RED LEADER', 7), ('RED TEN', 2)]

Сортировка узлов от высшего к низшему по степени может быть выполнена с помощью одной строки кода:

 print(sorted(G_starWars.degree, key=lambda x: x[1], reverse=True))

Выход:

 [('LUKE', 15), ('LEIA', 12), ('C-3PO', 10), ('R2-D2', 9), ('BIGGS', 8), ('OBI-WAN', 7), ('RED LEADER', 7), ('CHEWBACCA', 6), ('HAN', 6), ('BERU', 5), ('GOLD LEADER', 5), ('WEDGE', 5), ('DARTH VADER', 4), ('OWEN', 4), ('MOTTI', 3), ('TARKIN', 3), ('DODONNA', 3), ('CAMIE', 2), ('RED TEN', 2)]

Будучи суммой, степень не принимает во внимание детали отдельных ребер. Соединяется ли данное ребро с изолированным узлом или с узлом, связанным со всей сетью? Алгоритм Google PageRank объединяет эту информацию, чтобы оценить, насколько «важным» является узел в сети.

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

Такие узлы будут иметь более высокий PageRank, который мы можем рассчитать с помощью библиотеки NetworkX:

 pageranks = nx.pagerank(G_starWars) # A dictionary print(pageranks["LUKE"]) print(sorted(pageranks, key=lambda x: x[1], reverse=True))

Это печатает ранг Люка и наших персонажей, отсортированных по рангу:

 0.12100659993223405 ['OWEN', 'LUKE', 'MOTTI', 'DODONNA', 'GOLD LEADER', 'BIGGS', 'CHEWBACCA', 'LEIA', 'BERU', 'WEDGE', 'RED LEADER', 'RED TEN', 'OBI-WAN', 'DARTH VADER', 'CAMIE', 'TARKIN', 'HAN', 'R2-D2', 'C-3PO']

Оуэн — персонаж с самым высоким PageRank, превосходящим Люка, имевшего самую высокую степень. Анализ: хотя Оуэн не является персонажем, который разделяет большинство сцен с другими персонажами, он является персонажем, который разделяет сцены со многими важными персонажами, такими как сам Люк, R2-D2 и C-3PO.

Наоборот, C-3PO, персонаж с третьей по величине степенью, имеет самый низкий PageRank. Несмотря на то, что у C-3PO много связей, многие из них связаны с неважными персонажами.

Вывод: использование нескольких метрик может дать более глубокое представление о различных характеристиках узлов графа.

Алгоритмы обнаружения сообщества

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

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

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

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

С библиотекой NetworkX запуск этого алгоритма занимает всего три строки Python:

 from networkx.algorithms.community.label_propagation import label_propagation_communities communities = label_propagation_communities(G_starWars) print([community for community in communities])

Выход:

 [{'R2-D2', 'CAMIE', 'RED TEN', 'RED LEADER', 'OBI-WAN', 'DODONNA', 'LEIA', 'WEDGE', 'HAN', 'OWEN', 'CHEWBACCA', 'GOLD LEADER', 'LUKE', 'BIGGS', 'C-3PO', 'BERU'}, {'DARTH VADER', 'TARKIN', 'MOTTI'}]

В этом списке наборов каждый набор представляет сообщество. Читатели, знакомые с фильмом, заметят, что алгоритму удалось идеально отделить «хороших парней» от «плохих парней», осмысленно различая персонажей без использования каких-либо истинных (общественных) ярлыков или метаданных.

Интеллектуальные идеи с использованием науки о графических данных в Python

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

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