Um dado que se repete em diversas redes complexas é que há uma relação inversa entre a quantidade de enlaces e o tamanho médio dos caminhos. O aumento do número de enlaces em um grafo leva, geralmente, a uma modificação do tamanho médio dos caminhos, que pode aumentar esta métrica ou diminuí-la.
Para medir esta relação podemos usar a eficiência dos enlaces, que permite determinar quão efetivos os enlaces são em diminuir as distâncias no grafo. Analisando esta métrica podemos entender se os enlaces existentes no grafo estão colaborando, de forma geral, para a redução do tamanho dos caminhos na rede. Por meio dela, também podemos comparar grafos similares e entender se uma topologia é mais eficiente do que outras.
Para um grafo $G$, com tamanho médio dos caminhos $TMC(G)$ e $m$ enlaces, a eficiência de seus enlaces é dada por
$E(G)=1-\frac{TMC(G)}{m}$
Esta métrica pode ir de 0 (0%), assumindo um tamanho médio do caminho teórico igual a $m$, até 1 (100%), quando o tamanho médio do caminho se aproxima de zero.
O racional por trás desta equação é que os piores casos acontecem quando o $TMC(G)$ é muito próximo de $m$, significando que os caminhos existentes precisam usar quase todos os enlaces da rede. Note-se que o caso em que $E(G)=0$ é apenas um limite teórico, já que é impossível que a média dos tamanhos dos caminhos seja $m$, afinal de contas os nós que estão ligados diretamente possuem caminhos de tamanho 1, o que faz com que $TMC(G)$ seja puxada para baixo.
Uma utilidade da eficiência é avaliar se topologias de rede são escaláveis. Uma dada topologia (ou modelo) de rede é dita escalável se a eficiência dos enlaces cresce ou se mantém, conforme o tamanho da rede $n$ cresce. Se isto não ocorre dizemos que a rede é não-escalável.
Este tipo de análise pode ser feita quando existe alguma lei de formação da rede. Imaginemos uma rede estrela, que é uma rede de $n$ nós cuja topologia é formada por um único nó central ligado diretamente aos $n-1$ nós. O grafo abaixo é uma rede estrela com $n=5$ nós.
Rede Estrela com 5 nós
Sabemos que a eficiência dos enlaces desta rede é de 60%. Se analisarmos o que acontece quando esta rede cresce em número de nós, veremos que a eficiência cresce também, aproximando-se de 100%. O tamanho médio dos caminhos em uma rede estrela é dado por
$TMC(G) = \frac{2*(n-1)*(n-2)+2*(n-1)}{n(n-1)}$
Para chegar nesta equação, basta observar que o TMC(G) é uma média. Basta somar o tamanho de todos os caminhos na rede e dividir pela quantidade máxima de caminhos possível, que é o denominador da equação de TMC(G) da rede estrela. Para o numerador, temos os seguintes caminhos:
- Aqueles que partem de qualquer nó (exceto o central) para qualquer nó (exceto o central) e que têm tamanho $2$. Assim, temos que existem $(n-1)*(n-2)$ caminhos deste tipo, logo $2*(n-1)*(n-2)$.
- E aqueles que partem do nó central para cada outro nó e vice-versa. Assim, temos $2*(n-1)$ caminhos deste tipo (ida e volta) de tamanho 1. Então fica $1*2*(n-1) = 2*(n-1)$.
Assim, o gráfico abaixo mostra o comportamento da eficiência com o crescimento do número de nós (partindo de $n=3$ à $n=30$).
Crescimento da eficiência dos enlaces em uma rede estrela
Conforme podemos observar, a rede em estrela é escalável, já que cada novo nó (e novo enlace junto com este nó) aumenta a eficiência da rede. Você pode imaginar esta métrica como uma forma de saber se uma rede é eficiente no transporte de informação ou bens. Neste caso, a rede estrela é bastante eficiente.
Comentários
Postar um comentário