Анализ сетевых графов: визуализация персонажей Гамильтона как социальной сети

Несколько лет назад я запоем читал книги «Игра престолов» и обнаружил, что мне трудно уследить за всеми персонажами в своей голове. (Это неудивительно — в сериале более 150 именных персонажей!) Я перемещался между главами или постоянно просматривал вики «Песнь Льда и Пламени», чтобы запомнить сюжетные линии. Мне нужна была мысленная карта — наверняка есть лучший способ визуализировать этих персонажей?

Основы

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

• Кружочки, обозначающие языки, на которых были написаны статьи, являются «вершинами» графа (взаимозаменяемо — «узлами»).

• «Ребра» — это линии, соединяющие каждую пару вершин. Каждое ребро графа определяется с помощью функции инцидентности, которая отображает пару вершин на ребро.

  
  

В этом примере каждое ребро представляет (по весу или толщине линии) количество редакторов, внесших вклад в оба языка, которые соединяет линия. Это то, что мы называем неориентированным простым графом. «Ненаправленный» означает, что {en--> fr} и {fr -> en} идентичны, а «простой» означает, что каждую пару вершин соединяет не более одного ребра. Граф также «взвешен», что означает, что толщина ребер зависит от силы связи между вершинами. В этом примере функция взвешенной заболеваемости может выглядеть примерно так:

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

Получение данных для набора данных Гамильтона

«В науке о данных 80 процентов времени тратится на подготовку данных, 20 процентов времени тратится на жалобы на необходимость подготовки данных».

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

Разведочный анализ

Вот как выглядит набор данных Гамильтона .

На каждого персонажа/песню/лирическую строку приходится одна строка записи.

• Название - относится к названию песни.
• Спикер - относится к персонажу, который поет данную строчку.
• Строки — относятся к конкретной строке текста в песне.

Построение матрицы смежности

Чтобы построить сетевой граф всех говорящих Гамильтона , необходимо определить следующее:

• Ноды (список спикеров)

• Края (для подключения каждой пары динамиков)

• Функция инцидентности для сопоставления каждой пары вершин с ребром (с дополнительным весом)

  
  

Функция инцидентности, которую я выбрал, — это количество песен, в которых каждая пара динамиков появляется вместе . Я предполагаю, что чем в большем количестве песен два персонажа появляются вместе, тем крепче их отношения.

Weight {speaker,x, speaker,y} = #songs that feature both speaker,x and speaker,y

Используя dplyr R, я могу преобразовать исходный набор данных в объект **{src, dest, weight}** , а затем преобразовать его в матрицу смежности. Затем я могу использовать Graph.adjacency в пакете R igraph для создания «объекта графика» из этой матрицы смежности, который затем можно использовать для построения графиков и другого анализа.

Визуализация сетевого графика

Graph_obj можно визуализировать с помощью функцииplot.igraph . Поскольку эта функция имеет множество пользовательских макетов на выбор, я начинаю с рендеринга того же графика, используя макет «звезда».

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

Как этот график может это отразить?

Здесь в игру вступают вес ребра и степень вершины . Я начинаю с экспериментирования с параметрами plot.igraph , чтобы сделать edge.width (т. е. толщину края графика) относительно веса и vertex.label.cex (т. е. размер шрифта вершины) относительно степени.

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

Вы также можете использовать библиотеку visNetwork в R для создания интерактивного сетевого графика. Библиотека позволяет увеличивать и уменьшать масштаб нескольких частей графика (особенно полезно для очень больших графиков) и поддерживает Shiny.

Меры центральности

Центральность — ключевое понятие в теории графов, позволяющее определить значимость узлов:

• Степень централизации : это мера количества ребер, соединенных с каждым узлом.

• Собственная центральность : она представляет собой меру того, насколько «хорошо связан» узел, сколько каналов общего доступа и т. д. в сети. Он идентифицирует узлы, оказывающие влияние на всю сеть, а не только на те, которые напрямую к ней подключены.

• Центральность по посредничеству: буквально это то, насколько данный узел находится между другими узлами и действует как «мост» между различными кластерами сетей. Это мера «влияния» каждой вершины на остальную часть сети.

  
  

Я могу использовать функции Grade(), Betweenness() и eigen_centrality() igraph, чтобы получить централизованность сгенерированного графа:

Похоже, что у Аарона Берра самая высокая центральность посредничества («мост») на нашем графике, а у Гамильтона самая высокая центральность по собственным векторам («влиятель»). Делайте из этого что хотите.

Заключение

Бизнес-приложения сетевых графов многочисленны:

• Сайты социальных сетей используют сетевые графики для создания сообществ похожих пользователей и предоставления целевых рекомендаций. Простейшая реализация алгоритма функции «предлагаемых друзей» может выглядеть примерно так: «Девять из десяти непосредственных друзей Алисы также дружат с Бобом -> рекомендовать Боба как потенциального друга Алисы».

  
  

• Приложения, которые отображают кратчайшее расстояние от места X до места Y (например, карты, службы совместного использования поездок, цепочки поставок и логистика для грузовиков доставки и т. д.), вероятно, используют варианты алгоритмов «кратчайшего пути», широко известных в информатике как Задача коммивояжера .

  
  

• Теория сетей является важнейшим компонентом лексической и семантической обработки в рамках обработки естественного языка (NLP), которая, в свою очередь, используется чат-ботами и виртуальными помощниками, такими как Alexa, Cortana, Siri и даже Watson от IBM, выигравшим Jeopardy! , игра слов и слов, далеко не простая.

  
  

• В таких громких играх для вечеринок, как «Шесть градусов Кевина Бэкона», используются сетевые графы.

  
  

• В эпидемиологии меры центральности могут использоваться для выявления причин пандемий или событий «суперраспространения».

  
  

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

  
  

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