Arquivo da tag: Sistemas Complexos

Posts sobre sistemas complexos e complexidade em física.

Epidemias, parte I

Hardcore

Trombei esses dias com um artigo de 2001 sobre propagação de vírus em humanos e sua comparação a vírus de internet. O estudo da disseminação de infecções é velho na física, diversos modelos de epidemias são estudados e muitos com resultados razoavelmente bons. Um ponto comum em modelos estudados pela epidemiologia é a noção de threshold, ou seja, o valor mínimo de eficiência que uma infecção deve ter para conseguir se propagar. Novamente, esse é um post hardcore, os corajosos sigam-me, vamos ver com cuidado como isso funciona.

Esse post ficou grande, então parti em dois. Nesse primeiro, comento o modelo de propagação de vírus em seres humanos, no próximo trato da internet.

Representamos indivíduos como pontos e o contato entre indivíduos como linhas em um grande grafo. Passamos a nos perguntar qual seria um modelo eficaz de grafo para modelizar as relações humanas. Certamente não conhecemos pessoas aleatoriamente na rua, costumamos conhecer melhor nossos vizinhos, familiares e colegas de trabalho, que por sua vez conhecem-se. Um jeito legal de modelizar essa ideia, que chamamos de grafo de small world, é tomar um anel de pontos, sendo cada ponto ligado a seus $ m$ vizinhos mais próximos. Em seguida, passamos “em revista” essas conexões da seguinte forma: cada ponto terá uma probabilidade $ p$ de desfazer uma conexão com um vizinho seu no sentido horário e associá-la a algum outro ponto aleatoriamente. A ideia do sentido horário é apenas para evitar mexer na mesma conexão duas vezes. Se $ p=1$, essa revista resulta em um grafo em forma de anel com conexões completamente aleatórias. Se $ p=0$, o grafo continuará no modelo do conhecimento apenas da vizinhança, mas, se $ p$ é pequeno, o grafo tornar-se-á um modelo muito próximo do que queremos: vizinhos possuem uma chance maior de se conhecerem do que conhecerem alguém do outro lado do grafo, mas de vez em quando algum vizinho seu conhece alguém lá longe, o que é bem coerente com a realidade e até permite aquelas coincidências do tipo “hoje meu avô almoçou com o pai de um professor meu”.

O resultado está bem representado nessa figura, onde os pontos são inicialmente ligados a seus $ 2m$ vizinhos mais próximos, com $ m=2$. É o famoso modelo de Watts-Strogatz, ou modelo de small-world:

Podemos, com esse modelo bonitinho, estudar a propagação de infecções entre seres humanos. Imaginemos um vírus que, a cada contato entre são e infectado, tenha uma probabilidade $ nu$ de contágio e, a cada “turno”, tenha uma probabilidade $ \delta$ de cura de um infectado. A chance de um ponto possuir $ k$ vínculos é $ P(k)= \frac{1}{\langle k\rangle}e^{-k/\langle k\rangle}$ nesse modelo, e $ \langle k\rangle=2m$. A equação estocástica dessa criança não é bonita, então vamos usar um mean field, calcular o que vai acontecer com a densidade média de infectados supondo que todos os pontos possuem o mesmo número de conexões, $ 2m$, naturalmente, e que todos estão ligados a um número de infectados igual ao valor médio de infectados, essas são as características de uma abordagem de campo médio. A densidade total de infectados, denotada $ \rho_t$ por ser uma função do tempo, é apenas o número total de infectados dividido pelo número total de pessoas. Diremos que a variação na densidade de infectados $ \rho_t$ (a fração da população infectada naquela “rodada”), que toma valores entre 0 e 1, perde a cada “rodada” o equivalente a $ \delta\rho_t$ (os que se curaram) e ganha o equivalente ao contato são-infectado, que é $ nu\langle k\rangle\rho_t(1-\rho_t)$, ou seja, chance de um contato ser são-infectado $ \rho_t(1-\rho_t)$ multiplicada pelo número médio de contatos $ \langle k\rangle$ e pela chance de esse contato transmitir a infecção $ \nu$. Dividindo a equação toda por $ \delta$ e sem precisar ir muito além de uma reparametrização no tempo, podemos escrever:

\[\frac{d}{dt}\rho_t=-\rho_t+\lambda\langle k\rangle\rho_t(1-\rho_t).\]

Com $ \lambda= \frac{\nu}{\delta}$ o valor que interessa para medir a eficácia de uma infecção. E essa equação, ainda que seja apenas uma teoria de campo médio, já nos dá bastante informação sobre o que está acontecendo. Você até pode pedir para o Wolfram Alpha resolver essa para você, eu não faria diferente, mas vale mais estudar algumas propriedades na mão. Chamamos densidade de persistência o valor de $ rho_t$ para o qual sua derivada temporal é zero. Se ela não é nula, temos uma infecção persistente em uma fração da população. Igualando a equação acima a zero, percebemos duas respostas possíveis: ou $ rho_t = 0$, ou $ \rho_t=1- \frac{1}{\lambda\langle k\rangle}$. Como a densidade de infectados não pode ser menor que 0, naturalmente, descobrimos que, se $ \lambda < \frac{1}{\langle k\rangle}$, então a única solução possível é $ \rho_t=0$, pois a segunda solução fica absurda. Mas, se a infecção é mais eficaz que o threshold $ \frac{1}{\langle k\rangle}$, teremos um crescimento da densidade de persistência que tende a 1 quando $ \lambda$ se aproxima do infinito.

