Análise de Redes: Rodovias da Europa
A análise de redes pode ser resumidamente definida como um conjunto de técnicas integradas que proporcionam a capacidade de estimar padrões complexos de relacionamentos de uma maneira mais simplificada através da utilização de grafos, permitindo descobrir características importantes dessa rede.
Existem diversas campos de estudo que podemos aplicar técnicas de análise de redes, onde podemos destacar aplicações relacionadas a análise de redes sociais (que mapeia relacionamentos entre indivíduos numa rede social, ou organizações), redes biológicas, redes de ligações, redes temporais, redes de rotas, entre outros.
Neste artigo, vamos estudar sobre análise de redes aplicada em redes de estradas, onde apresentaremos um estudo de caso bastante interessante: as rodovias que conectam as cidades da Europa. Na sequência desse artigo, vamos abordar os seguintes tópicos: base de dados do estudo de caso, pré-processamento e construção do arquivo graphml, informações sobre a topologia da rede criada, e análise de métricas.
Base de dados
A base de dados utilizada inclui a presença de dois arquivos csv. O primeiro deles informa todas as conexões (arestas do grafo) entre as cidades da Europa que possuem rodovias entre elas, onde essas conexões estão expressas através de números inteiros (IDs). A figura abaixo mostra as cinco primeiras linhas deste arquivo.
Nessa figura, a primeira linha informa que a cidade com ID 0 possui uma estrada conectada diretamente com a cidade com ID 1. A terceira linha informa que a cidade com ID 1 está diretamente conectada com a cidade com ID 16, e assim por diante.
O segundo CSV indica inicialmente qual é a cidade representada por cada ID e uma segunda coluna informa um par de coordenadas que indica a posição dessa cidade no mapa. A figura abaixo mostra um exemplo das cinco primeiras linhas desse arquivo.
Essa base de dados é pública e está disponível no seguinte link, onde é possível realizar o download dos dois arquivos csv mencionados e de outras informações sobre o tema.
Pré-processamento
Com o objetivo de deixar as informações padronizadas em um determinado formato, inicialmente precisamos realizar um pré-processamento das informações contidas na base de dados. Nesse artigo, vamos utilizar Python, Pandas e Network x para realizar essas modificações e construir o grafo que vai relacionar as rodovias com as cidades.
O primeiro passo do pré-processamento consiste em substituir os IDs dos nós mostrados na Figura 1 pelos nomes das suas respectivas cidades. Assim, quando construirmos a imagem do sistema, ficará mais fácil de identificar as cidades mais importantes (ou seja, aquelas que possuem mais rodovias que ligam outras cidades). Resumidamente, para realizar essa tarefa, criamos um dicionário que relaciona cada ID com o nome cidade e atualizamos as colunas source e target em função desse dicionário. Como resultado, as linhas mostradas na Figura 1 ficaram da seguinte forma:
Em seguida, criamos o Grafo a partir desse DataFrame recém construído utilizando as seguintes linhas de código:
import networkx as nxG = nx.Graph()
G = nx.from_pandas_edgelist(edges, 'source', 'target')
No qual edges representa o DataFrame com as conexões entre as cidades que possuem rodovias.
O próximo passo consiste em adicionar as informações das coordenadas de cada cidade (mostradas na Figura 2) para cada um dos nós do grafo (que representam cidades). Nesse ponto, foi necessário realizar alguns processamentos envolvendo Strings, visto que as informações das posições x e y de cada cidade estavam sendo interpretadas como sendo Strings. Após realizar esse processamento, criamos dois dicionários que relacionam cada cidade com as posições x e y (novos atributos de cada um dos nós). O código abaixo resume esse procedimento:
pos_string = [s[7:-2].split(', ') for s in edges.pos.tolist()]
x = [float(s[0])*-2000 for s in pos_string]
y = [float(s[1])*-2000 for s in pos_string]cities_pos_x = dict(zip(edges.meta, x))
cities_pos_y = dict(zip(edges.meta, y))nx.set_node_attributes(G, cities_pos_x, "x")
nx.set_node_attributes(G, cities_pos_y, "y")
Finalmente, nesse ponto, concluímos o pré-processamento do grafo. Então, salvamos o grafo em um arquivo do tipo graphml com o objetivo de analisá-lo em um outro software. O comando para salvar o grafo está mostrado no bloco abaixo:
nx.write_graphml(G, "euroroad.graphml")Nesse caso, o nome do arquivo salvo será euroroad.graphml.
Topologia da rede e métricas
Para visualizar e interpretar melhor as informações da rede deste artigo, vamos inicialmente utilizar o programa chamado Gephi, uma ferramenta open-source e gratuita que ajuda a realizar a visualização e a exploração de grafos e redes.
Ao iniciar um novo projeto com o arquivo criado na subseção anterior, o programa já informa algumas informações do grafo, conforme mostrado na Figura abaixo:
Dessa forma, nessa aplicação, existem 1174 nós e 1417 arestas. Ou seja, a nossa base de dados possui 1174 cidades e existem 1417 rodovias que ligam essas cidades.
A primeira métrica que vamos aplicar é chamada de modularidade, que mede a força da divisão de uma rede em módulos (também chamados de grupos, clusters ou comunidades). Redes com um alto valor de modularidade têm conexões densas entre os nós dentro dos módulos, mas conexões esparsas entre nós em módulos diferentes, reforçando a ideia de que os módulos estão bem definidos.
No nosso grafo, foram encontrados 46 comunidades e o valor da modularidade foi de 0.87. Assim, como temos um alto valor de modularidade (o máximo é 1), podemos interpretar que as conexões dentro dos módulos são densas e fora dos módulos são esparsas.
Em seguida, fizemos as seguintes modificações para melhorar a visualização do grafo:
- Configuramos uma cor distinta para cada uma das comunidades que possuem pelo menos 6 elementos.
- Aumentamos o tamanho da representação de cada nó em função do seu grau de centralidade. Ou seja, quanto maior o número de conexões do nó, maior será o seu tamanho.
- Inserimos um filtro para mostrar os nomes das cidades que possuem no mínimo 8 conexões.
Assim, após realizarmos essas conexões, temos o resultado mostrado na Figura abaixo.
Através dessa figura, é possível obter diversas informações! Por isso a importância de realizar o estudo da análise de redes, além de mostrar de uma maneira bem intuitiva sobre as informações das rotas.
A cidade Moscow está escrita com a maior fonte de todas, e isso não é a toa. Essa cidade o maior grau de centralidade, visto que possui estradas que conectam com outras 10 cidades! Paris, Liège, Berlim, Munique e Budapeste também se destacam com 8 conexões. Metz, Praga, Viena, Bratislava e Warsaw possuem 7 conexões.
Outro ponto interessante é ver como ficaram as distribuições das cores para cada nó. Nesse caso, cada cor poderia inclusive representar um país diferente (ou estado, dependendo do tamanho do país).
No Gephi, é possível customizar o grafo mostrado de qualquer forma que o programador quiser, alterando a quantidade de nós mostrados, a cor, o tamanho, etc. Para exemplificar, considere a imagem abaixo, onde foi filtrado todas os nós que possuem um grau de centralidade menor que 0,6 (6 conexões).
Agora, vamos fazer a análise da métrica chamada clustering, que pode ser entendida como sendo uma medida do grau que as conexões de um determinado nó fazem entre si. Para ilustrar melhor o funcionamento dessa métrica, considere a Figura 7.
A cidade de Londres possui conexões com outras 5 cidades. Porém, nenhuma dessas cidades fazem conexões entre elas. Dessa forma, o coeficiente de clustering será igual a 0 para o nó que representa Londres. Inclusive, quando temos um valor nulo para este coeficiente, dizemos que a topologia da rede é em estrela. Se todas as outras cidades tivessem conexões entre elas, então, o coeficiente de clustering seria igual a 1.
Para computar o coeficiente de clustering do sistema, deve-se calcular esse valor para cada um dos nós do grafo e então realizar a média. Fazendo essa operação para o grafo apresentado nesse artigo, temos o valor de 0.01673.
Esse valor baixo do coeficiente de clustering é esperado para a aplicação que está sendo abordada neste artigo. Ou seja, em geral, não é necessário que exista diversas rodovias ligando uma mesma cidade. No próprio caso de Londres, mostrado na figura 7, não existe a necessidade de ter uma estrada ligando diretamente Colchester com NewCastle, por exemplo. Se alguém quiser se deslocar de uma cidade para a outra, basta seguir o rodovia que passa por Londres que vai conseguir chegar ao seu destino. Essa ideia vale para a maioria das outras cidades, não só na Europa, mas em todo o mundo.
Uma outra forma de analisar esse coeficiente é apresentado na Figura 8, que representa um histograma com a quantidade de nós em função do valor do clustering. Como era esperado, a grande maioria dos nós possuem um baixo clustering, enquanto que algumas amostras possuem um valor entre 0.2 e 0.4 e uma quantidade ainda menor está entre 0.8 e 1.0.
O código utilizado para realizar todos os cálculos e as figuras deste artigo está disponibilizado no meu Github. Sinta-se livre para reproduzir os resultados mostrados nesse artigo e também fazer qualquer modificação e adaptação para outras aplicações.
Um vídeo resumindo o que foi discutido nesse artigo pode ser visualizado através desse link: https://bit.ly/3nv6WEX
Conclusão
Este artigo apresentou um estudo de caso para a aplicação de análise de redes, que consiste em uma rede de rotas das rodovias da Europa. Vimos, inicialmente, como realizar algumas etapas de pré-processamento para que o grafo ficasse padronizado em um determinado formato.
Em seguida, trabalhamos com o Gephi, um software bastante interessante para a visualização e manipulação de grafos. Através deste programa, foi possível construir figuras e calcular algumas métricas, como o grau de modularidade e o grau de centralidade, que nos ajudaram a entender melhor a nossa aplicação.
Por fim, discutimos uma outra métrica, chamada de coeficiente de clustering, que indica o grau de conexão entre os nós do grafo. Nesse estudo de caso que envolve uma rede de rotas, esse coeficiente é bastante próximo de zero, visto que, na maioria dos casos, não é necessário existir diversos caminhos diferentes para uma mesma cidade.
Espero que vocês tenham compreendido um pouco mais da aplicação de análise de redes com o exemplo mostrado neste artigo. Existem diversas outras aplicações bastante interessantes e que são de extrema importância para questões sociais e até mesmo de marketing.
Até a próxima!
