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.