Визуализация статических и динамических сетей на R, часть 4

В первой части:

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

Во второй части: цвета и шрифты в графиках R.

В третьей части: параметры графов, вершин и ребер.

В этой части: размещения сети.

Размещения сети

Размещения сети — это алгоритмы, возвращающие координаты каждой вершины графа.
Для исследования размещений создадим немного больший граф, из 80 вершин. Используем функцию barabasi.game, которая генерирует простой граф, начинающийся с одной вершины и наращивающий вершины и ребра в зависимости от заданного уровня предпочтительного присоединения (сколько еще новых объектов предпочтут установить связь с более популярными вершинами в сети).

net.bg <- barabasi.game(80) 
V(net.bg)$frame.color <- "white"
V(net.bg)$color <- "orange"
V(net.bg)$label <- "" 
V(net.bg)$size <- 10
E(net.bg)$arrow.mode <- 0
plot(net.bg)

Можно задать размещение в функции построения:

plot(net.bg, layout=layout.random)

Или рассчитать координаты вершин заранее:

l <- layout.circle(net.bg)
plot(net.bg, layout=l)

l — матрица x- и y-координат (N x 2) для N вершин графа. Их можно легко задать самостоятельно:

l <- matrix(c(1:vcount(net.bg), c(1, vcount(net.bg):2)), vcount(net.bg), 2)
plot(net.bg, layout=l)

Это размещение — только пример, оно не слишком полезно. К счастью, в igraph есть набор встроенных размещений, включая такие:

# Случайно расположенные вершины
l <- layout.random(net.bg)
plot(net.bg, layout=l)

# Размещение по кругу
l <- layout.circle(net.bg)
plot(net.bg, layout=l)

# Размещение в виде 3D-сферы
l <- layout.sphere(net.bg)
plot(net.bg, layout=l)

Фрюхтерман-Рейнгольд — один из наиболее часто используемых силовых алгоритмов размещения.

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

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

Также можно использовать параметр «веса», который увеличивает силы притяжения между вершинами, связанными более тяжелыми ребрами.

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

Размещение fruchterman.reingold.grid аналогично fruchterman.reingold, но быстрее.

l <- layout.fruchterman.reingold(net.bg, repulserad=vcount(net.bg)^3, 
                                      area=vcount(net.bg)^2.4)
par(mfrow=c(1,2),  mar=c(0,0,0,0)) # построить два графика - 1 строка, 2 столбца
plot(net.bg, layout=layout.fruchterman.reingold)
plot(net.bg, layout=l)

dev.off() # выключить графику, чтобы очистить конфигурацию.

Другой популярный алгоритм силового размещения, показывающий хорошие результаты для связных графов — Камада-Каваи. Как и Фрюхтерман-Рейнгольд, его цель — минимизировать энергию в системе пружин. Igraph также содержит размещение на основе пружин, которое называется layout.spring().

l <- layout.kamada.kawai(net.bg)
plot(net.bg, layout=l)

l <- layout.spring(net.bg, mass=.5)
plot(net.bg, layout=l)

Алгоритм LGL (Large Graph Layout — размещение больших графов) предназначен для больших связных графов. Он также позволяет задать корень — вершину, которая будет располагаться в центре размещения.

plot(net.bg, layout=layout.lgl)

По умолчанию координаты графиков масштабируются до интервала [-1,1] как по х, так и по у. Это можно изменить с помощью параметра rescale=FALSE и масштабировать график вручную, умножая координаты на число. Функция layout.norm позволяет нормализовать график по желаемым границам.

l <- layout.fruchterman.reingold(net.bg)
l <- layout.norm(l, ymin=-1, ymax=1, xmin=-1, xmax=1)

par(mfrow=c(2,2), mar=c(0,0,0,0))
plot(net.bg, rescale=F, layout=l*0.4)
plot(net.bg, rescale=F, layout=l*0.6)
plot(net.bg, rescale=F, layout=l*0.8)
plot(net.bg, rescale=F, layout=l*1.0)

dev.off()

По умолчанию igraph использует размещение layout.auto. Он автоматически подбирает необходимый алгоритм размещения на основании свойств графа (размеру и связности).

Давайте посмотрим на размещения, доступные в igraph:

layouts <- grep("^layout\\.", ls("package:igraph"), value=TRUE) 
# Убрать размещения, не подходящие для нашего графа.
layouts <- layouts[!grepl("bipartite|merge|norm|sugiyama", layouts)]

par(mfrow=c(3,3))

for (layout in layouts) {
  print(layout)
  l <- do.call(layout, list(net)) 
  plot(net, edge.arrow.mode=0, layout=l, main=layout) }

dev.off()