Gráficos de ciência de dados com Python/NetworkX

Estamos inundados de dados. Bancos de dados e planilhas em constante expansão estão repletos de insights de negócios ocultos. Como podemos analisar dados e extrair conclusões quando há tanto deles? Gráficos (redes, não gráficos de barras) fornecem uma abordagem elegante.

Muitas vezes usamos tabelas para representar informações de forma genérica. Mas os gráficos usam uma estrutura de dados especializada: em vez de uma linha de tabela, um nó representa um elemento. Uma aresta conecta dois nós para indicar seu relacionamento.

Essa estrutura de dados de gráfico nos permite observar dados de ângulos únicos, e é por isso que a ciência de dados de gráfico é usada em todos os campos, desde a biologia molecular até as ciências sociais:

Então, como os desenvolvedores podem aproveitar a ciência de dados gráficos? Vamos nos voltar para a linguagem de programação de ciência de dados mais usada: Python.

Introdução aos gráficos de “teoria dos grafos” em Python

Os desenvolvedores de Python têm várias bibliotecas de dados de gráficos disponíveis para eles, como NetworkX, igraph, SNAP e graph-tool. Prós e contras à parte, eles têm interfaces muito semelhantes para manipular e processar estruturas de dados de gráficos Python.

Usaremos a popular biblioteca NetworkX. É simples de instalar e usar e suporta o algoritmo de detecção de comunidade que usaremos.

Criar um novo gráfico com o NetworkX é simples:

 import networkx as nx G = nx.Graph()

Mas G ainda não é um grafo, sendo desprovido de nós e arestas.

Como adicionar nós a um gráfico

Podemos adicionar um nó à rede encadeando o valor de retorno de Graph() com .add_node() (ou .add_nodes_from() para vários nós em uma lista). Também podemos adicionar características ou atributos arbitrários aos nós passando um dicionário como parâmetro, como mostramos com o node 4 e o node 5 :

 G.add_node("node 1") G.add_nodes_from(["node 2", "node 3"]) G.add_nodes_from([("node 4", {"abc": 123}), ("node 5", {"abc": 0})]) print(G.nodes) print(G.nodes["node 4"]["abc"]) # accessed like a dictionary

Isso irá produzir:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5'] 123

Mas sem arestas entre os nós, eles são isolados e o conjunto de dados não é melhor do que uma tabela simples.

Como adicionar arestas a um gráfico

Semelhante à técnica para nós, podemos usar .add_edge() com os nomes de dois nós como parâmetros (ou .add_edges_from() para várias arestas em uma lista), e opcionalmente incluir um dicionário de atributos:

 G.add_edge("node 1", "node 2") G.add_edge("node 1", "node 6") G.add_edges_from([("node 1", "node 3"), ("node 3", "node 4")]) G.add_edges_from([("node 1", "node 5", {"weight" : 3}), ("node 2", "node 4", {"weight" : 5})])

A biblioteca NetworkX suporta gráficos como estes, onde cada aresta pode ter um peso. Por exemplo, em um gráfico de rede social onde os nós são usuários e as arestas são interações, o peso pode significar quantas interações acontecem entre um determinado par de usuários – uma métrica altamente relevante.

NetworkX lista todas as arestas ao usar G.edges , mas não inclui seus atributos. Se quisermos atributos de borda, podemos usar G[node_name] para obter tudo o que está conectado a um nó ou G[node_name][connected_node_name] para obter os atributos de uma borda específica:

 print(G.nodes) print(G.edges) print(G["node 1"]) print(G["node 1"]["node 5"])

Isso irá produzir:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5', 'node 6'] [('node 1', 'node 2'), ('node 1', 'node 6'), ('node 1', 'node 3'), ('node 1', 'node 5'), ('node 2', 'node 4'), ('node 3', 'node 4')] {'node 2': {}, 'node 6': {}, 'node 3': {}, 'node 5': {'weight': 3}} {'weight': 3}

Mas ler nosso primeiro gráfico dessa maneira é impraticável. Felizmente, há uma representação muito melhor.

Como gerar imagens de gráficos (e gráficos ponderados)

A visualização de um gráfico é essencial: permite ver as relações entre os nós e a estrutura da rede de forma rápida e clara.

Basta uma chamada rápida para nx.draw(G) :

Vamos tornar as arestas mais pesadas correspondentemente mais grossas por meio de nossa chamada nx.draw() :

 weights = [1 if G[u][v] == {} else G[u][v]['weight'] for u,v in G.edges()] nx.draw(G, width=weights)

Fornecemos uma espessura padrão para arestas sem peso, como visto no resultado:

Nossos métodos e algoritmos de gráfico estão prestes a ficar mais complexos, então o próximo passo é usar um conjunto de dados mais conhecido.

Gráfico de ciência de dados usando dados do filme Star Wars: Episódio IV

