Matriz de adjacências (1)

Em Matemática, uma matriz é uma entidade constituída por um conjunto bidimensional de valores arrumados num número finito de linhas e colunas, sendo Aij o valor que se encontra na linha i e na coluna j.
Uma rede ou um grafo com N vértices podem ser representados por uma matriz quadrada com N linhas e N colunas, significando Aij = 1 que existe um lado orientado do vértice i para o vértice j e Aij = 0 que não existe.
Pegando nesta rede, por exemplo

percebe-se facilmente a sua relação com esta matriz 6x6

Esta matriz diz-se a matriz de adjacências da rede em causa. Assinala os vértices que são adjacentes. Se a matriz é simétrica relativamente à sua diagonal então os lados são simétricos (sem direcção).
Por outro lado, esta representação suporta lados múltiplos e mesmo anéis (lados que ligam um nó a ele próprio).

Medir os nós (4)

O grau de um nó, ou o grau in de um nó numa rede direccionada, mede de certa forma a popularidade ou o prestígio do nó. Numa rede de artigos ou autores científicos relacionados pelas citações, seria o número de citações do artigo ou do autor.
Nem todas os lados da rede terão o mesmo valor. Uma citação de um autor com muitas citações valerá mais que uma citação de um autor não citado. Faz assim sentido considerar que cada lado vale para o nó incidente o valor do nó de onde emerge.
Este cálculo fica um pouco complicado pois como se imagina facilmente o valor de um nó passa a depender do valor de todos os outros, de uma forma iterativa.
Um método de cálculo destes valores consiste em atribuir um valor inicial a cada nó (por exemplo a sua centralidade de grau), calcular os valores corrigidos dos graus, e repetir iterativamente ou um número definido de vezes ou até se atingir uma situação de estabilidade.

Neste exemplo, para cada nó indicam-se as primeiras três iterações, a primeira correspondente ao grau in de cada nó (1, 2, 2, 3, 2, 3), a segunda em que os nós contribuem com os valores da primeira iteração (3, 4, 5, 7, 6, 6), a terceira em que os nós contribuem com os valores da segunda (6, 9, 11, 15, 13, 16), e assim sucessivamente.

Estes valores, normalizados para uma soma dos graus igual a 1, vai tender para o vector próprio (eigenvector) da matriz de adjacências do grafo correspondente ao maior eigenvalue, daí ser conhecida por centralidade de eigenvector.

Numa das próximas publicações tentaremos explicar de uma forma simples de que se trata.

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.

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.

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.