Rede robusta

Rede robusta é uma rede complexa capaz de suportar falhas e perturbações — fato comum aos complexos sistemas que elas representam.

(a) Rede antes da falha local.

(b) Rede depois da falha local.Fig. 1 - Falha local.

Em Networking Science, uma rede é a representação da interação direta (links/arestas) entre elementos (nós/vértices). Dessa forma, sistemas de diferentes naturezas ou aparências podem apresentar representação em rede similar, facilitando comparativos desses sistemas e permitindo que resultados de um determinado estudo sejam aplicados em vários contextos. Sendo assim, redes podem representar sistemas de naturezas diversas como: biologia, ciência, economia, comunicação, etc.

Para ilustrar o efeito da robustez de uma rede, usamos como exemplo a Internet. A falha em um determinado roteador pode causar um impacto local, ou seja, alguns dispositivos perderiam a conexão com o restante da rede. Porém, se ocorrer uma falha em número significativamente grande de roteadores, a rede seria fragmentada em clusters (grupos), onde os dispositivos só poderiam se conectar a outros do mesmo cluster. Dessa forma, a robustez de uma rede está ligada o número de falhas que ela tolera, sem que a mesma seja transformada em um conjunto de pequenos clusters.

As perturbações que uma rede pode sofrer são representadas pela remoção de um nó ou link. Dessa forma, o estudo da robustez de uma rede visa compreender o impacto que a perde de um nó causa nesta. Algumas perturbações podem ser locais, sem impacto generalizado na conexão, como pode ser visto na Fig. 1; e outras podem impactar largamente a rede, gerando vários componentes desconexos, como pode ser visto na Fig. 2. Para avaliar o impacto que a perda de um nó causa na rede, é usada a teoria metamatemática da Percolação.

(a) Rede antes de falha central

(b) Rede depois de falha central

Fig. 2 - Falha central.

Teoria da percolação

Podemos pensar na teoria da percolação como uma grid em que a probabilidade de uma intersecção possuir um ponto é $p$; e que dois pontos vizinhos são considerados conectados. É fácil de perceber que, quanto maior é $p$, maior será o número de pontos presentes na grid. Segundo a teoria da percolação, se $p$ se aproxima de um valor $p_{c}$, então os pontos da grid formaram um grande cluster, chamado de percolating cluster, o qual interliga toda a grid, embora não necessariamente exista um único cluster nesta. Para caracterizar $p_{c}$, são utilizadas três medidas:

- Tamanho médio dos clusters $\langle d\rangle$: $\langle s\rangle \sim |p-p_{c}|^{-\gamma _{p}}$ (Eq. 1)

- Parâmetro de ordem $P_{\infty }$ é a probabilidade de que um ponto P escolhido aleatoriamente pertença ao maior cluster.

$p_{\infty }\sim (p-p_{c})^{\beta _{p}}$ (Eq. 2)

- Tamanho de correlação $\xi$ é a distância média entre dois pontos que pertençam ao mesmo cluster.

$\xi \sim |p-p_{c}|^{-\nu }$

Os expoentes críticos $\gamma _{p}$, $\beta _{p}$ e $\nu$ caracterizam os efeitos da percolação próximos ao ponto crítico $p_{c}$. Eles são determinados pela dimensões da grid; e independentes ao tamanho desta ou ao valor de $p_{c}$.

Percolação inversa

Para aplicar a teoria de percolação no estudo de redes robustas, usamos a percolação inversa, ou seja, verificamos o comportamento ao remover os pontos.

Imagine que os pontos na grid representam nós de uma rede; e aleatoriamente é removida uma fração $f$ de nós. Veja que um valor pequeno de $f$ tem um impacto limitado na integridade da rede. Já para um valor de $f$ suficientemente grande, a rede é quebrada em pequenos componentes desconexos.

Dessa forma, existe um limite crítico $f_{c}$, onde para qualquer $f$ < $f_{c}$, os pontos da rede continuam formando um grande componente, e para $f$ > $f_{c}$, esse grande componente desaparece, tornando a rede um conjunto de clusters desconexos. A presença do limite crítico mostra que o impacto provocado pela remoção aleatória de nós não é um processo gradual.

Robustez em redes sem escala

Uma rede sem escala possui uma distribuição de grau irregular; e apresenta hubs, nós centrais de algumas regiões da rede. Essas características não acontecem com as redes regulares e aleatórias, onde os nós possuem graus comparáveis. Para que uma rede sem escala seja dividida em componentes desconexos, é necessário que quase todos os nós sejam removidos, ou seja, $f_{c}$ deve ser próximo a 1.

Uma ilustração desse caso é a rede dos aeroportos. Perceba que provavelmente um aeroporto removido aleatoriamente é um aeroporto pequeno. Por exemplo, o aeroporto de Pampulha (MG), o qual não afetará a conexão da rede por inteira, já que ainda seria possível viajar de São Paulo para Paris ou de Nova York para Sydney.

Tolerância a ataques

Um ataque a uma rede é uma ação deliberada que visa desconectá-la. Nesse caso, ao invés de remover nós aleatórios, são removidos os nós de maior grau. Ao analisar esse tipo de situação, percebemos que a remoção de poucos nós é capaz de fragmentar a rede em clusters desconexos. Nessa caso, $f_{c}$ de ataques em redes sem escala possuem o mesmo comportamento que $f_{c}$ para falhas (aleatórias) em redes regulares, ou seja, valor mais próximo a 0 do que a 1.

O exemplo dos aeroportos pode ilustrar esse fato. Imagine que os aeroportos de Atlanta, Chicago, Denver e Nova York fiquem inoperantes ao mesmo tempo. Eles representam uma parcela pequena do número de aeroportos existentes, porém são responsáveis por muitas conexões na malha aérea.

Falhas em cascata

Um efeito cascata ocorre quando um sequência de eventos locais são propagados para todo o sistema. Por exemplo, uma falha em uma estação de redistribuição de energia elétrica encadearia na falha de outros elementos conectados e dependentes dela.

Modelos de falhas em cascata

O mecanismo do fenômeno de cascata de uma rede depende da estrutura desta; do modo de propagação da falha; e do critério de falha de cada nó. E as três principais características do sistema para que ele possa sofrer falhas em cascata são:

• O sistema é caracterizado por um fluxo que percorre a rede. Por exemplo, as informações são propagadas pelos nós.
• Cada elemento tem uma regra de falha própria.
• Cada sistema tem uma política de redistribuição do fluxo.

Modelo de propagação de falha

No modelo de propagação, o nó $i$ falha quando uma fração $\varphi _{i}$ de seus vizinhos estão com falhas. Nesse modelo, o grau de um nó ou o grau médio da rede caracterizam a vulnerabilidade da rede a falhas em cascata.

Modelo de árvore

Esse modelo caracteriza a ideia de falhas em cascata em sua concepção. Nele, os nós são analisados como a raiz de uma árvore, uma representação de grafo direcionado com um único nó que não possuí aresta de entrada. Caso o nó de grau zero falhe, ou seja, o nó raiz, então toda a árvore falha. Caso falhe um nó de grau maior que zero, a árvore não falha.