Redes com pesos

Até o momento nós apresentamos toda a teoria de redes considerando que os enlaces indicam a presença ou não de uma relação entre dois nós. Embora esta forma de modelagem de redes seja bastante útil para uma série de situações, há casos em que precisamos indicar algo mais sobre esta relação na forma de uma componente numérica que indique a intensidade ou a capacidade desta relação.

Para isso usamos os chamados grafos com pesos ou grafos valorados, em que cada enlace possui associado a si um número (normalmente, positivo) para indicar algum aspecto da realidade que queremos modelar. Um caso muito simples, em redes de transporte de energia, por exemplo, é utilizar os pesos para representar as distâncias entre os elementos do sistema. Maior distância, logo maior peso. Porém, é possível atribuir outros significados a este valor.

Note-se que ao usarmos grafos valorados, vários dos conceitos que já estudamos ganham novo significado. A Matriz de Adjacência é modificada profundamente, já que cada posição $a_{ij}$ da matriz indicará o peso do enlace que liga o nó $i$ ao nó $j$, se houver. Se não houver enlace entre $i$ e $j$ então $a_{ij} = 0$.

Também modificamos a forma como definimos o tamanho de um caminho. Ao invés de contarmos apenas o número de enlaces, somamos os pesos dos enlaces que pertencem ao caminho. Desta forma, o menor caminho será aquele que possuir a menor soma de pesos. 

Logicamente, isso também afeta outras métricas que dependem do menor caminho como o diâmetro da rede e o raio de cada nó. Esta mudança no grafo afetará também a Matriz de Caminhos, fazendo com que a relação desta com a matriz de adjacência se perca ($P = \min_{k=1..D}\{kA^k\}$ deixa ser válido). Por fim, a intermediação também é afetada, já que esta depende do cálculo dos menores caminhos em seu próprio cômputo.

Note-se que em grafos valorados devemos ter cuidado com o significados dos pesos. A modelagem de um certo parâmetro do mundo real como peso nos enlaces, pode descaracterizar medidas baseadas em caminhos. Por exemplo, no caso da rede de energia elétrica, se o peso de cada aresta indicar a tensão naquele enlace de transmissão, o cômputo dos menores caminhos baseados neste peso não terá um significado direto. 

Contudo, isso não quer dizer que este modelo não seja útil. Já que podemos usar este grafo com os valores de tensão para medir a força de um nó. Esta é uma medida de centralidade similar ao grau, mas que leva em consideração os pesos dos enlaces diretamente conectados ao nó, somando estes pesos para compor a força do nó. No caso da rede de energia, este valor indicaria a quantidade de tensão manipulada pelo nó.

Estas e outras observações a respeito de redes com pesos são feitas no artigo seminal de Barrat et al. denominado the architecture of complex weighted networks, publicado em 2004. Vale a pena a leitura.