Установка и подгрузка пакета igraph

# install.packages('igraph')
library('igraph')

Мы привыкли, что для нас граф это матрица смежности. И мы работаем только с ней. Но пакеты, которые работают с графами делают свои объекты, с которыми мы потом непосредственно работаем. Такой объект можно составить из матрицы смежности или с помощью списка ребёр.

M <- matrix(c(0,0,0,1,0,
              0,0,1,1,0,
              0,1,0,1,1,
              1,1,1,0,0,
              0,1,0,0,0),nrow = 5, ncol = 5)
print(M)
##      [,1] [,2] [,3] [,4] [,5]
## [1,]    0    0    0    1    0
## [2,]    0    0    1    1    1
## [3,]    0    1    0    1    0
## [4,]    1    1    1    0    0
## [5,]    0    0    1    0    0
g1 <- graph.adjacency(M, weighted = TRUE,mode = 'undirected')
print(g1)
## IGRAPH 167ecb0 U-W- 5 6 -- 
## + attr: weight (e/n)
## + edges from 167ecb0:
## [1] 1--4 2--3 2--4 2--5 3--4 3--5

Можно увидеть, что это объект пакета igraph. Сам граф содержит 5 вершин и 16 рёбер.

Аналогично, можно создать граф из списка рёбер. Важно, чтобы на входе подавалась матрица, не data frame. Также имеется параметр directed, отвечающий за ориентированность графа. Название вершин может быть и строковой переменной.

L <- data.frame(name1 = c("Jessie", "Jessie", "Sidney","Karl"),
                name2 = c("Sidney", "Britt", "Britt","Sidney"))
g2 <- graph.edgelist(as.matrix(L), directed = FALSE)

Изобразим оба графа!

plot(g1)

plot(g2)

Несколько полезных функций:

  • V(g) - список вершин
  • E(g) - список ребер
  • gsize(g) - количество ребер
  • gorder(g) - количество вершин
  • add_edges - добавление ребер
  • add_vertices - добавление вершин
V(g1)
## + 5/5 vertices, from 167ecb0:
## [1] 1 2 3 4 5
E(g1)
## + 6/6 edges from 167ecb0:
## [1] 1--4 2--3 2--4 2--5 3--4 3--5
gsize(g1)
## [1] 6
gorder(g1)
## [1] 5

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

vertex_attr(g2)
## $name
## [1] "Jessie" "Sidney" "Britt"  "Karl"

Еще одним атрибутом вершин может являться возраст. Давайте добавим этот атрибут.

g2 <- set_vertex_attr(g2, "age", value = c(16,20,40,25))
vertex_attr(g2)
## $name
## [1] "Jessie" "Sidney" "Britt"  "Karl"  
## 
## $age
## [1] 16 20 40 25

Главным атрибутом рёбер является вес ребра.

edge_attr(g1)
## $weight
## [1] 1 1 1 1 1 1

Но можно добавлять и другие атрибуты.

g1 <- set_edge_attr(g1, '1/weight', value = 1/ edge_attr(g1)$weight)

Можно просматривать вершины в удобном формате.

V(g2)[[]]
## + 4/4 vertices, named, from d64b294:
##     name age
## 1 Jessie  16
## 2 Sidney  20
## 3  Britt  40
## 4   Karl  25
V(g2)[[1,3]]
## + 2/4 vertices, named, from d64b294:
##     name age
## 1 Jessie  16
## 3  Britt  40

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

V <- data.frame(name = c('A', 'B', 'C', 'D', 'E'),
                value = c(20,25,10,19,30))
E <- data.frame(from = c('A','B','C','D'),
                to = c('B','C','D','A'),
                weight = c(1,2,3,4))
g3 <- graph_from_data_frame(d = E, vertices = V, directed = FALSE)
g3
## IGRAPH f9000b1 UNW- 5 4 -- 
## + attr: name (v/c), value (v/n), weight (e/n)
## + edges from f9000b1 (vertex names):
## [1] A--B B--C C--D A--D
vertex_attr(g3)
## $name
## [1] "A" "B" "C" "D" "E"
## 
## $value
## [1] 20 25 10 19 30
edge_attr(g3)
## $weight
## [1] 1 2 3 4