Densidade de persistência com m=2.

E fica claro que o threshold, dependendo do inverso do número médio de contatos, que nesse modelo é proporcional ao número de vizinhos, nos dá uma informação esperada: quanto maior o número de vizinhos (contatos), menos eficaz uma doença deve ser para se propagar. Se uma doença é bem eficaz, podemos reduzir seu impacto com uma diminuição nos vizinhos, se está com gripe, não saia de casa.

Esse modelo é bem coerente com diversas observações de epidemias simples em populações. Por esse mecanismo de small-world, apenas doenças suficientemente poderosas, com eficácia $ \lambda$ maior que um determinado limite, podem se propagar pela população, possuem vida no longo prazo. A mudança de fase ocorre no threshold $ \lambda^\star= \frac{1}{\langle k\rangle}$ que, no gráfico acima, ocorre em $ \lambda = 0,25$. O próximo passo nesse modelo seria estudar um grafo em que pessoas podem morrer, nascer, tornar-se imunes, tomarem vacinas ou tornarem-se mais suscetíveis a doenças com o tempo.

Tudo isso é muito interessante, mas não consegue explicar a propagação de vírus na internet. Em um próximo post, veremos que, na internet, small-world não pode ser aplicado (afinal, todos conhecem o Google ou o Facebook) e a própria noção de threshold, por um fenômeno estatístico fascinante, desaparece.

2 respostas

O problema da diretora do colégio

Geek

Venho por meio deste compartilhar um problema deveras interessante que requereu algumas horas do meu dia para a programação. Escrevi-o há algum tempo a um amigo cursando ciência da computação que, sendo garoto de programa, certamente saberia apreciar o que fiz, e sou carente desse tipo de apreciação. O problema que me foi proposto em meu curso de física estatística foi o da diretora do colégio.

Aconteceu uma vez comigo, recebi, acho que na sexta série, um papel para escrever os nomes dos coleguinhas com que gostaria de estar ano seguinte. Escrevi os dois nomes que queria (era uma criança sozinha e com poucos amigos), entreguei e no ano seguinte estava na sala deles. Ainda, as salas não mudaram muito, o que é razoável, já que as pessoas tendiam a querer ficar com quem já estavam, achei que a diretora havia atendido aos pedidos individualmente, mas hoje penso que não. Vamos tentar entender a razão de, se a diretora fosse realmente levar aqueles papéis a sério, ela teria que aprender um pouco mais de física e informática.

Imagine-se uma diretora de colégio, responsável por preparar as classes para o próximo ano letivo. Como você é boazinha, decide deixar os alunos escolherem com quem eles querem ficar no próximo ano, então dá a possibilidade de eles escreverem em um papel nomes dos coleguinhas que mais querem encontrar no ano seguinte. Mas sendo uma diretora justa, você pergunta aos professores quais alunos seria melhor que não ficassem na mesma turma, uma “lista negra” de duplas que seria melhor que ficassem separados. Com essas duas informações: a preferência dos alunos e a lista negra dos professores, como determinar qual distribuição ideal de alunos?

Esse não é um problema fácil. Podemos pensar em tratar o problema brutalmente: listar todas as possibilidades e verificar qual satisfaz melhor às condições das listas, tanto a de preferência quanto a de exclusão, mas isso, com um número pequeno de alunos, logo atinge limites astronômicos. O número de configurações possíveis de sala será $2^{\text{numero de alunos}}$, com 100 alunos você teria algo perto de $10^{30}$ configurações. Meu processador i5 só aguenta algo perto de 10MIPS, o que me dá o direito de realizar $10^7$ instruções por segundo e eu precisaria de pelo menos $10^{23}$ segundos para fazer qualquer coisa com essas configurações, isso é mais que a idade do universo. Essa conta provavelmente está bem errada, mas acredito no argumento de que, para listar todos os casos possíveis, terei que investir mais que uma tarde em cálculos. Precisamos pensar em um jeito mais malandro.

Primeiro, vamos pensar no quadro teórico do problema e como implementar de maneira adequada. Eu quero um jeito prático de saber quantas condições uma configuração de alunos satisfaz e quantas ele viola. Vou atribuir pesos iguais à preferência dos alunos e à lista dos professores, poderiam ser diferentes, mas sou preguiçoso. Seja n o número de alunos. Tomo um vetor $S_n$ com $n$ coordenadas que podem valer 1 ou -1. Se $S_i=1$, então o aluno $i$ está na sala A. Se $S_i=-1$, o aluno $i$ está na sala B.

