Время прочтения: 3 мин.

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

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

Загружаем пакет igraph.

library(igraph)

Далее сформируем датафрейм df и на основе него создадим граф my_graph с помощью метода graph_from_data_frame. Признак directed=TRUE определяет то, что граф направленный, в нашем случае от  Sender к Recepient. Если же хотим работать просто со связями, то указываем directed=FALSE.

df <- data.frame(Sender = c("Кролик", "Кролик", "Винни-Пух", "Иа-Иа", "Иа-Иа", "Пятачек", "Сова"),
                 Recepient = c("Сова", "Сова", "Сова", "Сова", "Иа-Иа", "Сова", "Кристофер-Робин"),
                 Sum = c(23,2,41,32,10,55,40))
my_graph <- graph_from_data_frame(df, directed = TRUE)

Посмотрим содержание нашего графа.

my_graph

IGRAPH 1324238 DN-- 6 7 -- 
+ attr: name (v/c), Sum (e/n)
+ edges from 1324238 (vertex names):
[1] Кролик   ->Сова            Кролик   ->Сова            Винни-Пух->Сова            Иа-Иа    ->Сова           
[5] Иа-Иа    ->Иа-Иа           Пятачек  ->Сова            Сова     ->Кристофер-Робин

 Теперь попробуем вывести изображение на основе полученного графа.

plot(my_graph, layout=layout.fruchterman.reingold)

На изображении видно, что в нашем графе присутствуют множественное ребро (Кролик->Сова) и петля (Иа-Иа). Для избавления от множественных ребер и петель применим метод simplify.

my_graph <- simplify(my_graph)
plot(my_graph, layout=layout.fruchterman.reingold)

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

my_graph_degree <- degree(my_graph)
Кролик      Винни-Пух           Иа-Иа        Пятачек            Сова  Кристофер-Робин              
1           1                   1            1                  5     1                  

Построим гистограмму с частотой связей по вершинам графа.

hist(my_graph_degree)

Рассмотрим ещё одну интересную функцию, как поиск и выделение подграфов. Здесь нам поможет метод induced_subgraph, который создаёт (выделяет) подграф, содержащий только определенные вершины и рёбра между ними.

my_graph2 <- induced_subgraph(my_graph, 1:5)
plot(my_graph2, layout=layout.fruchterman.reingold)

Получаем подграф с первой по пятую вершину нашего основного графа:

Так же в igraph есть метод write_graph для сохранения графа в файл.

write_graph(my_graph2, file='my_graph.txt', format="ncol")

В данном случае мы используем значение format=»ncol» для возможности восстановления графа с именованными вершинами. Для чтения графа из файла нужно будет воспользоваться методом read_graph.

my_graph3 = read_graph(file='my_graph.txt', format="ncol", directed = TRUE)

В заключение хочу отметить, что open source пакет igraph  прост  в использовании, эффективен и имеет довольно высокую популярность наряду с такими пакетами, как sna. А имеющиеся отличные средства визуализации для R (например, ggplot2) предоставляют широкие возможности для решения задач графового (сетевого) анализа.