# Teoria da percolação em redes

Em física estatística e matemática, a teoria de percolação descreve o comportamento de uma rede quando nós ou links são removidos. Este é um tipo geométrico de transição de fase, pois em uma fração crítica de remoção a rede se divide em clusters conectados significativamente menores. As aplicações da teoria da percolação à ciência dos materiais e em muitas outras disciplinas são discutidas aqui e nos artigos de teoria de redes e percolação.

## Introdução

A teoria Flory-Stockmayer foi a primeira teoria a investigar os processos de percolação.
Uma pergunta representativa (e a fonte do nome) é a seguinte. Suponha que algum líquido seja derramado sobre algum material poroso. O líquido conseguirá passar de buraco em buraco e chegar ao fundo? Esta questão física é modelada matematicamente como uma rede tridimensional de n × n × n vértices, geralmente chamados de "sites", em que as bordas ou "ligações" entre cada dois vizinhos podem estar abertas (permitindo a passagem do líquido) com probabilidade p, ou fechadas com probabilidade 1 - p, sendo que as situações de cada borda são consideradas independentes. Para um dado p, qual é a probabilidade de que um caminho aberto (significando um caminho one cada um dos links é um vínculo "aberto") exista de cima para baixo? O comportamento para n grande é de interesse primário. Este problema, agora chamado de percolação de títulos, foi introduzido na literatura matemática por Broadbent & Hammersley (1957), e tem sido estudado intensamente por matemáticos e físicos desde então.
A remoção de um único nó tem impacto limitado na integridade de uma rede. A remoção de vários nós, entretanto, pode quebrar uma rede em vários componentes isolados. Obviamente, quanto mais nós removemos, maiores são as chances de danificarmos uma rede, o que nos leva a perguntar: Quantos nós temos que excluir para fragmentar uma rede em componentes isolados? Por exemplo, que fração dos roteadores da Internet deve quebrar para que a Internet se transforme em grupos de computadores que não conseguem se comunicar uns com os outros? Para responder a estas perguntas, devemos primeiro nos familiarizar com os fundamentos matemáticos da robustez da rede, oferecidos pela teoria da percolação.

## Percolação

A teoria da percolação é um subcampo altamente desenvolvido da física estatística e da matemática. Um problema típico tratado por ele é ilustrado pelo exemplo de uma rede quadrada, onde colocamos nós com probabilidade p de estarem ativados em cada intersecção. Nós vizinhos ativados são considerados conectados, formando aglomerados (clusters) de tamanho dois ou mais de nós ativados. Dado que a posição de cada nó é decidida ao acaso, perguntamos: qual é o tamanho esperado do maior cluster? Qual é o tamanho médio dos clusters?
Obviamente, quanto maior for p, maiores serão os clusters. Uma previsão chave da teoria da percolação é que o tamanho do cluster não muda gradualmente com p. Em vez disso, para uma ampla faixa de p, a rede é povoada com numerosos aglomerados minúsculos. Se p se aproximar de um valor crítico pc, estes pequenos clusters crescem e se aglutinam, levando ao surgimento de um grande cluster. Chamamos isso de aglomerado de percolação quando atinge o total da rede. Em outras palavras, em pc observamos uma transição de fase de muitos pequenos aglomerados para um aglomerado de percolação que permeia toda a rede.
Para quantificar a natureza desta transição de fase, nos concentramos em três quantidades:

### Tamanho médio do cluster:〈s〉

De acordo com a teoria de percolação, o tamanho médio ⟨s⟩ de todos os aglomerados finitos segue a fórmula:
⟨s⟩∼|p−pc|$^{−γp}$
Em outras palavras, o tamanho médio do cluster diverge conforme nos aproximamos do valor pc.

### Parâmetro de ordem: P∞

A probabilidade P∞ de que um nó escolhido aleatoriamente pertença ao maior aglomerado segue a fórmula:
P∞∼(p−pc)$^{βp}$
Portanto, à medida que p diminui em direção a pc, a probabilidade de um nó pertencer ao maior aglomerado cai para zero.

### Comprimento de correlação: ξ

A distância média entre dois nós ativados que pertencem ao mesmo cluster segue a fórmula:
ξ∼|p−pc|$^{−ν}$
Portanto, enquanto para p < pc a distância entre os nós no mesmo aglomerado é finita, para pc essa distância diverge. Isto significa que em pc o tamanho do maior cluster torna-se infinito, permitindo que ele englobe toda a rede.
Os expoentes γp, βp e ν são chamados de expoentes críticos, pois caracterizam o comportamento do sistema próximo ao ponto crítico pc. A teoria da percolação prevê que estes expoentes são universais, o que significa que são independentes da natureza da rede ou do valor preciso de pc. Portanto, independentemente de colocarmos os nós ativados em uma rede triangular ou hexagonal, o comportamento de 〈s〉, P∞ e ξ é caracterizado pelos mesmos expoentes γp, βp e ν.

## Transição de Percolação Inversa e Robustez

