Medir os nós (3)

Outra medida de centralidade muito utilizada é a chamada centralidade de intermediaridade (betweenness). Conta o número de caminhos geodésicos que passam por um determinado nó. A um nó de grande centralidade de intermediaridade associa-se uma posição estratégica no que respeita ao tráfego no interior da rede.
Nesta rede, por exemplo, o nó 4 tem centralidade de intermediação 6, que corresponde a todos os caminhos geodésicos entre um dos três nós do seu lado esquerdo e um dos dois nós do seu lado direito: 6 = 3x2.

Este valor pode ser normalizado, dividindo pelo número máximo de caminhos geodésicos possíveis entre os restantes N - 1 nós, ou seja 10 = 5x4/2, neste caso. A centralidade de intermediaridade normalizada do nó 4 é assim 6/10 = 0.6 = 60%.
Aprofundando um pouco mais, podemos ver o que nos diz o SocNetV:

Confirma-se o resultado para o nó 4, e os resultados para os 1, 5 e 6 são facilmente entendíveis.
Os nós 2 e 3 têm centralidade de intermediaridade 1.5, porque entre os nós 1 e 4 (ou 1 e 5 ou 1 e 6) há dois caminhos geodésicos, um que passa pelo nó 2 e outro que passa pelo nó 3, e nesse caso aplica-se o princípio da igual probabilidade.

Distância, excentricidade e diâmetro

A distância entre dois nós é medida pelo número mínimo de lados que é necessário percorrer para chegar de um nó ao outro (distância geodésica). Numa rede direccionada, cada lado só pode ser percorrido no sentido permitido.
A excentricidade de um nó é a distância (geodésica) entre esse nó e o nó mais afastado onde se pode chegar partindo do nó em causa.
Por exemplo, nesta rede

o nó 1 tem excentricidade 3, pois tem o nó 5 à distância 3 (dois caminhos: 1 - 2 - 4 - 5 e 1 - 3 - 4 - 5), os nós 2 e 3 têm excentricidade 2, o nó 4 tem excentricidade 1 (do nó 4 só se pode chegar ao nó 5) e o nó 5 tem excentricidade 0 (de 5 não se chega a nenhum outro nó).
A maior distância é o diâmetro da rede, neste caso, 3.
Podemos ver o relatório produzido pelo software SocNetV

De notar a simplicidade com que podemos calcular estes valores com o recurso a software apropriado.

Software (1)

Há ferramentas de software muito interessantes para análise de redes.

Já foram muito populares Ucinet/Netdraw e Pajek, e mais recentemente NodeXL e Gephi, esta última considerada a mais poderosa. Todas acabaram por definir formatos próprios para os ficheiros de dados, que se foram tornando standards de facto.

Uma ferramenta de software que uso regularmente, SocNetV, usa como formato nativo a norma .graphml, e recomendo vivamente a sua utilização.

Importa e exporta outros formatos, e disponibiliza uma selecção de métodos de análise e de visualização adequados a muitas situações.
Numa fase de aprendizagem, a introdução/eliminação manual de vértices/arestas é muito útil.
Utilizaremos todas estas, e não só.

Referências:

 - Kalamaras D. Social Network Visualizer (SocNetV). Social network analysis and visualization software. Home page: http://socnetv.sourceforge.net
 - Francisco Restivo's recommended sites. Tools. https://sites.google.com/site/frestivo/networked-life/tools