Intermediação

A intermediação é uma medida de centralidade de um nó em uma rede. Ela é igual ao número de menores caminhos de todos os vértices para quaisquer outros vértices que passam por aquele nó. A intermediação é uma medida mais útil do que apenas a conectividade de um nó. A primeira é mais global para a rede, enquanto a segunda tem apenas um efeito local. O desenvolvimento da intermediação é geralmente atribuído ao sociólogo Linton Freeman, que também desenvolveu várias outras medidas de centralidade. A mesma ideia também foi proposta pelo matemático J. Anthonisse, embora seu trabalho nunca tenha sido publicado.

Ao longo dos últimos anos, a intermediação se tornou uma estratégia popular para lidar com redes complexas. As aplicações incluem redes sociais e de computadores, redes biológicas (tais como redes tróficas e de polinização), redes de transporte, redes de cooperação científica e outras.

Definição

A intermediação de um nó $v$ é dada pela expressão:

$g(v)=\sum _{s\ne v\ne t}\frac{{\sigma }_{st}(v)}{{\sigma }_{st}}$

onde ${\sigma }_{st}$ é o número total de menores caminhos do nó $s$ para o nó $t$ e ${\sigma }_{st}(v)$ é o número de menores caminhos que passam por $v$.

Vale salientar que a intermediação de um nó escala com o número de pares de nós, indicado pelo somatório dos índices. Portanto o cálculo pode ser redimensioado dividindo pelo número de pares de nós não incluindo $v$, de maneira que $g\in [0,1]$. A divisão é feita por $(N-1)(N-2)$ para grafos direcionados e por $(N-1)(N-2)/2$ para grafos não-direcionados, onde $N$ é o número de nós no componente grande. Nota-se que o valor escala para o máximo quando um nó é compartilhado por todos os menores caminhos. Este geralmente não é o caso, e a normalização pode ser realizada sem a perda de precisão

$\text{normal}(g(v))=\frac{g(v)-\min (g)}{\max (g)-\min (g)}$

que resulta em:

$\max (normal)=1$

$\min (normal)=0$

Este redimensionamento sempre será de uma faixa menor para uma faixa maior, logo não há perda de precisão.

Algoritmos

Calcular a intermediação e a proximidade de todos os vértices de um grafo envolve calcular os menores caminhos entre todos os pares de vértices do grafo. Isto leva um tempo $\mathrm{\Theta }(|V{|}^3)$ com o algoritmo de Floyd-Warshall, modificado para não apenas encontrar um mas contar todos os menores caminhos entre dois nós. Em grafos esparsos, algoritmo de Johnson pode ser mais eficiente, levando um tempo $O(|V{|}^2\log |V|+|V||E|)$. Em grafos sem peso, calcular a intermediação leva um tempo $O(|V||E|)$ usando o algoritmo de Brandes.

Ao se calcular a intermediação e a proximidade de todos os vértices de um grafo, se assume que o grafo é não-direcionado e suas conexões permitem laços e arestas múltiplas. Ao lidar especificamente com grafos complexos, por vezes os grafos não possuem laços ou arestas múltiplas de modo a manter as relações simples (onde as arestas representam conexões entre duas pessoas ou vértices). Neste caso, o algoritmo de Brandes divide o valor final por 2, considerando que cada menor caminho é contado duas vezes.

Predefinição:Tradução/ref