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.

Passeios, trilhos e caminhos

Um passeio (walk) num grafo é uma sucessão de lados adjacentes (com um vértice comum), sem qualquer outra restrição. É o que fazemos quando passeamos numa cidade, em que podemos repetir ruas, esquinas, etc.
Um trilho (trail) é um passeio em nenhum lado é percorrido mais que uma vez. Num passeio citadino, seria aquele que não passa duas vezes pela mesma rua.
Um caminho (path) é um passeio que não passa duas vezes pelo mesmo nó. Acharíamos estranho se alguém nos indicasse um caminho para um determinado ponto numa cidade que passasse duas vezes pela mesma esquina.
O caminho mais curto entre dois pontos é um caminho geodésico, e o seu comprimento é a distância entre os dois pontos.
Um circuito é um caminho fechado, que se inicia e termina no mesmo nó ou vértice.

Nesta rede, por exemplo, temos
 - um passeio: 1 - 2 - 3 - 4 - 2 - 1
 - um trilho: 1 - 2 - 3 - 4 - 6 - 2
 - um caminho: 1 - 2 - 3 - 4 - 5
 - um caminho geodésico: 1 - 6 - 5
 - um circuito: 1 - 2 - 4 - 6 - 1.

Medir os nós (2)

Uma medida muito interessante da centralidade da posição de um nó na rede é a chamada centralidade de proximidade, que no fundo visa indicar se esse nó estará mais ou menos próximo dos restantes nós da rede.
Mede-se muito simplesmente calculando o inverso da soma das distâncias do nó em causa aos restantes nós da rede.

Nesta rede, por exemplo, o nó 3 está à distância 1 dos nós 1, 2 e 4, à distância 2 do nó 5 e à distância 3 do nó 6, e somando estas distâncias obtém-se 1 + 1 + 1 + 2 + 3 = 8, e o seu inverso 0.125 é a sua centralidade de proximidade.
Este valor é frequentemente normalizado para ficar independente do tamanho da rede. Como numa rede com N nós, a maior centralidade de proximidade se obtém quando um nó está à distância 1 de todos os restantes, e vale 1/(N - 1), pode-se normalizar a centralidade de proximidade multiplicando aquele valor por N - 1. A centralidade de proximidade do nó 3 será assim 5 x 0.125 = 0.625, ou 62.5%.

Na rede do exemplo, o nó de maior centralidade de proximidade é o nó 4.

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.

Medir as redes (2)

Medir uma rede é olhar para uma rede de forma global, considerando todos os seus elementos em simultâneo.
Uma medida muito interessante é a distribuição dos graus dos nós, a frequência (o número de vezes) com que cada grau ocorre.
Na rede "reportar a"

que já apresentamos, temos 21 nós e uma distribuição curiosa dos graus in e out

n	16	0	1	1	2	0	0	1	0
Grau in	0	1	2	3	4	5	6	7	8

n	1	20	0	0	0	0	0	0	0
Grau out	0	1	2	3	4	5	6	7	8

No que respeita ao grau in, há um único nó com o grau in mais elevado, e que será em princípio o nó com maior prestígio, e no que se refere ao grau out há uma distribuição quase uniforme, com todos os nós excepto um com grau idêntico.

Em redes com um número elevado de nós, estas distribuições guardam muita informação sobre a sua natureza.

Medir os nós (1)

Numa rede, estamos muitas vezes interessados em determinar o nó mais influente, mais poderoso, mais importante, melhor colocado, etc. Estas medidas não são simples, e não há uma resposta única para todas estas questões.
A métrica mais simples consistirá em contar o número de ligações com origem ou destino em cada nó, o chamado grau de cada nó.
Numa rede direccionada, há o grau out, número de ligações com origem no nó em causa, e o grau in, número de ligações que incidem nesse nó, sendo evidente que numa rede não direccionada estes dois graus coincidem.
Por exemplo na rede social do Twitter, o grau out de um nó mede o número de amigos que esse elemento segue, enquanto que o grau in mede o número de amigos que seguem esse elemento, e parece claro que este último será o valor que devemos associar ao prestígio de cada elemento da rede.
Numa rede de citações, será igualmente o grau in que medirá a importância de um determinado artigo. (esta métrica é demasiado simplista e sujeita a fraude de uma forma simples, pelo que se usam outras métricas mais resistentes, que referiremos mais tarde)
A rede a seguir é disponibilizada pelo SocNetV e representa a relação "reportar a" numa empresa tecnológica.