Para facilitar a interpretação e compreensão de nossos resultados, usaremos esse conjunto de dados. Os nós representam personagens importantes e as arestas (que não são ponderadas aqui) significam coaparência em uma cena.

Nota: O conjunto de dados é de Gabasova, E. (2016). Rede social de Guerra nas Estrelas. DOI: https://doi.org/10.5281/zenodo.1411479.

Primeiro, vamos visualizar os dados com nx.draw(G_starWars, with_labels = True) :

Personagens que geralmente aparecem juntos, como R2-D2 e C-3PO, aparecem intimamente conectados. Em contrapartida, podemos ver que Darth Vader não compartilha cenas com Owen.

Layouts de visualização do Python NetworkX

Por que cada nó está localizado onde está no gráfico anterior?

É o resultado do algoritmo spring_layout padrão. Ele simula a força de uma mola, atraindo nós conectados e repelindo os desconectados. Isso ajuda a destacar nós bem conectados, que terminam no centro.

O NetworkX tem outros layouts que usam critérios diferentes para posicionar nós, como circular_layout :

 pos = nx.circular_layout(G_starWars) nx.draw(G_starWars, pos=pos, with_labels = True)

O resultado:

Esse layout é neutro no sentido de que a localização de um nó não depende de sua importância – todos os nós são representados igualmente. (O layout circular também pode ajudar a visualizar componentes conectados separados - subgrafos com um caminho entre quaisquer dois nós - mas aqui, o gráfico inteiro é um grande componente conectado.)

Ambos os layouts que vimos têm um grau de desordem visual porque as arestas são livres para cruzar outras arestas. Mas Kamada-Kawai, outro algoritmo direcionado por força como spring_layout , posiciona os nós de forma a minimizar a energia do sistema.

Isso reduz o cruzamento de bordas, mas tem um preço: é mais lento do que outros layouts e, portanto, não é altamente recomendado para gráficos com muitos nós.

Este tem uma função de desenho especializada:

 nx.draw_kamada_kawai(G_starWars, with_labels = True)

Isso produz esta forma em vez disso:

Sem nenhuma intervenção especial, o algoritmo colocou os personagens principais (como Luke, Leia e C-3PO) no centro e os menos proeminentes (como Camie e General Dodonna) na fronteira.

Visualizar o gráfico com um layout específico pode nos dar alguns resultados qualitativos interessantes. Ainda assim, os resultados quantitativos são uma parte vital de qualquer análise de ciência de dados, portanto, precisaremos definir algumas métricas.

Análise de nós: grau e PageRank

Agora que podemos visualizar nossa rede com clareza, pode ser de nosso interesse caracterizar os nós. Existem várias métricas que descrevem as características dos nós e, em nosso exemplo, dos personagens.

Uma métrica básica para um nó é seu grau: quantas arestas ele possui. O grau do nó de um personagem de Star Wars mede com quantos outros personagens eles compartilharam uma cena.

A função degree() pode calcular o grau de um caractere ou de toda a rede:

 print(G_starWars.degree["LUKE"]) print(G_starWars.degree)

A saída de ambos os comandos:

 15 [('R2-D2', 9), ('CHEWBACCA', 6), ('C-3PO', 10), ('LUKE', 15), ('DARTH VADER', 4), ('CAMIE', 2), ('BIGGS', 8), ('LEIA', 12), ('BERU', 5), ('OWEN', 4), ('OBI-WAN', 7), ('MOTTI', 3), ('TARKIN', 3), ('HAN', 6), ('DODONNA', 3), ('GOLD LEADER', 5), ('WEDGE', 5), ('RED LEADER', 7), ('RED TEN', 2)]

A classificação dos nós do maior para o menor de acordo com o grau pode ser feita com uma única linha de código:

 print(sorted(G_starWars.degree, key=lambda x: x[1], reverse=True))

A saída:

 [('LUKE', 15), ('LEIA', 12), ('C-3PO', 10), ('R2-D2', 9), ('BIGGS', 8), ('OBI-WAN', 7), ('RED LEADER', 7), ('CHEWBACCA', 6), ('HAN', 6), ('BERU', 5), ('GOLD LEADER', 5), ('WEDGE', 5), ('DARTH VADER', 4), ('OWEN', 4), ('MOTTI', 3), ('TARKIN', 3), ('DODONNA', 3), ('CAMIE', 2), ('RED TEN', 2)]

Sendo apenas um total, o grau não leva em consideração detalhes de arestas individuais. Uma determinada borda se conecta a um nó isolado ou a um nó que está conectado a toda a rede? O algoritmo PageRank do Google agrega essas informações para avaliar a “importância” de um nó em uma rede.

A métrica PageRank pode ser interpretada como um agente movendo-se aleatoriamente de um nó para outro. Os nós mais bem conectados têm mais caminhos passando por eles, então o agente tenderá a visitá-los com mais frequência.

