Как найти минимальный разрез графа

Поточная сеть — Теория графов

В этом уроке мы разберем, что такое поточная сеть. Вы узнаете, как строятся такие сети и как диграфы помогают в этом.

Как строится поточная сеть

Представим, что у нас есть диграф и две вершины — источник и сток. У каждого ребра есть вес, который называется его пропускной способностью. Нам нужно пропустить как можно больше материала через диграф от источника к стоку. Это называется потоком, а взвешенный диграф — сетью. Таким образом мы строим сетевой поток.

Например, источник — это

Первое число, выделенное красным на каждом ребре — это значение потока, а второе — пропускная способность. В этом случае поток не оптимальный, так как через сеть можно пропустить больше вещей, чем

Количество потока на ребре не может превышать его пропускную способность. Еще общее количество потока в вершину должно быть равно общему количеству потока из этой вершины, за исключением источника и стока. В итоге поток проходит через вершины, которые не создают и не потребляют поток.

Общее объем потока, который проходит через сеть, называется величиной потока. Это количество можно найти, если посчитать:

Общий поток, который выходит из источника

Общий поток, который входит в сток

Многие реальные проблемы можно смоделировать с помощью сетей потоков. Например, источник — это место, где мы добываем сырье. Его нужно доставить на завод — сток. Края — это различные маршруты, по которым мы можем отправить сырье, а мощность — сколько материала можно доставить по этим маршрутам.

Если предположить, что транспортная сеть — это ограничивающий фактор, то нас интересует, сколько сырья мы можем доставить на фабрику.

Многие несвязанные проблемы теории графов можно преобразовать в проблемы сетевых потоков.

Теорема о максимальном потоке и минимальном разрезе

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

Найти максимальный поток и минимальный разрез в графе, продемонстрировав работу алгоритма Форда-Фалкерсона

Н айдем путь, по которому можно увеличить поток и увеличим поток

Е сть еще один путь, по которому можно увеличить поток

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

с ледующий граф. Цветом выделены все вершины в которых можно получить избыточный поток. Все ребра, соединяющие помеченные и непомеченные вершины входят в минимальный разрез. Размер разреза равен размеру потока и они равны 25.

Алгоритм Каргера для нахождения минимального разреза

Алгоритм Каргера (англ. Karger’s algorithm) — рандомизированный алгоритм для нахождения минимального разреза в связном графе. Он был разработан Дэвидом Каргером (англ. David Karger) в 1993 году.

Содержание

Основные определения

Пусть [math]G[/math] — неориентированный мультиграф с множеством вершин [math]V[/math] и множеством ребер [math]E[/math] , и [math]|V| = n[/math] , [math]|E| = m[/math] .

Определение:

Мультивершиной (англ. supervertex) называется вершина, полученная из двух вершин стягиванием ребра между ними, каждая из которых, в свою очередь, может быть также мультивершиной.

Определение:

Стянутым графом (англ. contracted graph) называется граф, состоящий из двух мультивершин или одной мультивершины и одной обычной вершины (которую, чтобы избежать оговорок в дальнейшем, также будем называть мультивершиной), полученный из исходного графа последовательным стягиванием произвольных ребер.

Такой разрез часто называют также глобальным разрезом, чтобы отличать его от [math](s,t)[/math] -разреза.

Задача поиска разреза минимальной веса (англ. min-cut problem) заключается в поиске разреза минимального веса среди всех возможных разрезов исходного графа. Эту задачу можно решить с помощью любого из алгоритмов поиска максимального потока, зафиксировав произвольную вершину [math]s[/math] в качестве истока и запуская его [math]O(n)[/math] раз для всех возможных стоков. Если использовать быстрый алгоритм поиска максимального потока, работающий за [math]O(mn)[/math] , то время работы такого алгоритма поиска минимального разреза будет [math]O(n^2m)[/math] . Ниже описан более простой в реализации и сравнимый по скорости алгоритм Каргера. При некоторых оптимизациях, этот алгоритм работает значительно быстрее, чем использование алгоритмов поиска максимального потока.