O fenômeno de interesse primário na robustez é o impacto das falhas dos nós na integridade de uma rede. Podemos usar a teoria da percolação para descrever esse processo.
Tomemos como base uma rede quadrada como uma rede cujos nós ativados são as interseções. Removemos aleatoriamente uma fração f de nós ativados, perguntando como sua ausência afeta a integridade da rede.
Se f for pequeno, os nós ativados ausentes causam poucos danos à rede. Aumentar f, no entanto, pode isolar pedaços de nós ativados do componente gigante. Finalmente, para f suficientemente grande, o componente gigante se divide em minúsculos componentes desconectados.
Este processo de fragmentação não é gradual, mas é caracterizado por um limite crítico fc: para qualquer f < fc continuamos a ter um componente gigante. Quando f excede fc, o componente gigante desaparece. Isto é ilustrado pela dependência de P∞ em relação a f, representando a probabilidade de que um nó seja parte do componente gigante: P∞ é diferente de zero abaixo de fc, mas cai para zero à medida que nos aproximamos de fc. Os expoentes críticos que caracterizam esta quebra, γp, βp, ν, são os mesmos encontrados anteriormente. Na verdade, os dois processos podem ser mapeados um no outro escolhendo f = 1 - p.
E se a rede subjacente não for tão regular quanto uma rede quadrada? A resposta depende da topologia precisa da rede. No entanto, para redes aleatórias, a resposta continua a ser fornecida pela teoria da percolação: Redes aleatórias sob falhas de nó aleatórias compartilham os mesmos expoentes de escala que a percolação de dimensão infinita. Logo, os expoentes críticos para uma rede aleatória são γp = 1, βp = 1 e ν = 1/2, correspondendo a expoentes de percolação para reticulados em dimensão d > 6
Em resumo, o colapso de uma rede durante a remoção aleatória de nós não é um processo gradual. Em vez disso, a remoção de uma pequena fração de nós tem apenas impacto limitado na integridade de uma rede. Mas, uma vez que a fração de nós ativados removidos atinge um limite crítico, a rede se divide abruptamente em componentes desconectados. Em outras palavras, falhas aleatórias de nós induzem uma transição de fase de uma rede conectada para uma fragmentada. Podemos usar as ferramentas da teoria da percolação para caracterizar essa transição em redes regulares e aleatórias. Para redes sem escala, os principais aspectos dos fenômenos descritos mudam, no entanto.

## Aplicações
### Em biologia, bioquímica e virologia física

A teoria da percolação foi usada para predizer com sucesso a fragmentação de "cascas" de vírus biológicos (cápsides), com o limiar de fragmentação da cápside do vírus da Hepatite B predito e detectado experimentalmente. Quando um número crítico de subunidades foi removido aleatoriamente do invólucro nanoscópico, ele se fragmenta e esta fragmentação pode ser detectada usando Espectroscopia de Massa para Detecção de Carga (CDMS), entre outras técnicas de partícula única. Este é um análogo molecular do jogo de tabuleiro comum Jenga e tem relevância para a desmontagem de vírus.

### Em ecologia

A teoria da percolação foi aplicada a estudos de como a fragmentação do ambiente impacta os habitats dos animais e modelos de como a bactéria da peste Yersinia pestis se espalha.

### Percolação de redes interdependentes multicamadas

Buldyrev et al. desenvolveram um framework para estudar percolação em redes multicamadas com links de dependência entre as camadas. Novos fenômenos físicos foram encontrados, incluindo transições abruptas e falhas em cascata. Quando as redes estão embutidas no espaço, elas se tornam extremamente vulneráveis, mesmo para uma fração muito pequena de links de dependência e para ataques localizados em uma fração zero de nós. Quando a recuperação de nós é introduzida, um diagrama de fase rico é encontrado, incluindo pontos multicríticos, histerese e regimes metaestáveis.

### No tráfego

Em artigos recentes, a teoria da percolação foi aplicada para estudar o tráfego em uma cidade. A qualidade do tráfego global em uma cidade em um determinado momento pode ser caracterizada por um único parâmetro, o limiar crítico de percolação. O limite crítico representa a velocidade abaixo da qual se pode viajar em uma grande fração da rede da cidade. Acima desse limite, a rede da cidade se divide em grupos de vários tamanhos e é possível viajar em bairros relativamente pequenos. Este novo método também é capaz de identificar gargalos de tráfego repetitivos. Os expoentes críticos que caracterizam a distribuição do tamanho do cluster de bom tráfego são semelhantes aos da teoria de percolação. Também foi descoberto que durante os horários de pico a rede de tráfego pode ter vários estados metaestáveis ​​de diferentes tamanhos de rede e a alternância entre esses estados. Um estudo empírico sobre a distribuição de tamanho espaço-temporal de congestionamentos foi realizado por Zhang et al. Eles encontraram uma lei de potência universal aproximada para a distribuição de tamanhos de congestionamentos em diferentes cidades. Um método para identificar grupos funcionais de ruas espaço-temporais que representam o fluxo de tráfego fluente em uma cidade foi desenvolvido por Serok et al.