Граф – это математический объект, и в этом уроке речь пойдет о том, как можно его описывать и анализировать. Данные для этого урока происходят из корпуса Dracor.
DraCor — сокращение от drama corpora — это собрание размеченных по стандарту TEI драматических текстов. Здесь есть пьесы на французском, немецком, испанском, русском, итальянском, шведском, португальском (только Кальдерон) и английском (только Шекспир), а также совсем небольшие коллекции эльзасских, татарских и башкирских пьес.
Два крупных корпуса пьес в составе собрания — немецкий и русский — были собраны и поддерживаются создателями проекта DraCor. Остальные корпуса были взяты из сторонних проектов, а затем адаптированы для совместимости с функционалом DraCor. Подробнее об этом можно прочитать здесь.
На сайте проекта “Системный Блокъ” можно прочитать серию материалов о том, как возможности Dracor используются в литературоведении:
# remotes::install_github("Pozdniakov/rdracor")
library(rdracor)
library(tidyverse)
library(igraph)
get_dracor_meta() |>
summary()DraCor hosts 21 corpora comprising 4210 plays.
The last updated corpus was German Drama Corpus (2024-10-09 06:16:59.279).Извлекаем метаданные.
meta <- get_dracor_meta() |>
select(name, title, plays)
metameta |>
plot()
rus <- get_dracor("rus")
summary(rus)212 plays in Russian Drama Corpus
Corpus id: rus, repository: https://github.com/dracor-org/rusdracor
Description: Edited by Frank Fischer and Daniil Skorinkin. Features more than 200 Russian plays from the 1740s to the 1940s. For a corpus description and full credits please see the [README on GitHub](https://github.com/dracor-org/rusdracor).
Written years (range): 1747–1940
Premiere years (range): 1750–1992
Years of the first printing (range): 1747–1986rus <- as_tibble(rus)
rusТут хранится очень много всего: размер сети, плотность сети и т.д. Вот так, например, выглядят самые длинные пьесы в корпусе:
rus |>
arrange(-wordCountText) |>
select(firstAuthorName, title, wordCountText)А так – самые густонаселенные.
rus |>
arrange(-size) |>
select(firstAuthorName, title, size)Подробнее см. презентацию Ивана Позднякова, разработчика DraCor Shiny App (https://shiny.dracor.org/).
Извлекаем граф для “Бориса Годунова”.
godunov <- get_net_cooccur_igraph(play = "pushkin-boris-godunov", corpus = "rus")
godunovIGRAPH 3ca5aac UNW- 79 327 --
+ attr: name (v/c), isGroup (v/l), gender (v/c), numOfScenes (v/n),
| numOfSpeechActs (v/n), numOfWords (v/n), degree (v/n), weightedDegree
| (v/n), closeness (v/n), betweenness (v/n), eigenvector (v/n),
| wikidataId (v/c), weight (e/n)
+ edges from 3ca5aac (vertex names):
[1] Воротынский--Шуйский
[2] Воротынский--Борис
[3] Воротынский--Бояре
[4] Шуйский --Борис
[5] Шуйский --Бояре
+ ... omitted several edgesПомимо уже знакомых нам атрибутов вроде имени (name (v/c)), гендера (gender (v/c)) и степени (degree(v/n)), мы видим здесь много новой информации. Некоторые атрибуты интуитивно понятны: является ли персонаж групповым (isGroup (v/l)); в каком часле явлений он участвует (numOfScenes (v/n)); сколько у него реплик (numOfSpeechActs (v/n)) и слов (numOfWords (v/n)).
Атрибут wikidataId (v/c) представлен лишь для исторических лиц, например, для самого Годунова.
tibble(name = V(godunov)$name,
isGroup = V(godunov)$isGroup,
numOfScenes = V(godunov)$numOfScenes,
numOfSpeechActs = V(godunov)$numOfSpeechActs,
numOfWords = V(godunov)$numOfWords) |>
arrange(-numOfScenes)Эта информация заботливо собрана создателями Dracor’а, но при желании ее можно проверить: функция get_text_df() дает возможность извлечь текст пьесы в виде датафрейма. Убедимся, например, что Григорий появляется в 8 сценах.
godunov_df <- get_text_df(play = "pushkin-boris-godunov", corpus = "rus")
godunov_dfgodunov_df |>
filter(who == "grigorij_dimitrij_lzhedimitrij_samozvanets") |>
count(scene_id)Нам осталось разобраться с такими атрибутами, как weightedDegree (v/n), closeness (v/n), betweenness (v/n), eigenvector (v/n), weight (e/n). Начнем с последнего.
Веса ребер, как следует из технической документации к пакету, хранят информацию о том, сколько раз персонажи вместе появляются на сцене.
E(godunov)[weight > 1] + 9/327 edges from 3ca5aac (vertex names):
[1] Воротынский--Шуйский Шуйский --Борис
[3] Борис --Бояре Борис --Феодор
[5] Борис --Басманов Григорий --Гаврила Пушкин
[7] Григорий --Курбский Григорий --Ляхи
[9] Ксения --Феодор Эти сведения можно извлечь и при помощи специальной функции.
cooc_dracor <- get_net_cooccur_edges(play = "pushkin-boris-godunov", corpus = "rus")
cooc_dracor |>
filter(Weight > 1) |>
arrange(-Weight)Важность (prominence) участника (актора, вершины, узла) определяется его положением внутри сети. Применительно к ненаправленным сетям говорят о центральности (центральный актор вовлечен в наибольшее количество связей, прямых или косвенных), а применительно к направленным – о престиже. Престижный актор характеризуется большим количеством входящих связей.
Мы уже умеем считать центральность по степени (degree centrality), которая определяется количеством связей: чем больше прямых связей, тем более важным является узел.
degrees <- degree(godunov)
sort(degrees, decreasing = T)[1:10] Борис Народ Григорий Феодор Бояре
29 26 25 23 21
Басманов Ксения Шуйский Гаврила Пушкин Ляхи
15 14 13 11 10 # проверка
# V(godunov)$degree == degreesС понятием веса ребра тесно связана взвешенная центральность по степени (weightedDegree(v/n)). В отличие от простой центральности, она учитывает вес связанных с узлом ребер.
wDegree <- strength(godunov)
# проверка
tibble(wd_old = V(godunov)$weightedDegree,
wd_new = wDegree) |>
arrange(-wd_old)Вот так, например, считается взвешенная центральность для Бориса Годунова:
# ребра, связанные с Годуновым
idx <- incident(godunov, "Борис")
# суммарный вес ребер
sum(E(godunov)[idx]$weight)[1] 35На графе веса ребер можно отразить за счет толщины и (или) прозрачности линии, а взвешенную центральность - за счет размера узла
library(ggraph)
library(paletteer)
cols <- paletteer_d("nbapalettes::hawks_statement")
set.seed(22092024)
ggraph(godunov, layout = "kk", maxiter = 500) +
# здесь кодируем вес ребер
geom_edge_link(aes(alpha = weight),
color = cols[3],
width = 0.8,
show.legend = FALSE) +
# здесь взвешенная центральность
geom_node_point(aes(size = weightedDegree),
color = cols[2],
show.legend = FALSE) +
# обратите внимание на фильтр!
geom_node_text(aes(filter = (weightedDegree > 10 | name %in% c("Курбский", "Воротынский")),
label = name),
color = cols[1],
repel = TRUE) +
theme_graph()
Центральность по близости (closeness centrality) говорит о том, насколько близко узел расположен к другим узлам сети. Центральность по близости – это величина, обратная сумме расстояний от узла i до всех остальных узлов сети.
\[\frac{1}{\sum_{i\neq v}d_{vi}}\]
Обратите внимание: в Dracor все метрики рассчитывались с использованием Python-пакета networkX. Имплементации расчетов сетевых метрик могут не совпадать.
close_new <- closeness(godunov,
mode = "all",
normalized = TRUE)
# похожие значения хранятся как атрибуты узлов
tibble(name = V(godunov)$name,
close_old = V(godunov)$closeness,
close_new = close_new) |>
arrange(-close_old)В пьесах эта метрика может означать, напрямую ли взаимодействуют с этим персонажем или нет. Например, в пьесе А. Н. Островского «Лес» персонаж Аксюша имеет невысокую взвешенную степень, но наибольшую степень близости. По сюжету, она находится в зависимом положении, в первую очередь от Гурмыжской (которая имеет наибольшую взвешенную степень), и это может означать что остальные персонажи взаимодействуют с ней напрямую, так как могут себе это позволить. – Источник.
На графе закодируем этот атрибут цветом; температурную шкалу установим вручную.
set.seed(22092024)
ggraph(godunov, layout = "kk", maxiter = 500) +
geom_edge_link(aes(alpha = weight),
color = cols[3],
width = 0.8,
show.legend = FALSE) +
geom_node_point(aes(size = weightedDegree,
# тут новое
color = closeness),
show.legend = FALSE) +
geom_node_text(aes(filter = (weightedDegree > 10 | name %in% c("Курбский", "Воротынский")),
label = name),
color = cols[3],
repel = TRUE) +
# градиентная шкала для closeness
scale_color_gradient(low = "plum", high = "purple") +
theme_graph()
Центральность по посредничеству (betweenness centrality) характеризует, насколько важную роль данный узел играет на пути “между” парами других узлов сети.
betweenness_new <- betweenness(godunov,
directed = FALSE,
normalized = TRUE)
tibble(name = V(godunov)$name,
b_old = round(V(godunov)$betweenness, 4),
b_new = round(betweenness_new, 4)) |>
arrange(-b_old)Хороший пример персонажа с высокой степенью посредничества в корпусе русской драмы — второстепенный персонаж Гаврила Пушкин из пьесы «Борис Годунов» А.С. Пушкина. …По сюжету, он является связующим персонажем между приближёнными Бориса и Григорием. При прочтении легко не заметить важность этого персонажа, однако на визуализации сети пьесы хорошо видно, что Гаврила связывает два кластера — персонажей в Москве и в Польше. – Источник.
Степень влиятельности (eigenvector centrality) показывает важность персонажа, учитывая влиятельность персонажей, с которыми взаимодействует данный персонаж. В пьесах эта метрика позволяет разделить действующих лиц на «центральных» и «периферийных».
Персонажи более значимы, если они взаимодействуют с персонажами важнее себя, и теряют свою значимость при контакте с менее важными действующими лицами. – Источник.
Чтобы посчитать eigenvector centrality, необходимо преобразовать граф в матрицу смежности (социоматрицу), в которой единицами отмечено наличие рёбер между персонажами, а нулями – их отсутствие. Вместо единиц в матрице могут быть указаны веса рёбер; в таком случае матрица будет взвешенной.
У таких матриц есть собственные векторы, то есть такие векторы, произведение которых на матрицу эквивалентно произведению числа на этот вектор.
\[\lambda \cdot C_e = A \cdot C_e,\] где
Элементы вектора \(C_e\) являются степенями влиятельности для каждой вершины. Это можно переписать для отдельных вершин так:
\[C_e(v_i)=\frac{1}{\lambda}\sum_{j=1}^{n}a_{ij} C_e(v_j),\] где
В такой записи видно, что на степень влиятельности вершины \(v_i\) влияют значения всех остальных вершин. Алгоритм расчета eigenvector centrality в последних версиях igraph немного отличается.
eigen_new <- eigen_centrality(godunov, scale = FALSE)$vector
tibble(name = V(godunov)$name,
eigen_old = V(godunov)$eigenvector,
eigen_new = eigen_new) |>
arrange(-eigen_old)Теперь мы понимаем смысл всех атрибутов в графах Dracor, и можем перейти к характеристике графа в целом.
Рассмотрим два крайних случая: круговой граф и звездчатый граф.
star_g <- make_star(5, mode = "undirected")
circle_g <- make_ring(5)
par(mfrow = c(1, 2))
plot(circle_g, vertex.color=2)
plot(star_g, vertex.color=3)
В случае звездчатого графа централизация максимальна, а для отдельных узлов наблюдается разброс центральности.
centr_clo(star_g)$res
[1] 1.0000000 0.5714286 0.5714286 0.5714286 0.5714286
$centralization
[1] 1
$theoretical_max
[1] 1.714286Во втором случае наборот – разброса нет, а для графа в целом централизация минимальна.
centr_clo(circle_g)$res
[1] 0.6666667 0.6666667 0.6666667 0.6666667 0.6666667
$centralization
[1] 0
$theoretical_max
[1] 1.714286Расчитаем централизацию для графа “Годунова”.
centr_clo(godunov)$centralization[1] 0.3050424Но в наших данных она уже рассчитана.
summary(godunov)rus: pushkin-boris-godunov - co-ocurence network summary
Пушкин, Александр Сергеевич: Борис Годунов (1831)
Size: 79 (9 FEMALES, 69 MALES, 1 UNKNOWN)
Density: 0.11
Degree:
- Maximum: 29 (Борис)
Distance:
- Maximum (Diameter): 7
- Average: 3.45
Clustering:
- Global: 0.65
- Average local: 0.92
Cohesion: 1
Assortativity: -0.06Точка сочленения – это узел, при удалении которого увеличивается число компонент связности. Таким образом, они соединяют разные части сети. При их удалении акторы (узлы, вершины) не могут взаимодействовать друг с другом.
articulation_points(godunov)+ 7/79 vertices, named, from 3ca5aac:
[1] Народ Патриарх Григорий Марина Гаврила Пушкин
[6] Борис Шуйский Точки сочленения тесто связаны с центральностью по посредничеству.
V(godunov)[betweenness > 0.025]+ 10/79 vertices, named, from 3ca5aac:
[1] Шуйский Народ Борис Бояре Григорий
[6] Патриарх Феодор Гаврила Пушкин Марина Басманов Многие сети состоят из относительно плотных подгрупп, которые соединены между собой менее крепкими связями. Один из способов взглянуть на подгруппы сети заключается в исследовании социальной сплочености (cohesion). Сплоченные подгруппы - это множество акторов, которые объединены между собой посредством многочисленных, сильных и прямых связей.
Клика – один из самых простых типов сплоченных подгрупп; это максимально полный подграф, т.е. подмножество узлов со всеми возможными связями между ними. Вопреки своему названию, функция clique_num() возвращает размер наибольшей клики:
clique_num(godunov)[1] 11На самом деле таких клик даже три. Узнаем, кто туда входит.
cliques(godunov, min=11)[[1]]
+ 11/79 vertices, named, from 3ca5aac:
[1] Народ Ксения Феодор
[4] Нищий Стража Один из народа (Кремль)
[7] Другой (Кремль) Один из народа (Кремль) Другой (Кремль)
[10] Третий (Кремль) Мосальский
[[2]]
+ 11/79 vertices, named, from 3ca5aac:
[1] Борис Бояре Феодор Басманов Боярин Один Другой
[8] Третий Четвертый Пятый Шестой
[[3]]
+ 11/79 vertices, named, from 3ca5aac:
[1] Народ
[2] Борис
[3] Бояре
[4] Один из народа (Площадь перед собором в Москве)
[5] Другой (Площадь перед собором в Москве)
[6] Третий (Площадь перед собором в Москве)
[7] Четвертый (Площадь перед собором в Москве)
[8] Мальчишки
[9] Старуха
[10] Юродивый
+ ... omitted several verticesИли, что то же самое:
largest_cliques(godunov)Но клика – это очень строгое определение сплоченной группы. Например, чтобы подграф, состоящий из 11 вершин, считался кликой, нужно, чтобы между ними было проведено \((11 \times 10) / 2 = 21\) связей. Если хотя бы одно ребро отсутствует, то условие не выполняется. Такие клики просто очень редко встречаются.
Популярным определением социальной сплоченности является k-ядро (k-core). Это максимальный подграф, в котором каждая вершина связана минимум с k другими вершинами этого же подграфа. K-ядра имеют множество преимуществ:
Выражение 6-ядро читают как “ядро степени 6”.
Ядро степени k+1 является подграфом ядра степени k. Любой узел в ядре степени k имеет степень либо k, либо выше. При этом coreness узла определяется по ядру с наибольшей степенью, к которому они принадлежат.
Для определения k-ядерной структуры используется функция graph.coreness():
cores_godunov <- coreness(godunov)
head(cores_godunov) Воротынский Шуйский Один (Красная площадь)
3 5 4
Другой (Красная площадь) Третий (Красная площадь) Народ
4 4 10 Посчитаем количество вершин в ядрах.
table(cores_godunov)cores_godunov
1 2 3 4 5 7 10
2 6 1 7 11 23 29 Для лучшей интерпретации k-ядерной структуры мы можем графически изобразить сеть, используя информацию о множестве k-ядер. Для начала добавим информацию о цвете к атрибутам узлов.
V(godunov)$core <- cores_godunov
# убедимся, что добавился новый атрибут
names(vertex_attr(godunov)) [1] "name" "isGroup" "gender" "numOfScenes"
[5] "numOfSpeechActs" "numOfWords" "degree" "weightedDegree"
[9] "closeness" "betweenness" "eigenvector" "wikidataId"
[13] "core" set.seed(22092024)
ggraph(godunov, layout = "kk", maxiter = 500) +
geom_edge_link(color = cols[3],
alpha = 0.3,
width = 0.6) +
# тут новое
geom_node_point(aes(color = as.factor(core)),
size = 3,
show.legend = TRUE) +
# новый фильтр
geom_node_text(aes(filter = degree > 10,
label = name),
color = cols[3],
repel = TRUE) +
scale_color_brewer("k-ядра", type = "qual") +
theme_void()
Чтобы глубже исследовать подгруппы, последовательно удаляют k-ядра более низкой степени. Для этого можно воспользоваться функцией induced_subgraph().
godunov5_10 <- induced_subgraph(godunov, vids=V(godunov)[core > 4])
ggraph(godunov5_10, layout = "kk", maxiter = 500) +
geom_edge_link(color = cols[3],
alpha = 0.3,
width = 0.6) +
geom_node_point(aes(color = as.factor(core)),
size = 3,
show.legend = TRUE) +
geom_node_text(aes(filter = degree > 10,
label = name),
color = cols[3],
repel = TRUE) +
scale_color_brewer("k-ядра", type = "qual") +
theme_void()
При интерпретации важно помнить, что ядра являются вложенными. Чем выше степень ядра, тем больше узлы связаны между собой.
Модулярность — одна из мер структуры сетей или графов. Мера была разработана для измерения силы разбиения сети на модули (называемые группами, кластерами или сообществами). Сети с высокой модулярностью имеют плотные связи между узлами внутри модулей, но слабые связи между узлами в различных модулях.
Модулярность равна доле рёбер от общего числа рёбер, которые попадают в данные группы, минус ожидаемая доля рёбер, которые попали бы в те же группы, если бы они были распределены случайно.
Если все узлы принадлежат к одному классу, то модулярность равна нулю. Если разбиение на классы хорошее, то модулярность должна быть высокая. Мы можем проверить, хорошо ли группируются персонажи по гендеру. Для этого перекодируем гендер, так как функция modularity() принимает числовую переменную в качестве аргумента. Значение гендера 3 (unknown) в пьесе имеют групповые персонажи.
V(godunov)$gender [1] "MALE" "MALE" "MALE" "MALE" "MALE" "UNKNOWN" "MALE"
[8] "MALE" "MALE" "MALE" "MALE" "MALE" "MALE" "MALE"
[15] "MALE" "FEMALE" "MALE" "MALE" "MALE" "MALE" "MALE"
[22] "MALE" "FEMALE" "FEMALE" "MALE" "MALE" "MALE" "MALE"
[29] "MALE" "MALE" "MALE" "MALE" "MALE" "MALE" "MALE"
[36] "FEMALE" "MALE" "FEMALE" "FEMALE" "FEMALE" "MALE" "MALE"
[43] "MALE" "MALE" "MALE" "FEMALE" "MALE" "MALE" "MALE"
[50] "MALE" "MALE" "MALE" "MALE" "MALE" "MALE" "MALE"
[57] "FEMALE" "MALE" "MALE" "MALE" "MALE" "MALE" "MALE"
[64] "MALE" "MALE" "MALE" "MALE" "MALE" "MALE" "MALE"
[71] "MALE" "MALE" "MALE" "MALE" "MALE" "MALE" "MALE"
[78] "MALE" "MALE" ## male = 1
idx <- V(godunov)$gender=="MALE"
V(godunov)$gender[idx] <- 1
## female = 2
idx <- V(godunov)$gender=="FEMALE"
V(godunov)$gender[idx] <- 2
## unknown = 3
idx <- V(godunov)$gender=="UNKNOWN"
V(godunov)$gender[idx] <- 3gender <- as.numeric(V(godunov)$gender)
modularity(godunov, gender)[1] 0.01434597При выделении сообществ в большинстве случаев наша задача – максимизировать модулярность.
Очевидно, что гендер не лучшим образом описывает деление персонажей “Годунова” на группы. Поищем другие сообщества.
В пакете igraph реализовано множество алгоритмов обнаружения сообществ. Обычной практикой является применение нескольких алгоритмов и сравнение результатов.
У нас ненаправленная взвешенная сеть. Применим алгоритм “случайного блуждания”.
cw <- cluster_walktrap(godunov)
membership(cw) |> head() Воротынский Шуйский Один (Красная площадь)
2 2 9
Другой (Красная площадь) Третий (Красная площадь) Народ
9 9 2 par(mar = rep(0, 4))
plot(cw, godunov)
Значение модулярности достаточно высокое (уж точно лучше, чем гендер).
modularity(cw)[1] 0.5639771Поищем другое разбиение.
csg <- cluster_spinglass(godunov)
membership(csg) |> head() Воротынский Шуйский Один (Красная площадь)
6 6 2
Другой (Красная площадь) Третий (Красная площадь) Народ
2 2 2 par(mar = rep(0, 4))
plot(csg, godunov)
Показатели модулярности чуть выше, чем для предыдущего разбиения.
modularity(csg)[1] 0.6128681Также используем алгоритм под названием “главный собственный вектор”.
cev <- cluster_leading_eigen(godunov)
modularity(cev)[1] 0.617586par(mar = rep(0, 4))
plot(cev, godunov)