Виды графиков и их характеристики

Авторы Хайме Д. Асеведо-Вилориа, Ана М. Кинтеро Осса, Луиза Ф. Роа

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

Здесь мы перейдем к описанию различных типов графов, их характеристик и реальных приложений, где мы можем их найти.

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

pip/pip3 install networkx

Давайте рассмотрим характеристики и свойства графиков!

Необходимые библиотеки

Первым шагом будет импорт необходимых библиотек для построения и анализа графиков и их свойств.

import networkx as nx
import random
import matplotlib.pyplot as plt

Направленный или ненаправленный

Это свойство относится к тому, имеют ли ребра, соединяющие графы, собственное направление.

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

#Initilize a random graph
g_gaussian = nx.gaussian_random_partition_graph(25, 4, 5, 0.25, 0.1, directed=False, seed=23)

#Plot the graph structure
nx.draw(g_gaussian, with_labels=True)

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

#Initilize a random graph
g_gaussian_dir = nx.gaussian_random_partition_graph(25, 4, 5, 0.25, 0.1, directed=True, seed=23)
#Plot the graph structure
nx.draw(g_gaussian_dir, with_labels=True)

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

Эта характеристика имеет большое значение в реальных сценариях. При создании графиков у нас может быть Instagram (социальная сеть), где пользователь может подписаться на другого пользователя, но не обязательно наоборот. Это будет ориентированный граф.

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

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

Мы также можем видеть это, извлекая ребра графа с помощью метода edge(), взгляните:

g_gaussian.edges()
g_gaussian_dir.edges()

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

Взвешенные и невзвешенные

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

Мы создаем граф с 35 узлами и 50 случайными ребрами с помощью функции gnm_random_graph, затем мы присваиваем ребрам свойства «веса» со случайной вероятностью. Кроме того, давайте теперь предположим, что это социальная сеть, где каждый узел - это человек, который имеет разные связи с друзьями или семьей, если вес больше 0,6, то связь более тесная, поэтому они семья, но если вес равен меньше 0,6, то отношения менее крепкие и они друзья.

#Inicialize a random graph
G=nx.gnm_random_graph(35, 50, seed=12)
#Assign a random weights
for (u, v) in G.edges():
  G.edges[u,v]['weight'] = random.random()

#Define type of relationship - Family have a higher importance than friends
family = [(u, v) for (u, v, d) in G.edges(data=True) if d["weight"] >= 0.6]
friend = [(u, v) for (u, v, d) in G.edges(data=True) if d["weight"] < 0.6]

#Plot - Family relationship (red edge) - Friendship (blue edge)
pos = nx.spring_layout(G, seed=124)
nx.draw_networkx_nodes(G, pos)
nx.draw_networkx_edges(G, pos, edgelist=family, width=2, edge_color='r', alpha = 0.4)
nx.draw_networkx_edges(G, pos, edgelist=friend, width=1, edge_color='b', alpha = 0.4)
nx.draw_networkx_labels(G, pos)
ax = plt.gca()
ax.margins(0.08)
plt.axis("off")
plt.tight_layout()
plt.show()

Хотя это простой пример, во многих реальных приложениях важно учитывать взвешенные ребра, поскольку не все отношения равны. Кроме того, затронуты различные алгоритмы графов (следите за обновлениями в этом посте). Например, в алгоритме кратчайшего пути мы используем веса ребер, чтобы определить наименьшую стоимость доставки из узла x в узел y.

Разреженные и плотные графики

Плотность графа относится как к количеству узлов, так и к тому, насколько они связаны. В математике плотный граф — это граф, в котором количество ребер близко к максимальному количеству ребер. Максимальное количество ребер — это все парные комбинации узлов в неориентированном графе и все парные перестановки узлов в неориентированном графе.

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

Давайте рассмотрим несколько примеров NetworkX:

Мы создаем графики, используя метод генератора erdos_renyi_graph, это обычно используемая модель для генерации случайных графиков из двух параметров: количество узлов n и вероятность создайте ребро для каждой пары узлов p.

Поэтому для разреженного графа мы устанавливаем низкую вероятность 0,08, а для плотного графа устанавливаем вероятность 0,15.

Разреженный график

#Initilize a random graph - n=25, p=0.08
g_sparse = nx.erdos_renyi_graph(25, 0.08,seed=23)
#Plot the graph structure
nx.draw(g_sparse, with_labels=True)

Плотный график

#Initilize a random graph - n=25, p=0.15
g_dense = nx.erdos_renyi_graph(25, 0.15,seed=23)
#Plot the graph structure
nx.draw(g_dense, with_labels=True)

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

Ненаправленный:

Направлено:

Теперь давайте измерим плотность созданных ранее графов!

n = 25
e_sparse = g_sparse.number_of_edges()
e_dense = g_dense.number_of_edges()
def calculate_undirected_graph_density(n,e):
    return (2*e)/(n*(n-1))
density_sparse = calculate_undirected_graph_density(n,e_sparse)
density_dense = calculate_undirected_graph_density(n,e_dense)
print("The density of the sparse graph is:",round(density_sparse,2))
print("The density of the dense graph is: ",round(density_dense,2))
The density of the sparse graph is:  0.06 
The density of the dense graph is:  0.14

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

С другой стороны, в реальных задачах очень часто встречаются разреженные графы. Просто подумайте о том, чтобы быть на связи с каждым пользователем на Facebook или следить за каждой учетной записью в Twitter; это было бы почти невозможно! Следовательно, разреженный анализ может быть полезен на подграфах основного графа, оценивая сложность алгоритмов или определяя разреженную матрицу для представления графов (о чем мы поговорим в следующем посте).

Однородные и разнородные графики

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

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

Давайте перейдем к практическому примеру!

В этом случае мы строим случайный граф с 25 узлами и вероятностью 0,15 наличия ребра между узлами. Для нашего примера мы рассматриваем компанию связи, где на графике учитываются звонки между пользователями. В частности, компания хочет провести различие между новыми пользователями (менее 12 месяцев) и старыми пользователями (более 12 месяцев), чтобы понять, различается ли поведение между пользователями.

#Inicialize a random graph
G=nx.erdos_renyi_graph(25, 0.15,seed=45)
#Assign type of node
for u in G.nodes():
   rand = random.randint(0, 48)
   G.nodes[u][‘Type’] = 1 if rand < 12 else 0
color_val = [nx.get_node_attributes(G,’Type’).get(node) for node in G.nodes()]
nx.draw(G, pos, with_labels=True, node_color = color_val)

Как и в нашем примере, большинство реальных графов представляют собой разнородные графы, в которых взаимодействуют различные объекты. Довольно сложно описать процесс только с одним типом объекта, взаимодействующим с другими объектами того же типа, что делает гетерогенные графы более сложными для работы, но также и более выразительными для процесса, который они описывают. Однако существуют разные методы преобразования однородных графов в разнородные и наоборот. Например, представьте университетскую сеть, в которой у вас есть два типа узлов: студенты и классы. Интуитивно вы можете связать учеников с классами, но после того, как вы получите этот граф, вы можете удалить узлы «классы» и преобразовать их в ребра между учениками.

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

Заключительные мысли

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

Оставайтесь с нами!

Доступ к коду здесь

Виды графиков и их характеристики