Análisis de gráficos de red: visualización de personajes de Hamilton como una red social

Hace unos años, estaba leyendo compulsivamente los libros de Juego de Tronos y me resultó difícil realizar un seguimiento de todos los personajes en mi cabeza. (Esto no es sorprendente: ¡hay más de 150 personajes con nombre en la serie!) Iba y venía entre capítulos o buscaba constantemente la wiki de Canción de hielo y fuego para recordar las tramas. Necesitaba un mapa mental. ¿Seguramente había una mejor manera de visualizar a estos personajes?

Los basicos

Aquí se muestra un gráfico de red de muestra de Wikipedia que ilustra las contribuciones de los editores de Wikipedia a diferentes idiomas. Usando este ejemplo, aquí hay algunos conceptos básicos (o un repaso rápido, si ya está familiarizado) de los conceptos de la teoría de grafos:

• Los círculos que representan los idiomas en los que se escribieron los artículos son los "vértices" del gráfico (indistintamente, los "nodos").

• Las “aristas” son las líneas que conectan cada par de vértices. Cada arista del gráfico se determina mediante una función de incidencia que asigna un par de vértices a una arista.

  
  

En este ejemplo, cada borde representa (por grosor o grosor de línea) el número de editores que han contribuido a ambos idiomas que conecta la línea. Esto es lo que llamamos un gráfico simple no dirigido. "No dirigido" significa {en--> fr} y {fr --> en} son idénticos, y "simple" significa que no más de un borde conecta cada par de vértices. El gráfico también está "ponderado", lo que significa que el grosor de los bordes es relativo a la fuerza de la relación entre los vértices. En este ejemplo, la función de incidencia ponderada podría verse así:

Si bien la representación visual de gráficos de esta manera es un enfoque intuitivo para mostrar rápidamente relaciones de modo que sean fáciles de comprender, hay ideas aún más ricas que podemos obtener al representar un conjunto de datos como un objeto gráfico.

Obtener los datos para el conjunto de datos de Hamilton

"En la ciencia de datos, el 80 por ciento del tiempo dedicado a preparar datos, el 20 por ciento del tiempo se dedica a quejarse de la necesidad de preparar datos".

Puede que los científicos de datos no estén de acuerdo en todo, pero estamos de acuerdo en que la parte más difícil de cualquier proyecto es obtener los datos. Por suerte para nosotros, esa parte quedó atrás en este artículo. Hay un conjunto de datos limpio y agradable de letras de Hamilton disponible en Kaggle que simplemente puede descargar y comenzar a graficar.

Análisis exploratorio

Así es como se ve el conjunto de datos de Hamilton .

Hay una línea de grabación por personaje/canción/línea de letra.

• Título : se refiere al nombre de la canción.
• Orador : se refiere al personaje que canta una línea determinada.
• Líneas : se refiere a la línea particular de la letra de la canción.

Construyendo una matriz de adyacencia

Para construir un gráfico de red de todos los hablantes de Hamilton , se debe definir lo siguiente:

• Nodos (lista de oradores)

• Bordes (para conectar cada par de altavoces)

• Función de incidencia para asignar cada par de vértices a un borde (con un peso opcional)

  
  

La función de incidencia que he elegido es el número de canciones en las que aparece cada par de altavoces juntos . Mi suposición es que cuantas más canciones aparezcan juntos dos personajes, más fuerte será su relación.

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

Usando dplyr de R, puedo transformar mi conjunto de datos original en una entidad **{src, dest, weight}** y luego convertirlo en una matriz de adyacencia. Luego puedo usar graph.adjacency en el paquete igraph de R para crear un "objeto gráfico" a partir de esta matriz de adyacencia, que luego puedo usar para trazar y otros análisis.

Visualizando el diagrama de red

Graph_obj se puede visualizar usando la función plot.igraph . Debido a que esta función tiene muchos diseños personalizados para elegir, empiezo renderizando el mismo gráfico usando el diseño de "estrella".

El resultado es técnicamente una trama de red. ¿Pero es posible hacerlo aún mejor? El gráfico anterior parece sugerir que todos los vértices y aristas tienen la misma importancia, pero eso socava el objetivo de visualizar una red social. De hecho, algunos personajes son más “significativos” y algunos hablantes tienen relaciones más fuertes en relación con otros.

