Rede robusta
# Rede robusta

Rede robusta é uma rede complexa capaz de suportar falhas e perturbações — fato comum aos complexos sistemas que elas representam.
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.

## 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.