Алгоритм

Пусть нам дан граф [math]G = \[/math] .

Так как алгоритм вероятностный и функция [math]\mathrm[/math] возвращает вес случайного потока, а не минимального, то для того, чтобы наверняка найти вес минимального, необходим вызвать эту функцию [math]count[/math] раз. Какое конкретное значение [math]count[/math] выбрать будет описано ниже. Реализация функции [math]\mathrm[/math] — это и есть основа алгоритма. Будем действовать следующим образом: пока вершин больше двух, будем выбирать случайное ребро и стягивать его. Когда в графе останется две вершины, то количество ребер между этими вершинами будет равно весу некоторого разреза исходного графа.

Корректность алгоритма

Докажем корректность алгоритма. Для удобства доказательства и оценок вероятностей, будем считать, что мы ищем не просто вес минимального разреза, а величину конкретного минимального разреза. То есть зафиксируем какой-то один из минимальных разрезов, и если функция [math]\mathrm[/math] вернет правильный вес, но посчитает его на другом минимальном разрезе, то будем считать, что ответ получен неверный. Это условие не ухудшает оценки вероятностей и время работы алгоритма.

Необходимость. От противного. Если некоторое ребро [math]uv[/math] , принадлежащее разрезу [math]\langle A, B \rangle[/math] в [math]G[/math] будет стянуто, то обе вершины [math]u[/math] и [math]v[/math] будут принадлежать одной мультивершине, а значит [math]G'[/math] не соответствует разрезу [math]\langle A, B \rangle[/math] . Противоречие.

По лемме 4 искомый стянутый граф будет получен тогда и только тогда, когда ни одно из ребер разреза не будет стянуто. Так как на каждой итерации алгоритма мы случайно выбираем ребро для стягивания, то можно оценить вероятность того, что ни одно из ребер разреза не будет стянуто. Каждое стягивание уменьшает количество ребер на [math]1[/math] . Таким образом после [math]i[/math] -ой итерации алгоритма количество вершин в текущем графе будет равно [math]n — i + 1[/math] . Рассчитаем вероятность того, что на [math]i[/math] -ой итерации будет стянуто ребро из разреза [math]\langle A, B \rangle[/math] . Пусть [math]w = w(A, B)[/math] . По лемме 2 величина минимального потока в текущем графе будет не меньше, чем [math]w[/math] , и в нем будет не менее [math]\frac<2>[/math] вершин по лемме 3. Тогда вероятность того, что будет стянуто ребро из разреза [math]\langle A, B \rangle[/math] , при условии, что до этого не было стянуто ни одно из ребер разреза, будет не более

Обозначим за [math]\xi_i[/math] событие, что на [math]i[/math] -ой итерации случайным образом будет выбрано ребро из разреза [math]\langle A, B \rangle[/math] . Тогда мы только что установили, что

[math]p(\xi_i | \overline <\xi_1>\wedge \ldots \wedge \overline<\xi_>) \leqslant \frac<2>.[/math]

[math]p(\overline <\xi_i>| \overline <\xi_1>\wedge \ldots \wedge \overline<\xi_>) = 1 — p(\xi_i | \overline <\xi_1>\wedge \ldots \wedge \overline<\xi_>) \geqslant 1 — \frac<2> = \frac.[/math]

Тогда вероятность того, что во время работы функции не будет стянуто ни одно ребро оценивается следующим образом:

[math]p(\overline <\xi_1>\wedge \ldots \wedge \overline<\xi_>) = \prod\limits_^ p(\overline <\xi_i>| \overline <\xi_1>\wedge \ldots \wedge \overline<\xi_>) \geqslant [/math]

