Nós já vimos mais de uma forma de medirmos a importância de um nó na rede. A forma mais direta é pelo grau que mede a quantidade de conexões de um nó, mas podemos usar também o coeficiente de aglomeração deste nó, que vai dar uma medida da conectividade de sua vizinhança, indicando que este faz parte de uma comunidade. Neste post veremos uma forma diferente de medirmos a importância de um nó.
Considere o nó azul na rede abaixo. Observe que o grau deste nó é bem baixo (2) e o coeficiente de aglomeração é nulo, já que seus dois vizinhos não são vizinhos entre si. Contudo, o nó azul tem uma importância óbvia nesta rede que é manter as duas "partes" da rede conectadas entre si. Em outras palavras, o nó azul faz parte de todos os caminhos entre os 20 nós do lado esquerdo da rede para os 20 nós do lado direito da rede e vice-versa. Nesta rede, o nó azul será responsável por 400 caminhos (excetuando os caminhos em que ele é origem ou destino), e isso é metade da quantidade de caminhos na rede (note que consideramos o caminho entre os nós $i$ e $j$ apenas uma vez)!
Essa ideia de importância é capturada por uma medida de centralidade chamada de nível de intermediação (em inglês, betweenness), ou apenas intermediação. Para um nó $v$, a intermediação é definida como a soma da fração de menores caminhos que passam sobre o nó $v$ considerando os menores caminhos de todos os pares de nós.
Em outras palavras, obtemos o valor da intermediação considerando cada par de nós $i$ e $j$ (excetuando-se os caminhos em que $v$ é origem ou destino). Para cada par, verificamos quantos dos menores caminhos que ligam o par passam por $v$. Assim, se entre $i$ e $j$ temos dois menores caminhos e apenas um deles passa por $v$, assumimos 1/2 para este par de nós. A soma de todas estas frações é a intermediação.
Note-se que em grafos não-dirigidos computamos o caminho entre os nós $i$ e $j$ apenas uma vez, o que não ocorre se tivermos um digrafo.
Da forma que foi definido, a intermediação é um número absoluto. Contudo, é possível calcular um valor relativo de intermediação, tomando o valor absoluto e dividindo-o por $\frac{(n-1)(n-2)}{2}$, para grafos não-dirigidos, e $\frac{(n-1)(n-2)}{1}$ para digrafos.
Retornando a rede de exemplo. O nó azul possui, como dissemos, uma intermediação de 400, já que há apenas uma forma para que os nós da esquerda cheguem nos da direita e vice-versa que é passando pelo nó azul. Logo ele pertence a todos estes caminhos. Olhando de forma relativa, a intermediação do nó azul é de 0,51, aproximadamente.
Um detalhe importante nesta rede: a despeito de ter um alto valor de intermediação, você percebe que o nó azul não possui o maior nível de intermediação? Os nós que são seus vizinhos possuem um grau de intermediação um pouco maior (uma diferença entre 0,02-0,05, considerando a intermediação relativa).
Isso acontece porque estes outros dois nós fazem parte de todos os menores caminhos que o nó azul pertence, mas também pertencem a alguns outros menores caminhos dentro de sua própria parte da rede. Isso nos indica que as métricas não devem ser tomadas isoladamente, mas devem ser olhadas em conjunto para entendermos a importância de um nó na rede.
Comentários
Postar um comentário