Se pensarmos bem, a pessoa mais "importante" não reporta a ninguém (nó 7) pelo que terá o grau out 0, mas não tem necessariamente o grau in mais elevado. O grau in de um elemento indicará o número de pessoas que reportam a esse elemento, e poderá não medir directamente a sua importância na empresa.

Este exemplo é muito interessante.

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

Medir as redes (1)

A ordem de uma rede é o número de vértices da rede
     N = |V|.
O tamanho de uma rede é o número de arestas da rede
     S = |E|.
A densidade de uma rede é a razão entre o número de arestas da rede e o número máximo de arestas que a rede poderia ter se todos os vértices estivessem ligados entre si
     d = S / Smax
sendo
     Smax = N (N - 1).
Numa rede não direccionada as arestas (i, j) e (j, i) aparecem muitas vezes fundidas num único lado, pelo que é preciso todo o cuidado nesta contabilidade. Ou se multiplica por dois o número de lados ou se divide por dois o número máximo de lados.
Exemplo:
Qual será a densidade desta rede?

A rede tem 5 vértices e 6 arestas
     N = 5
     S = 6
e a densidade é
     d = 6 / 20 = 0.3 = 30%

Vértices e arestas, nós e lados, actores e interacções

Uma rede é um conjunto de vértices, nós, actores, entre os quais estão definidos arestas, lados, relações, interacções. Esta multiplicidade de nomes tem a ver com a riqueza de situações em que o paradigma da rede se verifica.
Formalmente, uma rede é constituída por um conjunto não vazio de vértices V e um conjunto de arestas E.

Nesta rede muito simples
     V = {1, 2, 3, 4, 5}
     E = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (4, 5)}.
Cada aresta é um par ordenado de dois vértices, a origem e o destino da relação ou interacção.
Podemos facilmente imaginar relações em que se (i, j) constituem uma aresta, então (j, i) também. São relações bidireccionais, ou não direccionadas. A relação de amizade no Facebook, ou uma rua com os dois sentidos de circulação, são relações bidireccionais. Seguir alguém no Twitter, passar uma bola num jogo de futebol, não são.
Numa rede, podem coexistir relações dos dois tipos
     V = {1, 2, 3, 4, 5}
     E = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 2), (3, 4), (4, 5), (5, 4)}.

Quando numa rede todas as relações são não direccionadas, e desde que tal seja claro, podemos omitir as setas com a indicação da direcção da relação na figura que a representa.

Bem vindos!

Mais um blogue? Sim!

Mas este vai ser um blogue com pouca opinião e muita interacção.
Pretendemos estudar e discutir redes, das mais simples às mais complexas, sem medo de as tratar da forma mais adequada e de usar ferramentas que ajudem nessa tarefa.
As redes são parte integrante da nossa vida e da nossa caminhada civilizacional.
Das redes marítimas aos caminhos de ferro, aos telefones, aos computadores, à Internet, cada vez mais funcionamos em rede.
O novo paradigma é a rede, não é a estrutura hierárquica tradicional, nas empresas e na sociedade.
E, em consequência, será cada vez mais difícil compreender o funcionamento destes sistemas, complexos, com muitos graus de liberdade, altamente dinâmicos e evolutivos.
É este o desafio.

Comunidades na rede dos amigos do autor no Facebook.

Olharemos para as redes, suas definições, representações, métricas, modelos de formação, comunidades, dinâmicas, e outros fenómenos que nos podem ajudar a estudar e interpretar redes.

Sigam-nos, e questionem-nos!