Что такое сеть?
Сеть (граф) — это модель любых объектов, имеющих связи друг с другом. Например, можно построить граф дружбы, можно — граф международной торговли или перелётов между аэропортами, а можно — граф взаимодействия вымышленных персонажей в пьесе. Объекты, образующие сеть, называются вершинами, или узлами, связи между ними обозначают, как рёбра, или дуги. Ниже представлена сеть персонажей пьесы «Скупой рыцарь» А. С. Пушкина.
Элементы сети на примере взаимосвязей между персонажами пьесы А. С. Пушкина «Скупой рыцарь»
Рёбра возникают, когда объекты сети взаимодействуют друг с другом. Например, когда два персонажа пьесы появляются в одной сцене и произносят хотя бы одну реплику. Рёбра могут иметь направление, если взаимодействие одностороннее.
Степень (degree) вершины графа
Степень вершины показывает количество её связей с другими объектами графа. Например, в сети на основе литературного произведения степень узла покажет, со сколькими персонажами взаимодействует герой на протяжении всего действия. На этой визуализации социальной сети пьесы «Горе от ума» красным цветом подписаны персонажи, имеющие степень 2 или 3 (т. е. успевшие по ходу пьесы пообщаться лишь с двумя или тремя другими героями). Видно, что это в основном слуги.
Сеть персонажей комедии А. С. Грибоедова «Горе от ума»
Взвешенная степень (weighted degree, strength)
Взвешенная степень — это расширенная версия обычной степени. Она учитывает не только количество соседних вершин, но также вес рёбер. Вес может показывать, например, время от одного населённого пункта до другого или сумму денег, взятую в долг (но тогда ребро должно быть направленным, чтобы показать, кто кому должен).
В соцсетях пьес веса связей показывают, сколько раз персонажи общаются друг с другом в течение всего произведения. Другими словами, взвешенная степень учитывает количество взаимодействий между двумя персонажами. На картинке выше веса рёбер отображены через толщину: видно, например, что Чацкий очень много говорит с Софьей, а сама Софья — со своей служанкой Лизанькой. Взвешенная степень каждого персонажа равна сумме всех его взаимодействий с другими действующими лицами.
Эта метрика позволяет легко определить персонажа, который больше всего взаимодействует с другими персонажами, а не только имеет больше знакомств, в отличие от обычной степени. Например, в пьесе И. А. Крылова «Филомела», Прогнея — персонаж с наибольшей взвешенной степенью, но на самом деле Терей больше связан с остальными действующими лицами и по другим метрикам он также лидирует.
Взвешенная степень и степень для сети пьесы И. С. Крылова «Филомела»
Степень близости (Closeness centrality)
Эта характеристика показывает, насколько легко попасть из определённой вершины в другие узлы сети. Чем показатель выше, чем ближе узел ко всем другим узлам.
Общая формула для расчета степени близости выглядит так:
где d(vj, vk) — длина минимального пути между vj и vk.
В пьесах эта метрика может означать, напрямую ли взаимодействуют с этим персонажем или нет. Например, в пьесе А. Н. Островского «Лес» персонаж Аксюша имеет невысокую взвешенную степень, но наибольшую степень близости. По сюжету она находится в зависимом положении, в первую очередь от Гурмыжской (которая имеет наибольшую взвешенную степень), и это может означать, что остальные персонажи взаимодействуют с ней напрямую, так как могут себе это позволить.
Степень близости и взвешенная степень персонажей пьесы А. Н. Островского «Лес»
Степень посредничества (Betweenness centrality)
Степень посредничества показывает, насколько связующим является узел, и определяется как сумма вероятностей встретить данную вершину в кратчайшем пути между двумя другими. Чем выше степень посредничества, тем больше информации проходит через узел.
Формула для расчёта этого показателя выглядит так:
где bij(vk) — это вероятность наличия вершины vk в кратчайшем пути между вершинами vi и vj.
При сетевом анализе пьесы можно сказать, что степень посредничества персонажа показывает вероятность того, что два других героя связаны через него. Эта характеристика помогает определять, кто в сети является посредниками при передаче информации от одной группы к другой.
Хороший пример персонажа с высокой степенью посредничества в корпусе русской драмы — второстепенный персонаж Гаврила Пушкин из пьесы «Борис Годунов» А. С. Пушкина. Наибольшая степень посредничества в этой сети у самозванца Григория Отрепьева, но сразу за ним идёт сравнительно малозаметный по ходу пьесы Гаврила Пушкин. По сюжету он является связующим персонажем между приближёнными Бориса и Григорием. При прочтении легко не заметить важность этого персонажа, однако на визуализации сети хорошо видно, что Гаврила соединяет два кластера — персонажей в Москве и в Польше. И действительно: он ездит между странами со своего рода дипломатическими миссиями, когда будущий Лжедмитрий и царь Борис ещё пытаются решить дело миром, затем он же подговаривает лучшего воеводу Годунова — Басманова — перейти на сторону самозванца; в конце пьесы именно Гаврила Пушкин идет зачитывать первые указы нового царя народу (который в пьесе является вполне самостоятельным персонажем, имеет свои реплики и образует третий большой кластер).
Гаврила Пушкин и сеть персонажей исторической драмы «Борис Годунов»
Степень влиятельности (Eigenvector centrality)
Степень влиятельности показывает важность узла, учитывая значимость других узлов, с которыми он взаимодействует. В пьесах эта метрика позволяет разделить действующих лиц на «центральных» и «периферийных». Персонажи более значимы, если они взаимодействуют с персонажами важнее себя, и теряют свою значимость при контакте с менее важными действующими лицами.
Эта метрика определяется немного сложнее, чем предыдущие, но если вас не пугает небольшая порция линейной алгебры, то следующие несколько абзацев для вас.
Сеть может быть представлена не только в виде графа, но и в виде матрицы. Такая матрица называется матрицей смежности, поскольку её элементы показывают, смежны ли вершины друг с другом. Например, составим матрицу смежности для уже упоминавшейся пьесы «Скупой рыцарь».
Сетевой граф и матрица смежности для «Скупого рыцаря»
Итоговую матрицу обозначим А:
Единицами отмечено наличие рёбер между персонажами, а нулями ― их отсутствие. Вместо единиц в матрице могут быть указаны веса рёбер, и тогда уже матрица будет взвешенной. Заметим, что получившаяся матрица является симметричной.
У таких матриц есть важное свойство — наличие собственных векторов, то есть таких, произведение которых на матрицу эквивалентно произведению числа на этот вектор. Формула записывается так:
где А — это матрица смежности;
λ — действительное число;
СE — собственный вектор матрицы А.
Элементы вектора СE и являются степенями влиятельности для каждой вершины. Если определить вектор СE как
где С_E(v_i) — это степень влиятельности вершины v_i;
то предыдущее равенство можно переписать в линейном виде для отдельной вершины:
где СE(vi) — это степень влиятельности вершины vi;
aij — элемент матрицы A, расположенный в i-й строке и j-м столбце.
В такой записи лучше видно, что на степень влиятельности вершины vi влияют значения всех остальных вершин.
В пьесе И. Е. Бабеля «Мария» Катя имеет наибольшее значение степени влиятельности, и все персонажи, которые связаны с ней, имеют большие показатели, чем те, кто не взаимодействует с Катей напрямую. Те герои, которые взаимодействуют только с Катей (Агаша, Кузьма, Нюша и др.), имеют более высокую степень влиятельности, чем большинство персонажей из другой части графа.
Сеть персонажей пьесы И. Е. Бабеля «Мария»
Это всё?
Кроме перечисленных мер существует ещё много других полезных и более сложных характеристик, таких как PageRank (её когда-то придумали основатели Google для ранжирования страниц в интернете), центральность узла по Кацу и другие. Тем не менее пять описанных нами метрик являются основными для сетевого анализа. Чтобы узнать, как сетевой анализ применяется на практике, почитайте наши материалы о сетях родства европейских монархов накануне Первой мировой войны, о разнице между трагедиями и комедиями, о сетях переписки в Англии,по которым вычисляли шпионов, о сетевом анализе «Войны и мира», а ещё об исследовании византийских писем.