Несколько лет назад я запоем читал книги и обнаружил, что мне трудно уследить за всеми персонажами в своей голове. (Это неудивительно — в сериале более 150 именных персонажей!) Я перемещался между главами или постоянно просматривал вики чтобы запомнить сюжетные линии. Мне нужна была мысленная карта — наверняка есть лучший способ этих персонажей? «Игра престолов» «Песнь Льда и Пламени», визуализировать Основы На изображении представлен , который иллюстрирует вклад редакторов Википедии в разные языки. Используя этот пример, приведем некоторые основы (или краткое напоминание, если вы уже знакомы) концепций теории графов: пример сетевого графика из Википедии Кружочки, обозначающие языки, на которых были написаны статьи, являются «вершинами» графа (взаимозаменяемо — «узлами»). «Ребра» — это линии, соединяющие каждую пару вершин. Каждое ребро графа определяется с помощью функции инцидентности, которая отображает пару вершин на ребро. В этом примере каждое ребро представляет (по весу или толщине линии) количество редакторов, внесших вклад в языка, которые соединяет линия. Это то, что мы называем неориентированным простым графом. «Ненаправленный» означает, что {en--> fr} и {fr -> en} идентичны, а «простой» означает, что каждую пару вершин соединяет не более одного ребра. Граф также «взвешен», что означает, что толщина ребер зависит от связи между вершинами. В этом примере функция взвешенной заболеваемости может выглядеть примерно так: оба силы Хотя визуальное представление графиков таким образом представляет собой интуитивный подход к быстрому отображению взаимосвязей, чтобы их было легко понять, есть еще более глубокие идеи, которые мы можем получить, представляя набор данных в виде объекта графа. Получение данных для набора данных Гамильтона «В науке о данных 80 процентов времени тратится на подготовку данных, 20 процентов времени тратится на жалобы на необходимость подготовки данных». Ученые, работающие с данными, могут не во всем соглашаться, но мы согласны с тем, что самая сложная часть любого проекта — это получение данных. К счастью для нас, эта часть статьи уже позади. хороший чистый текстами песен , который вы можете просто загрузить и начать рисовать графики. На Kaggle доступен набор данных с Гамильтона Разведочный анализ Вот как выглядит набор данных . Гамильтона На каждого персонажа/песню/лирическую строку приходится одна строка записи. - относится к названию песни. Название - относится к персонажу, который поет данную строчку. Спикер — относятся к конкретной строке текста в песне. Строки Построение матрицы смежности Чтобы построить сетевой граф всех говорящих , необходимо определить следующее: Гамильтона Ноды (список спикеров) Края (для подключения каждой пары динамиков) Функция инцидентности для сопоставления каждой пары вершин с ребром (с дополнительным весом) Функция инцидентности, которую я выбрал, — это . Я предполагаю, что чем в большем количестве песен два персонажа появляются вместе, тем крепче их отношения. количество песен, в которых каждая пара динамиков появляется вместе Weight {speaker,x, speaker,y} = #songs that feature both speaker,x and speaker,y Используя dplyr R, я могу преобразовать исходный набор данных в объект , а затем преобразовать его в матрицу смежности. Затем я могу использовать Graph.adjacency в для создания «объекта графика» из этой матрицы смежности, который затем можно использовать для построения графиков и другого анализа. **{src, dest, weight}** пакете R igraph Визуализация сетевого графика Graph_obj можно визуализировать с помощью . Поскольку эта функция имеет множество пользовательских макетов на выбор, я начинаю с рендеринга того же графика, используя макет «звезда». функцииplot.igraph Результатом является технически сетевой сюжет. Но можно ли сделать еще лучше? Приведенная выше диаграмма, кажется, предполагает, что все вершины и ребра имеют одинаковую важность, но это подрывает весь смысл визуализации социальной сети. Некоторые персонажи действительно более «значимы», а у некоторых говорящих отношения более крепкие по сравнению с другими. Как этот график может это отразить? Здесь в игру вступают и . Я начинаю с экспериментирования с параметрами , чтобы сделать (т. е. толщину края графика) относительно веса и (т. е. размер шрифта вершины) относительно степени. вес ребра степень вершины plot.igraph edge.width vertex.label.cex Намного лучше! Персонажи с более высокой степенью визуально крупнее, а различие между сильными и слабыми связями также видно по темноте линий. Эта итерация гораздо более интуитивна и позволяет зрителю сразу понять отношения между персонажами. Также вполне уместно, что King George — одинокий узел, учитывая, что его песни всегда (очень забавные) монологи. Вы также можете использовать библиотеку в R для создания сетевого графика. Библиотека позволяет увеличивать и уменьшать масштаб нескольких частей графика (особенно полезно для очень больших графиков) и поддерживает Shiny. visNetwork интерактивного Меры центральности — ключевое понятие в теории графов, позволяющее определить значимость узлов: Центральность : это мера количества ребер, соединенных с каждым узлом. Степень централизации : она представляет собой меру того, насколько «хорошо связан» узел, сколько каналов общего доступа и т. д. в сети. Он идентифицирует узлы, оказывающие влияние на всю сеть, а не только на те, которые напрямую к ней подключены. Собственная центральность буквально это то, насколько данный узел находится другими узлами и действует как «мост» между различными кластерами сетей. Это мера «влияния» каждой вершины на остальную часть сети. Центральность по посредничеству: между Я могу использовать функции Grade(), Betweenness() и eigen_centrality() igraph, чтобы получить централизованность сгенерированного графа: Похоже, что у Аарона Берра самая высокая («мост») на нашем графике, а у Гамильтона самая высокая («влиятель»). Делайте из этого что хотите. центральность посредничества центральность по собственным векторам Заключение Бизнес-приложения сетевых графов многочисленны: Сайты социальных сетей используют сетевые графики для создания сообществ похожих пользователей и предоставления целевых рекомендаций. Простейшая реализация алгоритма функции «предлагаемых друзей» может выглядеть примерно так: «Девять из десяти непосредственных друзей Алисы также дружат с Бобом -> рекомендовать Боба как потенциального друга Алисы». Приложения, которые отображают кратчайшее расстояние от места X до места Y (например, карты, службы совместного использования поездок, цепочки поставок и логистика для грузовиков доставки и т. д.), вероятно, используют варианты алгоритмов «кратчайшего пути», широко известных в информатике как . Задача коммивояжера Теория сетей является важнейшим компонентом лексической и семантической обработки в рамках обработки естественного языка (NLP), которая, в свою очередь, используется чат-ботами и виртуальными помощниками, такими как Alexa, Cortana, Siri и даже , игра слов и слов, далеко не простая. Watson от IBM, выигравшим Jeopardy! В таких громких играх для вечеринок, как используются сетевые графы. «Шесть градусов Кевина Бэкона», В эпидемиологии меры центральности могут использоваться для выявления причин пандемий или событий «суперраспространения». Если задуматься, Интернет — это просто гигантская сеть различных веб-сайтов. Поисковые системы используют меры , чтобы возвращать наиболее релевантные страницы для определенного поискового запроса. графа знаний Какими бы забавными они ни были, важно отметить, что сетевые графы не лишены недостатков при использовании в производстве. Например, они могут быть ресурсоемкими. Как и в случае с любыми матричными операциями, масштабируемость и производительность иногда страдают. Существует также проблема «холодного старта» — если ваш набор данных слишком разрежен или между сущностями не так много связей, сетевой граф не является эффективным решением. Однако при правильном использовании и в правильном контексте они могут оказаться ценными для бизнеса. • Код: https://github.com/iswaryam/hamilton/ Кредит набора данных: https://www.kaggle.com/lbalter/hamilton-lyrics# Если вы фанат Поттера, загляните на мой GitHub — я также нарисовал графики персонажей аналогичным методом. Гарри Поттера
