Análise de gráficos de rede: visualizando personagens de Hamilton como uma rede social

Alguns anos atrás, eu estava lendo os livros de Game of Thrones e tive dificuldade em acompanhar todos os personagens em minha cabeça. (Isso não é surpreendente – há mais de 150 personagens nomeados na série!) Eu estava indo e voltando entre os capítulos ou constantemente pesquisando o wiki de As Crônicas de Gelo e Fogo para lembrar os enredos. Eu precisava de um mapa mental – certamente havia uma maneira melhor de visualizar esses personagens?

O básico

Aqui está um exemplo de gráfico de rede da Wikipedia que ilustra as contribuições dos editores da Wikipedia para diferentes idiomas. Usando este exemplo, aqui estão alguns conceitos básicos (ou uma atualização rápida, se você já estiver familiarizado) dos conceitos da teoria dos grafos:

• Os círculos que representam os idiomas nos quais os artigos foram escritos são os “vértices” do gráfico (intercambiavelmente, os “nós”).

• As “arestas” são as linhas que conectam cada par de vértices. Cada aresta no gráfico é determinada por meio de uma função de incidência que mapeia um par de vértices para uma aresta.

  
  

Neste exemplo, cada aresta representa (por espessura ou espessura da linha) o número de editores que contribuíram para ambas as linguagens que a linha conecta. Isso é o que chamamos de gráfico simples não direcionado. “Não direcionado” significa que {en--> fr} e {fr --> en} são idênticos, e “simples” significa que não mais do que uma aresta conecta cada par de vértices. O gráfico também é “ponderado”, o que significa que a espessura das arestas é relativa à força da relação entre os vértices. Neste exemplo, a função de incidência ponderada poderia ser mais ou menos assim:

Embora a representação visual de gráficos dessa forma seja uma abordagem intuitiva para mostrar rapidamente relacionamentos para que sejam fáceis de compreender, há insights ainda mais ricos que podemos obter ao representar um conjunto de dados como um objeto gráfico.

Obtendo os dados para o conjunto de dados Hamilton

“Na ciência de dados, 80% do tempo gasto na preparação de dados, 20% do tempo é gasto reclamando da necessidade de preparar dados.”

Os cientistas de dados podem não concordar em tudo — mas concordamos que a parte mais difícil de qualquer projeto é obter os dados. Para nossa sorte, essa parte ficou para trás neste artigo. Há um bom conjunto de dados limpo de letras de Hamilton prontamente disponível no Kaggle que você pode simplesmente baixar e começar a representar graficamente.

Análise exploratória

Esta é a aparência do conjunto de dados de Hamilton .

Há uma linha de gravação por personagem/música/linha da letra.

• Título - refere-se ao nome da música.
• Palestrante - refere-se ao personagem que está cantando uma determinada frase.
• Linhas - refere-se à linha específica da letra da música.

Construindo uma matriz de adjacência

Para construir um gráfico de rede de todos os falantes Hamilton , o seguinte deve ser definido:

• Nós (lista de alto-falantes)

• Bordas (para conectar cada par de alto-falantes)

• Função de incidência para mapear cada par de vértices para uma aresta (com um peso opcional)

  
  

A função de incidência que escolhi é o número de músicas em que cada par de alto-falantes aparece junto . Minha suposição é que quanto mais músicas dois personagens aparecem juntos, mais forte é o relacionamento deles.

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

Usando o dplyr de R, posso transformar meu conjunto de dados original em uma entidade **{src, dest, weight}** e, em seguida, convertê-lo em uma matriz de adjacência. Posso então usar graph.adjacency no pacote igraph do R para criar um “objeto gráfico” a partir dessa matriz de adjacência, que posso então usar para plotagem e outras análises.

Visualizando o gráfico da rede

O graph_obj pode ser visualizado usando a função plot.igraph . Como esta função tem muitos layouts personalizados para escolher, começo renderizando o mesmo gráfico usando o layout “estrela”.

O resultado é tecnicamente um gráfico de rede. Mas é possível fazer ainda melhor? O gráfico acima parece sugerir que todos os vértices e arestas têm a mesma importância – mas isso prejudica todo o objetivo de visualizar uma rede social. Alguns personagens são de fato mais “significativos” e alguns falantes têm relacionamentos mais fortes em relação a outros.

