Социальная сеть вселенной Звёздных войн

в 23:51, , рубрики: star wars, визуализация данных, Программирование, социальные сети

image

Кто-то ждёт рождества, кто-то – новой серии Звёздных войн, «Пробуждение силы». А в это время я решила обработать весь шестисерийный цикл с количественной точки зрения и вычленить социальные сети, содержащиеся в нём – как из каждого фильма по отдельности, так и из всей вселенной ЗВ вместе. Пристальное разглядывание соцсетей выявляет интересные различия между оригинальными частями и их приквелами.

Ниже – соцсеть, добытая из всех 6 фильмов в сумме.

image

открыть

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

Узлы – это персонажи. Их соединение линией означает, что они говорят в одной и той же сцене. Чем больше они говорят, тем толще линия. Размер каждого узла пропорционален количеству сцен, в которых появляется персонаж. Пришлось принять немало трудных решений: например, Энакин и Дарт Вейдер, очевидно, один и тот же персонаж, но они представлены разными узлами на визуализации, поскольку этом их разделение важно для сюжета. И наоборот, я специально объединила Палпатина с Дартом Сидиусом, а Амидалу – с Падме.

Персонажи оригинальной трилогии расположены преимущественно справа и практически отделены от персонажей приквелов, поскольку большинство персонажей появляется только в одной из трилогий. Основные узлы, объединяющие обе сети – это Оби-ван Кеноби, R2-D2 и C-3PO. Роботы, очевидно, представляют особую важность для сюжета, ибо появляются чаще всего в фильмах. Структура у обеих подсетей разная. В оригинальной трилогии меньше важных узлов (Люк, Хан, Лея, Чубакка и Дарт Вейдер), и они плотно соединены между собой. У приквелов видно больше узлов и больше соединяющих линий.

Временные шкалы персонажей

Поскольку одни и те же персонажи встречаются в разных фильмах, я создала сравнительную временную шкалу, разбитую по эпизодам.

image

Здесь собраны все упоминания персонажей, включая упоминание их имён в разговорах других. Энакин появляется вместе с Дартом Вейдером в 3-м эпизоде, а затем Дарт Вейдер берёт вверх. Энакин снова появляется к концу 6-го эпизода, в котором Дарт Вейдер отворачивается от Тёмной стороны.

Те же персонажи, что постоянно задействованы во всех фильмах, стоят и в центре соцсети. Это Оби-Ван, C-3PO и R2-D2. Йода и Император также есть во всех фильмах, но они разговаривают с небольшим количеством людей.

Сети для отдельных эпизодов

Теперь рассмотрим эпизоды по отдельности. Обратите внимание, как количество узлов и сложность сетей меняется от приквелов к оригинальным эпизодам. (кликабельно).

image

image

image

image

image

image

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

Джордж Лукас как-то сказал:

На самом деле, это история трагедии Дарта Вейдера, начинается она, когда ему девять лет, а заканчивается с его гибелью.

Но действительно ли Дарт Вейдер/Энакин получился центральным персонажем? Попробуем применить методы сетевого анализа, чтобы выявить центральных персонажей и их социальную структуру. Я подсчитала два параметра, показывающих важность персонажа в сети.

  • степень важности: количество соединительных линий у узла в сети. То есть, общее количество сцен, в которых он разговаривает.
  • промежуточность: количество кратчайших путей, ведущих через узел. К примеру, если вы – Лея, и хотите отправить сообщение Гридо, то кратчайшим путём к нему будет путь через Хана Соло. А чтобы отправить сообщение Люку, идти через Хана не нужно, поскольку Лея знает его лично. Таким образом и подсчитывается промежуточность Хана – через количество кратчайших путей между всеми остальными персонажами, проходящими через него.

Первый параметр в результате показывает, со сколькими персонажами контактирует персонаж, а второй – насколько он в целом важен для истории. Персонажи с высокой промежуточностью объединяют разные участки соцсетей.

Чем параметр больше, тем он важнее. Ниже – Top-5 персонажей, ранжированных по параметрам, для каждого фильма.

image

В первых трёх эпизодах самым связным персонажем оказался Энакин. При этом в интеграции он практически не участвует – его промежуточность настолько мала, что он даже не попал в Top-5. Получается, что другие персонажи общаются лично, а не через него. А как это будет выглядеть для оригинальной трилогии?

image

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

Возможно, из-за этого оригинальная трилогия более популярна. Сюжеты более последовательны, и развиваются благодаря главным персонажам. У приквелов структура менее централизованная, нет центрального персонажа.

