Usuário(a):Maisa usp/Redes robustas

Redes Robustas (Network Robustness)

A palavra Robusto vem da palavra latina Quercus Robur, que significa carvalho vermelho que na Idade Antiga era símbolo de força e longevidade. Dessa forma, redes robustas são aquelas capazes de suportar falhas e pertubações, um fato comum aos complexos sistemas representados por redes.

(a) Rede antes da falha local.

(b) Rede depois da falha local.

Fig. 1 - Falha local.

Em Networking Science uma Rede (Networking) é a representação da interação direta, links/arestas, entre nós/vértices. Dessa forma, sistemas de diferentes natureza ou aparência podem ter uma representação em rede similar, permitindo que estes sistemas sejam relacionados e resultados de um determinado estudo seja aplicado em vários contextos. Sendo assim, Redes são utilizadas para representações de sistemas de diversas como: biologia, ciência, economia, comunicação etc.

Para ilustrar a importância da robustez de uma rede imagine a Internet, a falha em um determinado roteador 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 fragmenta em clusters, onde os dispositivos só poderiam se conectar a outros dispositivos do mesmo cluster (grupo). 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 pertubações que uma rede pode sofrer é representada pela remoção de um nó ou link, dessa forma o estudo da Robustez de uma rede visa compreender o impacto que tais remoções podem causar em uma rede. Algumas perturbações podem ser locais afetando diretamente alguns nós como pode ser visto na Fig. 1, , e outras podem impactar fortemente a rede, por exemplo quebrando ela em vários componentes conexos como pode ser visto na Fig. 2. A teoria metamatemática da Percolação é a técnica utilizada para avaliar o impacto da remoção dos nós de uma rede, e por consequência a robustez da mesma.

(a) Rede antes de falha central

(b) Rede depois de falha central

Fig. 2 - Falha central.

Teoria da Percolação

Podemos pensa na teoria da percolação com 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. Sendo que não necessariamente este é o único cluster da grid. Para caracterizar $p_{c}$ são utilizadas 3 medidas:

- Tamanho médio do cluster $\langle d\rangle$: média do tamanho de todos os cluster finitos.

$\langle s\rangle \sim |p-p_{c}|^{-\gamma _{p}}$ (Eq. 1)

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

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

- Tamanho de correlação $\xi$: 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 adição de pontos próximo ao ponto crítico $p_{c}$, eles são determinados pelo número de dimensões da grid e independentes ao tamanho da grid ou ao valor de $p_{c}$.

Percolação Inversa

Para aplicar a teoria de percolação no estudo de robustez de redes, 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}$ o 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. Fato que não acontece com as redes regulares e aleatória, casos onde os nós possuem graus comparáveis. Para que uma rede sem escala seja dividida em componentes é necessário que quase todos os nós sejam removidos, ou seja $f_{c}$ é próximo a 1.

Uma ilustração desse caso é a rede dos aeroportos, perceba que o aeroporto selecionado aleatoriamente para ser removido da rede muito provavelmente é um aeroporto pequeno, por exemplo o aeroporto de Pampulha/MG, o qual não afetará a conexão da rede por inteira, ainda seria possível viajar de São Paulo para Paris ou de Nova York para Sidney.

Tolerância a Ataques

Uma ataque a uma rede é uma ação deliberada que visa desconecta-la, 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 cluster 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 New 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 modelo de falhas em cascata caracteriza o mecanismo do fenômeno de cascata, ele depende da estrutura da rede, do modo de propagação da falha e do critério de falha de cada nó. As três principais características do sistema para que ela possa sofrer falhas em cascata são:

• O sistema é caracterizado por um fluxo pela rede, por exemplo, as informações são propagadas pelos nós.
• Cada componente tem uma regra de quebra local.
• Cada sistema tem uma política de redistribuição do fluxo.

Modelo de Propagação de Falha

Nesse caso o nó $i$ falha por propagação 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 do sistema 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 raíz 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 falha, ou seja, é o nó raíz, então toda a árvore falha, caso contrário a árvore não falha.