As redes estão por toda parte: a infraestrutura de tráfego e a Internet vêm à mente, mas as redes também estão na natureza: cadeias alimentares, redes de interação com proteínas, redes de interação genética e, claro, redes neurais que estão sendo modeladas pelas Redes Neurais Artificiais.
Neste post, criaremos uma pequena rede (também chamada gráfico matematicamente) e faça alguma pergunta sobre qual é o nó “mais importante” (também chamado vérticepl. vértices) Se você deseja entender conceitos importantes de centralidade da rede e como calcular aqueles em R, continue lendo!
Esta publicação é baseada em uma publicação do LinkedIn pelo renomado cientista de dados Dr. Keith McNulty. Vamos (re) criar a pequena rede de exemplo a partir daí, definindo primeiro o matriz de adjacência e depois plotá-lo com o igraph pacote (no CRAN). Já usamos este pacote em outro post nas redes: o Eigenvector do Google … ou como um Random Surfer encontra as páginas da Web mais relevantes.
library(igraph) ## Warning: package 'igraph' was built under R version 4.0.2 ## ## Attaching package: 'igraph' ## The following objects are masked from 'package:stats': ## ## decompose, spectrum ## The following object is masked from 'package:base': ## ## union # define simple network # A, B, C, D, E, F, G, H, I, J, K, L, M, N A
McNulty writes in his post:
I love to use this example when I teach about network analysis. I ask the group: who is the most important person in this network?
Now, what does “most important” person mean? It of course depends on the definition and this is where network centrality measures come into play. We will have a look at three of those (there are many more out there…).
Degree centrality
McNulty explains:
Degree centrality tells you the most connected person: it is simply the number of nodes connected to each node, and it’s easy to see that D has the highest (7).
This is often the only metric given to identify “influencers”: how many followers do they have?
Degree centrality is easy to calculate in R (first “by hand”, after that with the
igraphpackage):rowSums(A) ## A B C D E F G H I J K L M N ## 2 2 1 7 1 2 4 3 4 3 2 2 2 1 degree(g) ## A B C D E F G H I J K L M N ## 2 2 1 7 1 2 4 3 4 3 2 2 2 1Centralidade de proximidade
McNulty explica:
A centralidade de proximidade indica quem pode propagar as informações mais rapidamente: você soma os comprimentos do caminho do nó para o outro nó e depois o inverte. G possui quatro caminhos de comprimento 1, 6 de comprimento 2 e 3 de comprimento 3. O que lhe confere uma centralidade de proximidade de 1/25. Com os outros candidatos principais Eu é 1/26, H é 1/26 e D é 1/27.
Uma aplicação que vem à mente é a identificação dos chamados superespalhadores de doenças infecciosas, como o COVID-19.
Isso é um pouco mais complicado, a abordagem mais simples é primeiro converter a matriz de adjacência em um matriz de distância que mede as distâncias dos caminhos mais curtos de e para cada nó (não entrarei em detalhes, alguns ponteiros são dados nos comentários do código):
# exponentiate the n x n adjacency matrix to the n'th power in the min-plus algebra. This is, instead of adding taking the minimum and instead of multiplying taking the sum. # more details: https://en.wikipedia.org/wiki/Distance_matrix#Non-metric_distance_matrices # distance product "%C%"Betweenness centrality
McNulty explains:
Betweenness centrality tells you who is most important in maintaining connection throughout the network: it is the number of times your node is on the shortest path between any other pair of nodes. I uniquely connects all nodes on the left with all nodes on the right, which means it connects at 8×5 = 40 pairs, plus any node in the top right with the bottom right, a further 6 pairs, so 46 in total. If you follow a similar process for D, H and G you’ll see that they don’t come close to this.
For example in protein-interaction networks, betweenness centrality can be used to find important proteins in signalling pathways which can form targets for drug discovery.
The actual algorithm to calculate betweenness centrality is much too involved to show here (if you have a simple to understand algorithm please let me know on StackOverflow or in the comments), so we will just make use of the
igraphpackage to calculate it:betweenness(g) ## A B C D E F G H I J K L M N ## 0.0 0.0 0.0 41.5 0.0 0.0 21.5 15.0 46.0 22.0 0.0 0.0 12.0 0.0Como vimos, há mais de uma definição de "mais importante". Depende do contexto (e das informações disponíveis) qual escolher.
Por favor, deixe-me saber sua opinião nos comentários e compartilhe outras aplicações possíveis conosco.
Estamos aproveitando nossas férias de verão! Aguarde o próximo post em 6 de outubro de 2020 ... e mantenha-se saudável!
Relacionado