А как будут выглядеть эти измерения в применении ко всем фильмам сразу? Я сделала два варианта подсчётов – с разделением персонажей Энакина и Дарта Вейдера, и с объединением.

Слева – два отдельных персонажа, справа — персонажи объединены:

image

В первом случае Энакин остаётся самым связанным персонажем, но не центральным. При их объединении он становится третьим по важности персонажем в рейтинге промежуточности. В любом случае оказывается, что в реальности фильмы объединены персонажем Оби-Вана Кеноби.

image

Как это сделано

По большей части я использовала F#, скомбинировав его с D3.js для визуализаций соцсети, и с R для анализа центральности сетей. Все исходники доступны на гитхабе. Здесь я разберу только отдельные, самые интересные части года.

Разбор сценариев

Все сценарии я свободно скачала с The Internet Movie Script Database (IMSDb) (пример: сценарий к Episode IV: The New Hope). Правда, там лежат в основном черновики, которые часто отличаются от финальных версий.

Первый шаг – разбор сценариев. Оказалось, что у разных файлов немного разный формат. Они все представлены в HTML, либо между тегами <td class="srctext"></td>, или между <pre></pre>. Я использовала Html Parser из библиотеки F# Data, позволяющий обращаться к отдельным тегам при помощи запросов типа:

open FSharp.Data
let url = "http://www.imsdb.com/scripts/Star-Wars-A-New-Hope.html"
HtmlDocument.Load(url).Descendants("pre")

Код доступен в файле parseScripts.fs

Следующий шаг – извлечение нужной информации из сценариев. Обычно они выглядят так:


INT. GANTRY - OUTSIDE CONTROL ROOM - REACTOR SHAFT

Luke moves along the railing and up to the control room.

[...]
LUKE
He told me enough! It was you
who killed him.

VADER
No. I am your father.

Shocked, Luke looks at Vader in utter disbelief.

LUKE
No. No. That's not true!
That's impossible!

Каждая сцена начинается с обозначения места действия и примечания INT. (внутри) or EXT. (снаружи). Также может присутствовать пояснительный текст. В диалогах имена персонажей указываются заглавными буквами и жирным шрифтом.

Поэтому разделителями сцен могут служит прримечания INT. и EXT., написанные болдом.

// split the script by scene
// each scene starts with either INT. or EXT. 
let rec splitByScene (script : string[]) scenes =
    let scenePattern = "<b>[ 0-9]*(INT.|EXT.)"
    let idx = 
        script 
        |> Seq.tryFindIndex (fun line -> Regex.Match(line, scenePattern).Success)
    match idx with
    | Some i ->
        let remainingScenes = script.[i+1 ..]
        let currentScene = script.[0..i-1]
        splitByScene remainingScenes (currentScene :: scenes)
    | None -> script :: scenes 

Рекурсивная функция, принимающая весь сценарий, и ищущая шаблоны — EXT. или INT. болдом, перед которыми может идти номер сцены. Она разбивает строки на текущую сцену и остальной текст, и затем рекурсивно повторяет процедуру.

Получаем список персонажей

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

Пришлось использовать регулярки.

// Extract names of characters that speak in scenes. 
// A) Extract names of characters in the format "[name]:"
let getFormat1Names text =
    let matches = Regex.Matches(text, "[/A-Z0-9 -]+ *:")
    let names = 
        seq { for m in matches -> m.Value }
        |> Seq.map (fun name -> name.Trim([|' '; ':'|]))
        |> Array.ofSeq
    names

// B) Extract names of characters in the format "<b> [name] </b>"
let getFormat2Names text =
    let m = Regex.Match(text, "<b>[ ]*[/A-Z0-9 -]+[ ]*</b>")
    if m.Success then
        let name = m.Value.Replace("<b>","").Replace("</b>","").Trim()
        [| name |]
    else [||]

Каждая регулярка ищет не только заглавные, но и числа, тире, пробелы и слеши. Поскольку имена персонажей бывают разные: «R2-D2» или даже «FODE/BEED».

Также пришлось учесть, что у некоторых персонажей по нескольку имён. Палпатин – Дарт Сидиус – Император, Амидала – Падме. Я сделала файл псевдонимов aliases.csv, где задал имена, подлежащие объединению.

let aliasFile = __SOURCE_DIRECTORY__ + "/data/aliases.csv"
// Use csv type provider to access the csv file with aliases
type Aliases = CsvProvider<aliasFile>

/// Dictionary for translating character names between aliases
let aliasDict = 
    Aliases.Load(aliasFile).Rows 
    |> Seq.map (fun row -> row.Alias, row.Name)
    |> dict