[math]\geqslant \prod\limits_^ \frac = \frac \cdot \frac \cdot \frac \cdot \ldots \cdot \frac<2> <4>\cdot \frac<1> <3>= \frac<2> \geqslant \frac<2>.[/math]

Таким образом, мы видим, что вероятность получить правильный ответ после единичного запуска функции [math]\mathrm[/math] очень мала. Однако, вызвав эту функцию [math]count[/math] раз мы увеличим эту вероятность. Рассчитаем значение [math]count[/math] такое, чтобы вероятность успеха была близка к [math]1[/math] .

Для этого воспользуемся следующим неравенством:

[math] e^x \geqslant 1 + x[/math] для любого вещественного [math]x[/math] .

Вероятность того, что мы не получим правильный ответ после [math]count[/math] независимых запусков равна

Пусть [math]count = n^2\ln(n)[/math] . Тогда в силу указанного выше неравенства:

То есть, если вызвать функцию [math]\mathrm[/math] [math]n^2\ln(n)[/math] раз, и после каждой итерации запоминать минимум, то вероятность того, что найденный ответ будет неверен [math] \leqslant \frac<1>[/math] . Даже при небольших значениях [math]n[/math] алгоритм практически гарантированно выдает правильный ответ.

Оценка времени работы алгоритма

Время работы функции [math]\mathrm[/math] — [math]O(n^2)[/math] . Функция работает [math]O(n^2\log(n))[/math] раз. Итоговое время работы — [math]O(n^4 \log(n))[/math] .

Оптимизация алгоритма

Каргер совместно со Штейном (англ. Stein) придумали оптимизацию алгоритма Каргера, значительно ускоряющую время его работы. Новый алгоритм называется в честь обоих создателей — алгоритм Каргера-Штейна (англ. Karger-Stein algorithm). Его суть заключается в следуюшем. Заметим, что вероятность стягивания вершины, принадлежащей минимальному разрезу, в начале выполнения функции [math]\mathrm[/math] довольно мала, в то время, как вероятность стянуть ребро, которое не следует стягивать, ближе к концу работы функции существенно возрастает. Тогда будем использовать следующую рекурсивную версию алгоритма:

1. Запускаем функцию [math]\mathrm[/math] и стягиваем ребра до тех пор, пока не останется [math]\frac<\sqrt<2>>[/math] вершин.
2. Запускаем независимо эту же функцию для получившегося графа дважды и возвращаем минимальный из ответов.

Такая модификация алгоритма выдает правильный ответ с точностью, не менее [math]\frac<1><\log(n)>[/math] . Время работы функции [math]\mathrm[/math] вычисляется рекурсивной функцией:

[math]T(n) = O(n^2) + 2 * T(n/\sqrt<2>) = O(n^2\log(n))[/math] .

Это медленнее, чем оригинальный алгоритм, однако вероятность нахождения разреза минимального веса экспоненциально выше. Достаточно запустить алгоритм [math]c\log^2(n)[/math] раз, где [math]c[/math] — некоторая константа. Действительно, рассчитаем вероятность неправильного ответа также, как раньше:

Итоговое время работы — [math] O(n^2\log(n)) \cdot c\log^2(n) = O(n^2\log^3(n))[/math] .

Теория графов в Игре Престолов

Недавно, на Geektimes я опубликовал статью, где привёл немного поверхностной статистики из серии книг «Песнь льда и пламени». Но я не стал углубляться в самую интересную часть, в граф социальных связей, ибо тема заслуживает отдельного внимания. В этой статье я продемонстрирую как теория графов может помочь при анализе подобных данных и приведу реализации алгоритмов, которыми я пользовался.

Всем кому интересно, добро пожаловать под кат.

Из опроса вышеупомянутой статьи, я сделал вывод, что больше трети аудитории Geektimes ознакомлено с книгой фентези романа, а больше половины с сюжетом из сериала. Я надеюсь, аудитории Geektimes и Habrahabr пересекаются и вам возможно будут интересны не только использованные алгоритмы, но и результаты.