Como este gráfico pode refletir isso?

É aqui que o peso da aresta e o grau do vértice entram em jogo. Começo brincando com os parâmetros da função plot.igraph para tornar edge.width (ou seja, a espessura da borda no gráfico) em relação ao peso e vertex.label.cex (ou seja, o tamanho da fonte do gráfico). vértices) em relação ao grau.

Muito melhor! Personagens com um grau mais alto são visualmente maiores, e a distinção entre relacionamentos fortes e fracos também é aparente na escuridão das linhas. Esta iteração é muito mais intuitiva e permite ao espectador compreender imediatamente as relações entre os personagens. Também é justo que King George seja um nó solitário, considerando que suas canções são sempre monólogos (muito engraçados).

Você também pode usar a biblioteca visNetwork em R para criar um gráfico de rede interativo . A biblioteca torna possível aumentar e diminuir o zoom em várias partes do gráfico (especialmente útil com um gráfico particularmente grande) e tem suporte para Shiny.

Medidas de centralidade

Centralidade é um conceito chave na teoria dos grafos para identificar a importância dos nós:

• Centralidade de grau : Esta é uma medida do número de arestas conectadas a cada nó.

• Centralidade própria : representa uma medida de quão “bem conectado” um nó está, quantos links as conexões compartilham e assim por diante através da rede. Ele identifica nós com influência sobre toda a rede, não apenas aqueles diretamente conectados a ela.

• Centralidade de intermediação: é literalmente o quanto um determinado nó está entre outros nós e atua como uma “ponte” entre vários clusters de redes. É uma medida da “influência” de cada um dos vértices no resto da rede.

  
  

Posso usar as funções Degree(), Betweenness() e eigen_centrality() do igraph para obter centralidade para o gráfico gerado:

Parece que Aaron Burr tem a maior centralidade de intermediação (a “ponte”) em nosso gráfico, enquanto Hamilton tem a maior centralidade de autovetor (o “influenciador”). Faça o que quiser com isso.

Conclusão

As aplicações comerciais de gráficos de rede são numerosas:

• Os sites de redes sociais utilizam gráficos de rede para criar comunidades de usuários semelhantes e oferecer recomendações direcionadas. Uma implementação rudimentar do algoritmo por trás de um recurso de “amigos sugeridos” poderia ser mais ou menos assim: “Nove em cada dez amigos imediatos de Alice também são amigos de Bob -> recomendo Bob como um amigo em potencial para Alice”.

  
  

• Aplicações que mapeiam a distância mais curta do lugar X ao lugar Y (como mapas, serviços de transporte compartilhado, cadeia de suprimentos e logística para caminhões de entrega, e assim por diante) provavelmente usam variantes de algoritmos de “caminho mais curto”, popularmente conhecidos na ciência da computação como o problema do caixeiro viajante .

  
  

• A teoria da rede é um componente crucial do processamento léxico e semântico dentro do processamento de linguagem natural (PNL), por sua vez usado entre chatbots e assistentes virtuais como Alexa, Cortana, Siri e até mesmo o Watson da IBM, vencedor do Jeopardy! , um jogo de trocadilhos e palavras que está longe de ser simples.

  
  

• Jogos de festa que chamam a atenção, como Six Degrees of Kevin Bacon, usam gráficos de rede.

  
  

• Em epidemiologia, as medidas de centralidade podem ser utilizadas na identificação das origens de pandemias ou eventos “super disseminadores”.

  
  

• Se você pensar bem, a Internet é simplesmente uma rede gigantesca de diferentes sites. Os mecanismos de pesquisa utilizam medidas de gráfico de conhecimento para retornar as páginas mais relevantes para uma consulta de pesquisa específica.

  
  

Por mais divertidos que sejam, é importante observar que os gráficos de rede apresentam desvantagens quando empregados na produção. Por exemplo, eles podem consumir muitos recursos. Como é o caso de qualquer operação de matriz, a escalabilidade e o desempenho às vezes são prejudicados. Há também um problema de “inicialização a frio” – se o seu conjunto de dados for muito esparso ou não houver muitos relacionamentos entre entidades, um gráfico de rede não é uma solução eficaz. Usados corretamente e no contexto certo, porém, podem ser valiosos para os negócios.