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.^[1]

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^[2]

Podemos pensar na teoria da percolação como uma grid em que a probabilidade de uma intersecção possuir um ponto é ${\displaystyle p}$; e que dois pontos vizinhos são considerados conectados. É fácil de perceber que, quanto maior é ${\displaystyle p}$, maior será o número de pontos presentes na grid. Segundo a teoria da percolação, se ${\displaystyle p}$ se aproxima de um valor ${\displaystyle 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 ${\displaystyle p_{c}}$, são utilizadas três medidas:

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

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

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

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

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

Os expoentes críticos ${\displaystyle \gamma _{p}}$, ${\displaystyle \beta _{p}}$ e ${\displaystyle \nu }$ caracterizam os efeitos da percolação próximos ao ponto crítico ${\displaystyle p_{c}}$. Eles são determinados pela dimensões da grid; e independentes ao tamanho desta ou ao valor de ${\displaystyle 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 ${\displaystyle f}$ de nós. Veja que um valor pequeno de ${\displaystyle f}$ tem um impacto limitado na integridade da rede. Já para um valor de ${\displaystyle f}$ suficientemente grande, a rede é quebrada em pequenos componentes desconexos.

Dessa forma, existe um limite crítico ${\displaystyle f_{c}}$, onde para qualquer ${\displaystyle f}$ < ${\displaystyle f_{c}}$, os pontos da rede continuam formando um grande componente, e para ${\displaystyle f}$ > ${\displaystyle 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, ${\displaystyle 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^[3]

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, ${\displaystyle f_{c}}$ de ataques em redes sem escala possuem o mesmo comportamento que ${\displaystyle 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ó ${\displaystyle i}$ falha quando uma fração ${\displaystyle \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.

Referência

1. Barabási, Albert-László (2017). «Network Science». Consultado em 23 de junho de 2020 
2. Dietrich Stauffer, Ammon Aharony (2018). Introduction to Percolation Theory. London: Taylor & Francis 
3. Réka Albert, Hawoong Jeong & Albert-László Barabási (25 de janeiro de 2001). «Error and attack tolerance of complex networks». Nature. Consultado em 23 de junho de 2020