Данные

Начнём, конечно же, с главного — данных. У нас есть граф социальной активности:

На нём изображены персонажи из мира престолов в вершинах графа, где размер вершины зависит от сказанных им слов, и диалогов персонажей на ребрах графа, где толщина ребра зависит от количества состоявшихся разговоров.

Общие сведения о графе:

Граф неориентированный.
Вершин (читай персонажей): 1105
Рёбер (читай диалогов): 3505

Это всё хорошо, но кто же составил список всех разговоров, да еще и определил их принадлежность спросите вы меня (в 5ти книгах ведь почти 2 миллиона слов). Метод условных случайных полей, отвечу я. Да, для сбора данных было привлечено машинное обучение и, как заявляет «тренер» модели, точность определения принадлежности разговора составляет около 75%. Я добавлю опросник в конце статьи, чтобы узнать стоит ли переводить эту статью о том как метод условных случайных полей был применен.

Итак, формат входных данных для всех алгоритмов будет одинаковый:

Первая строка содержит V и E, количество вершин и ребер в графе соответственно.

Далее идут V строк с ID персонажа и его именем. После этого E строк вида u v w — описание рёбер. Означает, что между u и v есть ребро с весом w, где u и v это ID персонажа. Напомню, что вес означает количество диалогов между соответствующими персонажами. Вес самих вершин учитываться нигде не будет, т.к. не нашёл достойного ему применения. Ах да, код алгоритмов будет представлен на языке C++.

Нам, конечно же, нужно считать данные. Для этого я создал файлы definitions.h и definitions.cpp. Далее я везде буду подключать definitions.h чтобы кода было меньше и код читался легче. Каждый последующий алгоритм реализован как отдельная функция и вызывается в функции main.

Степень вершины

Для начала, попробуем реализовать что нибудь очень простое, что даже стыдно назвать алгоритмом, но будет интересно читателю/зрителю. Найдём степень каждой вершины. Степень вершины — это количество рёбер, инцидентных (примыкающих к) вершине. Этот параметр в контексте графа, который мы имеем, покажет нам сколько же «друзей» у персонажа.

Это можно сделать за один проход и сложность этого алгоритма О(V+E). Если применить и сортировку результата, как это сделал я, то сложность будет O(E+V*log(V)).

Топ 10 многосвязных персонажей:

1. Тирион Ланнистер: 168
2. Джон Сноу: 128
3. Арья Старк: 104
4. Джейми Ланнистер: 102
5. Серсея Ланнистер: 86
6. Кейтилин Старк: 85
7. Теон Грейджой: 76
8. Дайнерис Таргариен: 73
9. Бриенна: 71
10. Санса Старк: 69

Интересно то, что в топе не оказалось того, кто знаком со многими и по занимаемой должности обязан поддерживать контакт с людьми, Вариса (он на 25ом месте). А вот, казалось бы, второстепенный персонаж Бриенна, от имени которой главы еще нет, на 9ом месте.

Обход графа

Итак, теперь перейдем к простым алгоритмам, а именно к поиску в глубину (Depth-first search) и поиску в ширину (Breadth-first search). Оба алгоритма очень похожи, различаются только способом обхода графа. Они применяются, когда требуется пройти по рёбрам от заданной вершины в графе до другой. В случае поиска в глубину, граф проходится начиная от вершины и поочередно в максимальную глубину по одному из исходящих рёбер. В случае же с поиском в ширину граф обходится сначала по всем своим соседним вершинам, далее по соседям соседних вершин и так пока не пройденных вершин не останется. Оба алгоритма имеют сложность O(V+E).

Связность графа

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