¿Cómo puede este gráfico reflejar eso?

Aquí es donde entran en juego el peso del borde y el grado del vértice . Empiezo jugando con los parámetros de la función plot.igraph para hacer que edge.width (es decir, el grosor del borde en el gráfico) sea relativo al peso, y vertex.label.cex (es decir, el tamaño de fuente del gráfico). vértices) en relación con el grado.

¡Mucho mejor! Los personajes con un grado superior son visualmente más grandes, y la distinción entre relaciones fuertes y débiles también se hace evidente en la oscuridad de las líneas. Esta iteración es mucho más intuitiva y permite al espectador captar inmediatamente las relaciones entre los personajes. También es apropiado que King George sea un nodo solitario, considerando que sus canciones son siempre monólogos (muy divertidos).

También puede utilizar la biblioteca visNetwork en R para crear un gráfico de red interactivo . La biblioteca permite acercar y alejar múltiples partes del gráfico (especialmente útil con un gráfico particularmente grande) y es compatible con Shiny.

Medidas de centralidad

La centralidad es un concepto clave en la teoría de grafos para identificar el significado de los nodos:

• Centralidad de grado : es una medida del número de aristas conectadas a cada nodo.

• Centralidad propia : representa una medida de qué tan "bien conectado" está un nodo, cuántos enlaces comparten las conexiones, etc. a través de la red. Identifica nodos con influencia en toda la red, no sólo aquellos conectados directamente a ella.

• Centralidad de intermediación: esto es, literalmente, cuánto es un nodo determinado entre otros nodos y actúa como un "puente" entre varios grupos de redes. Es una medida de la “influencia” de cada uno de los vértices sobre el resto de la red.

  
  

Puedo usar las funciones de grado(), intermediación() y eigen_centrality() de igraph para obtener la centralidad del gráfico generado:

Parece que Aaron Burr tiene la centralidad de intermediación más alta (el "puente") en nuestro gráfico, mientras que Hamilton tiene la centralidad de vector propio más alta (el "influencer"). Haz lo que quieras con eso.

Conclusión

Las aplicaciones comerciales de los gráficos de red son numerosas:

• Los sitios de redes sociales utilizan gráficos de red para crear comunidades de usuarios similares y ofrecer recomendaciones específicas. Una implementación rudimentaria del algoritmo detrás de una función de "amigos sugeridos" podría verse así: "Nueve de cada diez amigos inmediatos de Alice también son amigos de Bob -> recomienda a Bob como un amigo potencial para Alice".

  
  

• Las aplicaciones que trazan la distancia más corta entre el lugar X y el lugar Y (como mapas, servicios de transporte compartido, cadena de suministro y logística para camiones de reparto, etc.) probablemente utilicen variantes de algoritmos de “camino más corto”, conocidos popularmente en informática como El problema del viajante .

  
  

• La teoría de redes es un componente crucial del procesamiento léxico y semántico dentro del procesamiento del lenguaje natural (PNL), que a su vez se utiliza entre chatbots y asistentes virtuales como Alexa, Cortana, Siri e incluso Watson de IBM, ganador de Jeopardy! , un juego de juegos de palabras y juegos de palabras que dista mucho de ser sencillo.

  
  

• Los juegos de fiesta que mencionan nombres como Six Degrees of Kevin Bacon utilizan gráficos de red.

  
  

• En epidemiología, las medidas de centralidad pueden usarse para identificar los orígenes de pandemias o eventos de “superpropagación”.

  
  

• Si lo piensas bien, Internet es simplemente una red gigantesca de diferentes sitios web. Los motores de búsqueda utilizan medidas de gráficos de conocimiento para devolver las páginas más relevantes para una consulta de búsqueda particular.

  
  

Por divertidos que sean, es importante tener en cuenta que los gráficos de red no están exentos de inconvenientes cuando se emplean en producción. Por ejemplo, pueden consumir muchos recursos. Como ocurre con cualquier operación matricial, la escalabilidad y el rendimiento a veces se ven afectados. También existe un problema de "arranque en frío": si su conjunto de datos es demasiado escaso o no hay muchas relaciones entre entidades, un gráfico de red no es una solución eficaz. Sin embargo, si se utilizan correctamente y en el contexto adecuado, pueden resultar valiosos para las empresas.