Можно выделять подграфы.

E(g3)[[inc('A')]]
## + 2/4 edges from f9000b1 (vertex names):
##   tail head tid hid weight
## 1    A    B   1   2      1
## 4    A    D   1   4      4
E(g3)[[weight>=3]]
## + 2/4 edges from f9000b1 (vertex names):
##   tail head tid hid weight
## 3    C    D   3   4      3
## 4    A    D   1   4      4

Одним из атрибутов вершин может быть их цвет.

V(g3)$color <- ifelse(V(g3)$value > 20, 'red', 'white')
plot(g3, vertex.label.color = "blue")

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

plot

Визуализация очень важна. Изучим некоторые опции, которые нам доступны.

  • vertex.color - цвет вершин
  • edge.color - цвет ребёр
  • label.color - цвет названий вершин
  • vertex.size - размер вершин
  • edge.width - размер рёбер
  • label.cex - размер названий вершин

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

  • layout - это способ рисовки графа. Различные способы представлены на картинке ниже.

Если не знаете, что выбрать, то можно поставить значение layout_nicely(стоит по умолчанию). Тогда график будет нарисован оптимально.

tkplot и graphjs

Обычный plot рисует статические графики, это бывает хорошо, когда граф большой. Если граф маленький или средний(если большой, то можно кластеризовать и посмотреть уже на кластеры), то можно нарисовать интерактивный граф. Функция tkplot встроена в пакет igraph. Вы можете запустить следующий код у себя в скрипте или консоли.

# tkplot(sample_k_regular(20,3), vertex.color = 'orange')

Там вы можете менять расположение ребер, менять цвет вершин и многое другое. Данная функция позволяет увидеть граф в 2D. Чтобы смотреть на графы в 3D можно использовать функцию graphjs, которая находится в пакете threejs.

# install.packages('threejs')
library('threejs')
graphjs(sample_k_regular(20,3))

Этот график построен на основе js, поэтому вы можете двигать его даже в онлайн скрипте.

Граф моих друзей в vk

Нам понадобятся некоторые пакеты, поэтом подгрузим их.

library('dplyr')
library('stringr')

Данные были выкачаны с помощью VK API через python.

data <- read.csv('edges.csv') %>% select(name_1, name_2)

Перед нами список рёбер. Создадим граф!

graph_vk <- graph.edgelist(as.matrix(data), directed = FALSE)
graph_vk
## IGRAPH 5431a99 UN-- 475 7394 -- 
## + attr: name (v/c)
## + edges from 5431a99 (vertex names):
##  [1] Зарманбетов Ахмед--Матросова Ксения    
##  [2] Зарманбетов Ахмед--Генералов Дмитрий   
##  [3] Зарманбетов Ахмед--Чухров Никита       
##  [4] Зарманбетов Ахмед--Емельянов Дмитрий   
##  [5] Зарманбетов Ахмед--Барышников Владислав
##  [6] Зарманбетов Ахмед--Ульянкин Филипп     
##  [7] Зарманбетов Ахмед--Бобылева Маша       
##  [8] Зарманбетов Ахмед--Маруева Катерина    
## + ... omitted several edges

Видим, что вершин 475, а ребер 7394. Максимальное количество ребер равно \(\frac{475(475+1)}{2} = 113050\).

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

V(graph_vk)$color = ifelse(V(graph_vk)$name == 'Зарманбетов Ахмед', 'red', 'orange')
plot(graph_vk)

Ничего не понятно, так как граф очень большой. Давайте уберем названия вершин.

plot(graph_vk, vertex.label = NA)

Сами вершины тоже очень большие, поэтому уменьшим их размер.

plot(graph_vk, vertex.label = NA, vertex.size = 3)

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

Можно увидеть, что имеется несколько кластеров:

  • кластер моих друзей и знакомых в Туле
  • кластер моих друзей и знакомых в Москве(в основом из Ранха)
  • кластер родственников

Но внутри второго кластера видно деление на мелкие кластеры(курсы:1,2,3,4).

Алгоритмы

В пакете реализовано много алгоритмов:

  • поиск в ширину - bfs
  • поиск в глубину - dfs
  • алгоритм Дейкстры - shortest_paths
  • и многие другие(в том числе различные кластеризации)