Было бы крайне странно, если бы граф был не связным и в нём было больше одной компоненты, не правда ли? Но к моему удивлению в графе оказалось аж 3 компоненты! Но посмотрев на них я увидел, что присутствовала одна большая компонента, и 2 другие, в которых было по одному персонажу (Это были улыбающийся старик (A smiley old man), который разговаривал с Арьей возле Божьего ока (God’s eye). И повар (A Cook), который играл с Тирионом на корабле). Ничего необычного, у них нет имён и удивительно, что участники разговора вообще определились правильно. Я, конечно же, добавил недостающие рёбра и в результате весь граф получился связным.

Теория рукопожатий

Следующее что мы найдем с помощью алгоритма поиска уже в ширину — максимальное число рукопожатий в графе, другими словами диаметр графа, т.е наидлиннейший из кратчайших путей между всеми вершинами графа. Как оказалось, максимальное количество рукопожатий это 8. Неплохой результат для произведения о «средневековых веках», если учитывать Теорию 6ти рукопожатий. Для примера, одна из таких цепочек связи:

Матушка Кротиха (Mother Mole) — Репейница (Thistle) — Варамир (Varamyr) — Джон Сноу (Jon Snow) — Эддард Старк (Ned Stark) — Барристан Селми (Barristan Selmy) — Квентин Мартелл (Quentyn Martell) — Принц-Оборванец (The Tattered Prince) — Льюис Ланстер (Lewis Lanster)

Такой алгоритм работает за O(V*V+V*E). Так как нужно запустить алгоритм BFS из каждой вершины графа. Будь этот граф деревом, то потребовалось бы только 2 раза запустить BFS. Сначала из любой вершины графа, а затем из самой отдалённой от неё вершины. И наибольшая глубина последнего запуска и была бы диаметром графа.

А раз я нашёл самые длинные пути для всех вершин графа, то можно вычислить и среднее значение, а так же составить распределение максимальных путей. Среднее значение для длины максимальных путей оказалось 6,16 (в среднем вполне вписывается в теорию о 6ти рукопожатиях), а общее среднее расстояние 3,6, для сравнения у фейсбука этот параметр 4.57.

Распределение длин максимальных путей:

Если взглянуть на распределение то мы видим что 77 персонажей находятся «в центре» графа, иными словами они могут связаться с любым другим персонажем не более чем через 4х других. Среди них все основные персонажи истории, кроме Дайнерис Таргариен и Сансы Старк, а среди тех, кому в книгах посвящено меньше пяти глав попали в список Барристан Селми, Джон Коннингтон и Мелисандра.

Клики в графе

Алгоритм Брона-Кербоша позволяет найти максимальные клики в графе, иными словами подмножества вершин, любые две из которых связаны ребром. В контексте рассматриваемого графа это позволит найти сильно связанные компании, которые общались между собой в истории. Сложность алгоритма линейна относительно количества клик в графе, но в худшем случае она экспоненциальна O(3 V/3 ), алгоритм решает NP полную задачу всё таки. Сам по себе алгоритм представляет рекурсивную функцию, которая для каждой вершины находит максимальную клику, т.е. такую, в которую нельзя добавить ни одной другой вершины. Итак, результаты:

Распределение размеров клик:

Как видно, максимальная клика размером в 9 персонажей. К примеру одна из таких — компания Ланнистеров: Тирион, Джейми, Серсея, Варис, Тайвин, Кеван, Пицель, Петир и Мейс Тирелл. Что интересно, все клики размера 8 и 9 сформированы в Королевской Гавани или вблизи неё. А максимальная клика с Дайнерис размера 5.

Остовное дерево

А теперь немного упростим наш граф связей, оставив в нём только «костяк», так называемое остовное дерево, т.е. наиболее важные рёбра связи и при этом превратив граф в дерево со всеми исходными вершинами. Поможет нам в этом алгоритм Крускала. Алгоритм жадный, для его осуществления нужно всего лишь отсортировать все рёбра по их весу и поочередно добавлять каждое ребро, если оно связывает две компоненты. Если использовать правильную структуру данных (обычно используют систему непересекающихся множеств), то сложность алгоритма получится O(E(logE)+V+E) = O(E(logV)). Ниже приведен результат графа, который подвергся этим манипуляциям. Я так же для читаемости удалил рёбра с весом 1.

