[Перевод] Социальная сеть вселенной Звёздных войн17.12.2015 08:33

Рекурсивная функция, принимающая весь сценарий, и ищущая шаблоны — 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 " [name] "
let getFormat2Names text =
    let m = Regex.Match(text, "[ ]*[/A-Z0-9 -]+[ ]*")
    if m.Success then
        let name = m.Value.Replace("","").Replace("","").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

/// 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, и Хана — как посредника Чюи, предположив, что их взаимодействия будут схожими. Я применила следующую формулу для подсчёта силы связей в диалоговой соцсети:

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

После ручного возвращения Чубакки и 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 [] linkFile = __SOURCE_DIRECTORY__ + "/networks/starwars-episode-1-interactions.json"
type Network = JsonProvider

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

© Habrahabr.ru