/// Map character names onto unique set of names
let mapName name = if aliasDict.ContainsKey(name) then aliasDict.[name] else name

/// Extract character names from the given scene
let getCharacterNames (scene: string []) =
    let names1 = scene |> Seq.collect getFormat1Names 
    let names2 = scene |> Seq.collect getFormat2Names 
    Seq.append names1 names2
    |> Seq.map mapName
    |> Seq.distinct

И теперь, наконец, можно извлекать имена персонажей из сцен. Следующая функция извлекает все имена персонажей из всех сценариев, для которых заданы URL.

let allNames =
  scriptUrls
  |> List.map (fun (episode, url) ->
    let script = getScript url
    let scriptParts = script.Elements()

    let mainScript = 
        scriptParts
        |> Seq.map (fun element -> element.ToString())
        |> Seq.toArray

    // Now every element of the list is a single scene
    let scenes = splitByScene mainScript [] 

    // Extract names appearing in each scene
    scenes |> List.map getCharacterNames |> Array.concat )
  |> Array.concat
  |> Seq.countBy id
  |> Seq.filter (snd >> (<) 1)  // filter out characters that speak in only one scene

Осталась ещё одна проблема – некоторые имена персонажей не были именами. Это были названия вроде «Пилот», «Офицер» или «Капитан». Пришлось вручную фильтровать те имена, которые были реальными. Так появился список characters.csv

Взаимодействие персонажей

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

let characters = 
    File.ReadAllLines(__SOURCE_DIRECTORY__ + "/data/characters.csv") 
    |> Array.append (Seq.append aliasDict.Keys aliasDict.Values |> Array.ofSeq)
    |> set

Тут я создала набор всех имён персонажей и их псевдонимов для поиска и фильтрации. Затем я использовала его для поиска персонажей в каждой из сцен.

let scenes = splitByScene mainScript [] |> List.rev

let namesInScenes = 
    scenes 
    |> List.map getCharacterNames
    |> List.map (fun names -> names |> Array.filter (fun n -> characters.Contains n)) 

Затем я использовала отфильтрованный список персонажей для определения соцсети.

// Create weighted network
let nodes = 
    namesInScenes 
    |> Seq.collect id
    |> Seq.countBy id        
    // optional threshold on minimum number of mentions
    |> Seq.filter (fun (name, count) -> count >= countThreshold)

let nodeLookup = nodes |> Seq.map fst |> set

let links = 
    namesInScenes 
    |> List.collect (fun names -> 
        [ for i in 0..names.Length - 1 do 
            for j in i+1..names.Length - 1 do
                let n1 = names.[i]
                let n2 = names.[j]
                if nodeLookup.Contains(n1) && nodeLookup.Contains(n2) then
                    // order nodes alphabetically
                    yield min n1 n2, max n1 n2 ])
    |> Seq.countBy id

Так получился список узлов, с количеством их разговоров на всём протяжении сценария — этот подсчёт используется для определения размера узла. Затем я создала линию между двумя персонажами, которые говорят в одной сцене, и подсчитала их количество. Вместе узлы и линии определяют всю соцсеть.

Наконец, я вывела эти данные в формате JSON. Все соцсети, глобальные и индивидуальные по эпизодам, можно найти на моём гитхабе. Полный код этого шага лежит в файле getInteractions.fsx

Упоминания персонажей

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

let scenes = 
    splitByScene mainScript [] |> List.rev
let totalScenes = scenes.Length

scenes
|> List.mapi (fun sceneIdx scene -> 
    // some names contain typos with lower-case characters
    let lscene = scene |> Array.map (fun s -> s.ToLower()) 

    characters
    |> Array.map (fun name -> 
        lscene 
        |> Array.map (fun contents -> if containsName contents name then Some name else None )
        |> Array.choose id)
    |> Array.concat
    |> Array.map (fun name -> mapName (name.ToUpper()))
    |> Seq.distinct 
    |> Seq.map (fun name -> sceneIdx, name)
    |> List.ofSeq)
|> List.collect id,
totalScenes

Для извлечения временных шкал я использовала нумеровку сцен, чтобы поставить в соответствие интервал каждому эпизоду в виде [episode index−1,episode index]. Это дало мне относительную шкалу появления персонажей в эпизодах. Времена в ячейках intervals [0,1] относятся к Эпизоду I, в ячейках [1,2] — к эпизоду II, и т.д.

// extract timelines
[0 .. 5]
|> List.map (fun episodeIdx -> getSceneAppearances episodeIdx)
|> List.mapi (fun episodeIdx (sceneAppearances, total) ->
    sceneAppearances 
    |> List.map (fun (scene, name) -> 
        float episodeIdx + float scene / float total, name))      

