Rede robusta
Rede robusta é uma rede complexa capaz de suportar falhas e perturbações — fato comum aos complexos sistemas que elas representam.
![Fig.1 - Grafo com falhar local](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Grafo_5_nos.png/220px-Grafo_5_nos.png)
![](http://upload.wikimedia.org/wikipedia/commons/3/32/Grafo_5_nos_falha.png)
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.
![](http://upload.wikimedia.org/wikipedia/commons/4/41/Grafo_no_central.png)
![](http://upload.wikimedia.org/wikipedia/commons/5/51/Grafo_no_central_falha.png)
Teoria da percolação[2]
[editar | editar código-fonte]Podemos pensar na teoria da percolação como uma grid em que a probabilidade de uma intersecção possuir um ponto é ; e que dois pontos vizinhos são considerados conectados. É fácil de perceber que, quanto maior é , maior será o número de pontos presentes na grid. Segundo a teoria da percolação, se se aproxima de um valor , 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 , são utilizadas três medidas:
- Tamanho médio dos clusters : (Eq. 1)
- Parâmetro de ordem é a probabilidade de que um ponto P escolhido aleatoriamente pertença ao maior cluster.
(Eq. 2)
- Tamanho de correlação é a distância média entre dois pontos que pertençam ao mesmo cluster.
Os expoentes críticos , e caracterizam os efeitos da percolação próximos ao ponto crítico . Eles são determinados pela dimensões da grid; e independentes ao tamanho desta ou ao valor de .
Percolação inversa
[editar | editar código-fonte]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 de nós. Veja que um valor pequeno de tem um impacto limitado na integridade da rede. Já para um valor de suficientemente grande, a rede é quebrada em pequenos componentes desconexos.
Dessa forma, existe um limite crítico , onde para qualquer < , os pontos da rede continuam formando um grande componente, e para > , 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
[editar | editar código-fonte]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, 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]
[editar | editar código-fonte]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, de ataques em redes sem escala possuem o mesmo comportamento que 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
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]No modelo de propagação, o nó falha quando uma fração 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
[editar | editar código-fonte]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
[editar | editar código-fonte]- ↑ Barabási, Albert-László (2017). «Network Science». Consultado em 23 de junho de 2020
- ↑ Dietrich Stauffer, Ammon Aharony (2018). Introduction to Percolation Theory. London: Taylor & Francis
- ↑ 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