Em seguida, defino a matriz $J_{ij}$, que é $n\times n$. Ela contém a seguinte informação: $J_{ij} = 1$ se o aluno $i$ quer ficar com o aluno $j$. $J_{ij} = -1$ se não é legal que o aluno $i$ fique com o aluno $j$ e $J_{ij}=0$ se eles são indiferentes entre si. Eu poderia ter privilegiado a opinião dos professores atribuindo um peso muito negativo ao invés de -1, mas vamos dar uma chance as alunos e atribuir pesos iguais às preferências dos alunos e dos professores. Isso vai servir para calcular o quanto de “felicidade” a configuração gera. Se dois alunos estão na mesma sala e queriam estar na mesma sala, a felicidade aumenta. Se eles não podem estar na mesma sala e estão em salas separadas, a felicidade aumenta. Se estão em salas diferentes e queriam estar juntos, ela diminui. Mas como computar isso? Basta calcular: $J_{ij}\cdot S_i\cdot S_j$.

Se eles estão na mesma sala, o produto $ S_i\cdot S_j$ será 1 e, se querem estar na mesma sala, $J_{ij}$ será 1, então o resultado será 1. Se não podem e estão na mesma sala, o resultado será -1. Se não estão na mesma sala, o produto $S_i\cdot S_j$ é -1. Deu para entender que esse produto representa bem a “felicidade” gerada pelo estudo de um par de alunos. Precisamos, então somar $J_{ij}\cdot S_i\cdot S_j$ para todos os $i$’s e $ j$’s e isso dará a felicidade da configuração.

Mais uma vez, isso exige produtos e somas com $2^n$ configurações possíveis, é absolutamente impossível resolver esse problema na força bruta para mais de 50 alunos. Para tal, precisamos de um método mais eficiente, e eu escolho Monte Carlo.

O método de Monte Carlo é um dos mais poderosos e usados na física estatística para resolver esse tipo de problema impossível. Tomamos uma configuração inicial de classes aleatória (um vetor $S$ aleatório) e procedemos da seguinte forma:

  • Trocamos um aluno de sala (tiramos $i$ aleatório e fazemos $S_i\to -S_i$)
  • Checamos a felicidade da nova configuração.
  • Se aumentou, ele fica nessa sala nova.
  • Se diminuiu, ele volta para a primeira sala.

Você ficaria impressionado em saber que, com 50 alunos, eu consigo a configuração certa de $S$ em menos de 1000 iterações. Claro, tomei um $J$ agradável o suficiente para que eu soubesse qual a configuração certa e esse $J$ em particular provavelmente facilitou minha vida. Tomei a sala em panelinha: metade dela quer ficar entre si e não pode ficar com a outra metade. Eu esperava um S da forma $(1,1,\ldots ,1,-1,-1,\ldots ,-1)$, e o tenho rapidamente com esse algoritmo.

Sabendo um pouco mais de física, eu poderia te contar que os átomos possuem uma propriedade chamada spin, que pode apontar para cima (1) ou para baixo (-1). Em uma rede cristalina, os spins interagem e são capazes de definir muita coisa, como, por exemplo, se a rede será um imã ou não. O que acontece é que os spins sempre atingem uma configuração que minimiza a energia da rede, e essa energia é calculada se o material é antiferromagnético (os spins gostam de ficam em direções opostas) ou ferromagnético (eles preferem se alinhar). Em algumas redes, você até mistura esses dois tipos e calcular a magnetização total (o conjunto de todos os spins) pode parecer um inferno.

Mas a energia total é calculada da seguinte forma: você multiplica os spins para saber se estão alinhados ou não, se estão, o produto será positivo, se estão invertidos, o produto será negativo. E então você multiplica pelo fator $J_{ij}$, que vale 1 se o material é ferromagnético ou -1 se é antiferromagnético (ou 0 se os spins estão longe e não interagem). A energia total será a soma para todos os i’s e j’s de $J_{ij}\cdot S_i\cdot S_j$ onde $S_i$ é o spin da partícula $i$. A magnetização do sistema será a configuração de spins que minimiza essa energia. Ora, é difícil não ver que a magnetização de um material misto entre dia e ferromagnetismo é o exato mesmo problema que uma diretora de escola enfrenta ao escolher quais alunos ficarão em qual sala.

Esse método, Monte Carlo, parece quase milagroso, mas possui um problema grave. Não é o caso da matriz $J$ que escolhi, que é extremamente agradável, mas com algum outro $ J$ eu poderia ter um sério problema. Eu poderia atingir uma configuração em que trocar qualquer aluno de sala causaria uma queda na felicidade, mas que, se eu trocasse dois ou três, poderia ter um ganho. Esse tipo de situação é um “mínimo local” da felicidade, um defeito sério em Monte Carlo, que não pode escapar de um mínimo local e atingir a verdadeira configuração ideal de salas, pois ele só aceita ganhos reais e imediatos. Como podemos nos livrar disso? Ah, precisamos de uma adaptação de Monte Carlo, chamada “Algoritmo de Metrópolis”, mas isso fica para outro dia, a diretora da minha sétima série, pelo que escrevi, já terá bastante trabalho pela frente.

1 resposta