картинка кликабельна

Итак, из этого графа можно увидеть главных героев и их связь между собой. Как я и ожидал, Тирион Ланнистер находится в «центре» всех связей, от него исходят 4 большие ветки: Серсея Ланнистер, Джон Сноу, Санса Старк и Джорах Мормонт (ветка Дайнерис). Последние в свою очередь герои следующего уровня по связям. Вполне ожидаемый результат, не правда ли?

А вот сколько всего остовных деревьев, включая не только максимальные можно построить? Неимоверно много в данном графе, разумеется. Но их можно подсчитать используя теорему Кирхгофа. Теорема говорит, что если построить матрицу, где все элементы матрицы смежности будут заменены на противоположные, а на главной диагонали будут стоять степени соответствующих вершин, то все алгебраические дополнения полученной матрицы будут равны и это значение будет количеством остовных деревьев графа.

Мосты и шарниры

Мостами в графе называют рёбра, при удалении которых, количество компонент связности увеличивается. Аналогичное определение и у шарниров, только в отличии от мостов, шарниры это вершины, при удалении которых количество компонент связности возрастает. В данном графе, наличие мостов будет означать что в мире престолов существуют связи, которые являются единственным источником коммуникации между отдельными группами персонажей. Шарниры же, это герои, которые являются единственным посредником к группе других персонажей. Мосты и шарниры искать не очень тяжело. Для этого нам понадобится знакомый нам алгоритм поиска в глубину, но слегка модифицированный. Нужно использовать, так называемое, время входа в вершину и функцию времени выхода (fout) на вершине, которая будет принимать значения минимума времени входа и значений fout вершины в которую поиск в глубину пройден, таким образом, если при проходе ребра окажется, что значение функции fout на вершине больше чем время захода в неё, то это будет мостом, а так же и шарниром, а если равно, то только шарниром. Иными словами мы проверяем, возвращаемся ли мы после обхода в то же самое ребро/вершину и только в неё при обходе части графа, если да, то это и будет искомым мостом либо шарниром.

Как и ожидалось, все шарниры и мосты охватывали только малозначимых персонажей. Количество вершин в компонентах, которые получилось бы изолировать, удалением шарниров и мостов, не превышает 4х. Это означает, что нет героя, которым бы невозможно было пожертвовать. Все связаны между собой как минимум через двух других персонажей.

Минимальный разрез

Но всё же интересно узнать, сколько героев требуется «убить» чтобы полностью исключить контакт двух самых популярных (по вышеизложенной статистике) персонажей, скажем, Тириона Ланнистера и Арью Старк, либо Джона Сноу и Серсею Ланнистер. Для этого будем использовать алгоритм Диница. Для начала разберёмся как работает алгоритм.

По теореме Форда-Фалкерсона следует, что величина максимального потока в графе путей равна величине пропускной способности его минимального разреза. Иными словами, мы можем найти минимальный разрез между двумя вершинами (сток и исток) если найдём максимальный поток между этими вершинами. Алгоритм Диница как раз позволяет найти величину максимального потока и, собственно, сам поток. Я не буду разбирать подробно сам алгоритм и предоставлю вам возможность самим разобраться в нём. Для понимания полученного результата достаточно знать, что поток — это некая функция, которая для каждого ребра лежащего на пути от истока к стоку, определяет положительную величину, не превышающую пропускную способность этого ребра. Для упрощения можно представить систему труб с водой, где объем воды протекающей от истока к стоку в момент t и есть величина потока.