Esses nós terão um PageRank mais alto, que podemos calcular com a biblioteca NetworkX:

 pageranks = nx.pagerank(G_starWars) # A dictionary print(pageranks["LUKE"]) print(sorted(pageranks, key=lambda x: x[1], reverse=True))

Isso imprime a classificação de Luke e nossos personagens classificados por classificação:

 0.12100659993223405 ['OWEN', 'LUKE', 'MOTTI', 'DODONNA', 'GOLD LEADER', 'BIGGS', 'CHEWBACCA', 'LEIA', 'BERU', 'WEDGE', 'RED LEADER', 'RED TEN', 'OBI-WAN', 'DARTH VADER', 'CAMIE', 'TARKIN', 'HAN', 'R2-D2', 'C-3PO']

Owen é o personagem com o PageRank mais alto, superando Luke, que tinha o maior grau. A análise: Embora Owen não seja o personagem que mais compartilha cenas com outros personagens, ele é um personagem que compartilha cenas com muitos personagens importantes como o próprio Luke, R2-D2 e C-3PO.

Em maior contraste, C-3PO, o personagem com o terceiro grau mais alto, é aquele com o PageRank mais baixo. Apesar do C-3PO ter muitas conexões, muitas delas são com personagens sem importância.

A conclusão: o uso de várias métricas pode fornecer informações mais detalhadas sobre as diferentes características dos nós de um gráfico.

Algoritmos de Detecção da Comunidade

Ao analisar uma rede, pode ser importante separar as comunidades : grupos de nós altamente conectados entre si, mas minimamente conectados com nós fora de sua comunidade.

Existem vários algoritmos para isso. A maioria deles é encontrada em algoritmos de aprendizado de máquina não supervisionados porque atribuem um rótulo aos nós sem a necessidade de que eles tenham sido rotulados anteriormente.

Uma das mais famosas é a propagação de rótulos . Nele, cada nó começa com um rótulo único, em uma comunidade de um. Os rótulos dos nós são atualizados iterativamente de acordo com a maioria dos rótulos dos nós vizinhos.

Os rótulos se difundem pela rede até que todos os nós compartilhem um rótulo com a maioria de seus vizinhos. Grupos de nós intimamente conectados entre si acabam tendo o mesmo rótulo.

Com a biblioteca NetworkX, a execução desse algoritmo leva apenas três linhas de Python:

 from networkx.algorithms.community.label_propagation import label_propagation_communities communities = label_propagation_communities(G_starWars) print([community for community in communities])

A saída:

 [{'R2-D2', 'CAMIE', 'RED TEN', 'RED LEADER', 'OBI-WAN', 'DODONNA', 'LEIA', 'WEDGE', 'HAN', 'OWEN', 'CHEWBACCA', 'GOLD LEADER', 'LUKE', 'BIGGS', 'C-3PO', 'BERU'}, {'DARTH VADER', 'TARKIN', 'MOTTI'}]

Nesta lista de conjuntos, cada conjunto representa uma comunidade. Leitores familiarizados com o filme perceberão que o algoritmo conseguiu separar perfeitamente os “mocinhos” dos “bandidos”, diferenciando os personagens de forma significativa sem usar nenhum rótulo ou metadados verdadeiros (comunidade).

Insights inteligentes usando o Graph Data Science em Python

Vimos que começar com ferramentas de ciência de dados gráficos é mais simples do que parece. Uma vez que representamos os dados como um gráfico usando a biblioteca NetworkX em Python, algumas linhas curtas de código podem ser esclarecedoras. Podemos visualizar nosso conjunto de dados, medir e comparar características de nós e agrupar nós de forma sensata por meio de algoritmos de detecção de comunidade.

Ter a habilidade de extrair conclusões e insights de uma rede usando Python permite que os desenvolvedores se integrem a ferramentas e metodologias comumente encontradas em pipelines de serviços de ciência de dados. De mecanismos de busca a programação de voos e engenharia elétrica, esses métodos se aplicam facilmente a uma ampla variedade de contextos.

Leitura recomendada em Graph Data Science

Algoritmos de Detecção da Comunidade
Zhao Yang, Rene Algesheimer e Claudio Tessone. “Uma Análise Comparativa de Algoritmos de Detecção de Comunidades em Redes Artificiais.” Relatórios Científicos, 6, n. 30750 (2016).

Aprendizado profundo de gráficos
Thomas Kipf. “Gráfico de Redes Convolucionais”. 30 de setembro de 2016.

Aplicações de Graph Data Science
Albanese, Federico, Leandro Lombardi, Esteban Feuerstein e Pablo Balenzuela. “Prevendo indivíduos em mudança usando mineração de texto e aprendizado de máquina de gráficos no Twitter.” (24 de agosto de 2020): arXiv:2008.10749 [cs.SI].

Cohen, Elior. “Encontro PyData Tel Aviv: Node2vec.” YouTube. 22 de novembro de 2018. Vídeo, 21:09. https://www.youtube.com/watch?v=828rZgV9t1g.