Сохранила это я в csv, где каждая строка содержит имя персонажа и точные времена, в котором он появлялся в фильмах, разделённые запятыми. Полностью код доступен в файле getMentions.fsx.

Добавим персонажей без слов

Просматривая статистику разговоров по персонажам, я увидел, что в ней отсутствуют R2-D2 и Чубакка. Вуки не только не получил медальку, но и пропал из всех диалогов. Конечно, они упоминаются в сценарии, но только как персонажи без диалогов.

Конечно, проигнорировать их было никак нельзя, и я решил вставить их в соцсеть на основании диалогов.

Я извлёк размеры узлов и связи между двумя отсутствующими персонажами из сети, определяемые по их упоминаниям. Чтобы превратить это в связи внутри соцсети, я решила масштабировать все полученные данные пропорционально другим сходным персонажам, которые участвуют в сценарии. Я выбрал C-3PO, поскольку он является посредником R2-D2, и Хана – как посредника Чюи, предположив, что их взаимодействия будут схожими. Я применила следующую формулу для подсчёта силы связей в диалоговой соцсети:

image

Визуализация

После ручного возвращения Чубакки и R2-D2 у меня получился полный набор соцсетей как для отдельных фильмов, так и для всей франшизы. Для визуализации соцсетей я использовала Силу… Ну, на самом деле, сило-направленную сетевую раскладку (force-directed network layout) из библиотеки D3.js. Этот метод использует физическую симуляцию заряженных частиц. Самое важное в коде следующее:

d3.json("starwars-episode-1-interactions-allCharacters.json", function(error, graph) {
  /* More code here */
  var link = svg.selectAll(".link")
      .data(graph.links)
    .enter().append("line")
      .attr("class", "link")
      .style("stroke-width", function(d) { return Math.sqrt(d.value); });

  var node = svg.selectAll(".node")
      .data(graph.nodes)
    .enter().append("circle")
      .attr("class", "node")
      .attr("r", 5)
      .style("fill", function (d) { return d.colour; })
      .attr("r", function (d) { return 2*Math.sqrt(d.value) + 2; })
      .call(force.drag);
  /* More code here */
});

На предыдущих шагах я сохранила все сети в JSON. Тут я их загружаю и определяю узлы и связи. Для каждого узла добавляется свой цвет, и значение, обозначающее важность (количество фраз персонажа). Этот параметр определяет радиус r, в результате все узлы масштабируются по важности. Так же и для связей – в JSON хранилась толщина каждой связи, и здесь она отображается через ширину линии.

Анализ центральности

И в конце я провёл анализ центральности каждого персонажа. Для этого я использовала RProvider вместе с пакетом R igraph , чтобы провести анализ сетей в F#. Сначала я загрузил сеть из JSON через FSharp.Data:

open RProvider.igraph

let [<Literal>] linkFile = __SOURCE_DIRECTORY__ + "/networks/starwars-episode-1-interactions.json"
type Network = JsonProvider<linkFile>

let file = __SOURCE_DIRECTORY__ + "/networks/starwars-full-interactions-allCharacters.json"
let nodes = Network.Load(file).Nodes |> Seq.map (fun node -> node.Name) 
let links = Network.Load(file).Links

Переменная links содержит все связи в сети, а узлы характеризуются их индексами. Для упрощения работы я поставила в соответствие индексам имена персонажей:

let nodeLookup = nodes |> Seq.mapi (fun i name -> i, name) |> dict
let edges = 
    links
    |> Array.collect (fun link ->
        let n1 = nodeLookup.[link.Source]
        let n2 = nodeLookup.[link.Target]
        [| n1 ; n2 |] )

Затем я создала объект graph при помощи библиотеки igraph:

let graph =
    namedParams["edges", box edges; "dir", box "undirected"]
    |> R.graph

Подсчёт промежуточности и центральности:

let centrality = R.betweenness(graph)
let degreeCentrality = R.degree(graph)

Код целиком можно найти тут.

Итоги

Как всегда это бывает с научными изысканиями, самое трудное – привести данные в читаемый вид. Поскольку у сценариев SW был немного разный формат, я провела большую часть времени, определяя общие свойства документов, чтобы создать одну функцию для их обработки. После этого пришлось повозиться лишь с проблемами вуки и дроида, у которых не было реплик. Сети в формате JSON можно скачать на гитхабе.

Ссылки

Исходники github.com/evelinag/StarWars-social-network
Соцсети в формате JSON: github.com/evelinag/StarWars-social-network/tree/master/networks
Сценарии: www.imsdb.com

Автор: SLY_G

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js