Поставленная мною задача слегка отличается от той, что решает алгоритм. Дело в том, что поток определяется на рёбрах, и если мы найдём минимальный разрез, то он «разрежет» граф по рёбрам, т.е. связям в графе, но нам ведь нужно разрезать граф не по рёбрам, а вершинам, т.е. персонажам. Чтобы решить эту задачу нужно подвергнуть граф небольшим изменениям. Раздвоим каждую вершину в графе, скажем вместо вершины v у нас получатся вершины v₁ и v₂, далее если между двумя вершинами v и u было ребро, то перенаправим v₁ в u₂, а u₁ в v₂, вместо ребра (u, v) получатся рёбра (v₁, u₂) и (u₁, v₂). И между каждыми раздвоенными вершинами v₁ и v₂ проведём ребро (v₂, v₁). В полученном, уже ориентированном, графе, все связи сохранятся, но там где раньше были вершины, появятся рёбра. Если вес этих ребер будет 1, а у всех остальных, скажем бесконечность (на практике можно использовать количество вершин в графе), то ребро между раздвоенными вершинами будет слабым звеном в графе и по принципу «предохранителя» не позволит пройти бОльшему потоку через себя, что даст возможность узнать количество вершин, которые нужно удалить, чтобы граф стал несвязным. А дальше запустим алгоритм Диница на полученном графе.

Сложность алгоритма O(n 2 m). Поэтому мы будем искать величину максимального потока не по всем парам вершин, а только по персонажам, которые имеют наибольшее количество связей, иначе для данного графа сложность получится O(n 5 ), где n=1000 и работать всё будет много часов. Ниже я приведу результаты по топ 100 персонажам по связям.

Я немного удивился результатам. Оказалось, что в топ 100, разрезать граф можно избавившись от минимум 6ти персонажей. Все такие связи при этом содержат либо Джона Коннингтона либо Эурона Грейджоя в качестве стока/истока. Но это не основные персонажи. Что интересно, в топ 10ти, в основном минимальный поток равен около 45ти. Например между Тирионом и Арьей поток равен 53, а между Джоном Сноу и Серсеей 42. Но есть и персонаж, которого можно отделить, удалив 16 других персонажей. Это Дайнерис Таргариен, не удивительно, ведь она наиболее удалённая героиня на карте престолов.

Ещё интересно было бы узнать, кто же наиболее «важный» герой в потоках. Т.е. через кого чаще всего протекает максимальный поток. Тут есть чему удивиться. Топ 10 важных персонажей в потоках (в скобках соответствующее количество вхождений в потоки):

1. Тирион Ланнистер (4109)
2. Джейми Ланнистер (3067)
3. Арья Старк (3021)
4. Джон Сноу (2883)
5. Эддард Старк (2847)
6. Серсея Ланнистер (2745)
7. Теон Грейджой (2658)
8. Бриенна (2621)
9. Сандор Клегане (2579)
10. Санса Старк (2573)

11. Джофрей Ланнистер
12. Робб Старк
13. Ренли Баратеон
14. Кейтилин Старк
15. Русе Болтон
16. Йорен
17. Сэм
18. Мелисандра
19. Бран Старк
20. Варис

где из верхних 6ти персонажей в книге уже убиты 5. Не позавидуешь этой десятке. Кто же следующий?

Так же, благодаря потокам, удалось вычислить «лишние» вершины, авторов реплик которых не удалось правильно распознать, поэтому они были связаны со многими персонажами, с которыми не должны были пересекаться. Ими оказались Человек (A Man) и Страж (A Guard). В следствии чего, я удалил эти вершины и пересчитал всю статистику заново.

На этом всё. Напоследок можно отметить, что Тирион Ланнистер очень важный персонаж в мире престолов. Надеюсь, статься оказалась для вас интересной, а возможно и полезной. Исходный код всех алгоритмов есть так же и на GitHub, ссылки ниже.

Ссылки:

Проект на GitHub
Исходный социальный граф
Программа Gephi, с помощью которого можно открыть проект
Автор фото заголовка — Adam Foster

В конце, как и обещал, опросник: стоит ли переводить статью о том, как были определены авторы диалогов в книгах?