Modelos de propagação de epidemias usando redes complexas

˜ PAULO UNIVERSIDADE DE SAO Instituto de Ciˆ encias Matem´ aticas e de Computa¸c˜ ao

Trabalho de Conclus˜ ao de Curso

Aluna Priscila Gutierres

Orientadora Cynthia de Oliveira Lage Ferreira

S˜ ao Carlos 2 Semestre de 2016 o

No USP 6418942

2

Resumo Neste trabalho discutiremos um modelo simples de um problema de propaga¸ca ˜o de epidemias usando o modelo SEIR, redes complexas e o pacote NetworkX para a linguagem Python.

3

1

Introdu¸ c˜ ao

Ao longo da hist´ oria da humanidade, as epidemias tem tido um grande impacto na sociedade humana. No Brasil, um dos desafios da sa´ ude p´ ublica ´e a dengue, doen¸ca que provavelmente existiu no Brasil desde o per´ıodo colonial, de origem africana que teria sido introduzida da mesma maneira que a febre amarela, j´a que seu vetor ´e o mesmo, o A. aegypti [1]. O mecanismo de transmiss˜ ao de uma doen¸ca ´e conhecido para a maioria das doen¸cas infecciosas; no entanto, as intera¸c˜ oes ocorridas ao longo da transmiss˜ ao s˜ ao muito complexas, e desse modo se faz necess´ario um modelo formal matem´ atico. Neste trabalho discutiremos a modelagem de um problema de propaga¸c˜ao de epidemias utilizando uma modelagem an´ aloga a feita em [2]. Para a simula¸c˜ ao escolhemos um modelo constitu´ıdo de quatro est´agios discretos: suscet´ıvel, exposto, infectado e resistente, o modelo SEIR. De modo simplificado, nesse modelo indiv´ıduos inicialmente suscet´ıveis podem se tornar expostos ap´os o contato com indiv´ıduos infectados.Indiv´ıduos expostos n˜ ao podem espalhar a doen¸ca at´e o ponto em que se tornam infectados. Ap´ os algum tempo, indiv´ıduos infectados se tornam resistentes, isto ´e, n˜ao podem espalhar a doen¸ca e n˜ao s˜ ao mais suscet´ıveis a ela. Ao contr´ ario de outros modelos, que descrevem epidemias por equa¸c˜oes diferenciais, utilizamos um modelo baseado em redes complexas.

Figura 1: O modelo SEIR

4

2

Descri¸ c˜ ao do problema

Cada epidemia possui um modo diferente de se espalhar dependendo, claramente, do tipo de doen¸ca e suas caracter´ısticas como tempo de latˆencia e infectuosidade. Mas o modo como ela se espalha depende tamb´em da conex˜ ao dos indiv´ıduos e por isso uma estrutura de rede ´e adequada para representar esse tipo de problema. Queremos analisar como uma epidemia se comporta nos trˆes tipos de rede apresentados adiante, a saber: redes aleat´ orias, redes pequeno mundo e redes livre escala.

2.1

Descri¸c˜ ao te´ orica

As redes complexas prov´em um modelo estrutural que torna poss´ıvel analisar e entender como sistemas separados interagem juntos. S˜ ao usadas eficientemente para simular diversos sistemas biol´ogicos como trocas celulares, redes de neurˆ onios , propaga¸c˜ oes de epidemias, entre outros. Uma rede complexa envolve o formalismo matem´atico da Teoria dos Grafos e a an´alise baseada em ferramentas da Estat´ıstica. Uma rede complexa ´e um conjunto de dados discreto associado a n´os ou v´ertices cuja liga¸c˜ao entre si ´e feita por uma aresta. Seu estudo ´e motivado pelo desejo de entender sistemas que v˜ao desde redes de comunica¸c˜ao entre pessoas at´e sistemas biol´ ogicos como redes de trocas inter-celulares. Por defini¸c˜ao, um grafo ou uma rede ´e uma cole¸c˜ ao de n´ os ligados entre si por v´ertices. Algumas das propriedades b´asicas de uma rede s˜ao o seu grau, distˆancia, diˆ ametro. A rede pode ser orientada ou n˜ ao orientada. Uma rede orientada determina a dire¸c˜ao das arestas entre os v´ertices, e as n˜ ao orientadas n˜ ao possuem dire¸c˜ ao, pois a aresta ´e definida nos dois sentidos. Dois n´os conectados por uma aresta s˜ ao ditos incidentes ` a aresta. O grau de um n´o ´e o n´ umero de arestas incidentes a ele, com la¸cos contados duas vezes. Um caminho ´e definido pelas arestas que dever˜ao ser percorridas entre um par de v´ertices. J´a a distˆancia ´e definida de um n´ o a outro e ´e definida pelo menor caminho (n´ umero de arestas) entre eles. Caso eles sejam desconectados, definimos que a distˆ ancia entre eles ´e infinita. Definimos o diˆametro de uma rede complexa como a distˆancia m´ axima entre quaisquer dois n´ os presentes na rede. Exemplo 1. Em 1727 Euler come¸cou o estudo de grafos resolvendo o que hoje ´e conhecido como o problema da ponte de K¨ onigsberg, situado na cidade de K¨onigsberg Alemanha (atual Kaliningrad, parte da R´ ussia). Em K¨ onigsberg, havia sete pontes conectando quatro ilhas. O problema original consistia em saber se era poss´ıvel atravessar todas as sete pontes sem passar duas vezes pela mesma. O problema pode ser representado pela rede a seguir:

Figura 2: O problema das pontes de K¨onigsberg Como Euler provou em 1735, n˜ ao existe nenhum caminho nessa rede que passe por cada ponte (aresta) uma s´ o vez. No nosso estudo utilizamos redes randˆ omicas, redes pequeno mundo gerado por algoritmo proposto por Watts and Strogatz [1998] e redes livre escala criados por liga¸c˜oes preferˆenciais descritos por Barab´asi e Albert [1999] para efetuar as simula¸c˜ oes desejadas.

5

2.1.1

Redes aleat´ orias

Redes aleat´ orias s˜ ao aquelas em que arestas n˜ ao direcionadas s˜ao adicionadas aleatoriamente entre um n´ umero fixo de N v´ertices ou n´ os. Esse tipo de rede foi extensivamente estudada por Erd¨os and R´enyi. Redes aleat´ orias podem ser usadas como uma primeira aproxima¸c˜ao para redes cuja estrutura desconhecemos, com exce¸c˜ ao de seus n´ umeros de n´ os e arestas. Numa rede aleat´oria n˜ao existe nenhum crit´erio que privilegie umas liga¸c˜ oes em rela¸c˜ ao a outras, logo ela ´e caracterizada pelo n´ umero de n´os N e pela probabilidade p de que uma liga¸c˜ ao qualquer das n(n−1) poss´ ıveis liga¸ c o ˜ es entre n´ o s diferentes seja estabelecida. 2 Podemos obter uma rede aleat´ oria utilizando os seguintes passos: 1. Pegamos uma cole¸c˜ ao de n´ os; 2. Atribu´ımos a cada par de n´ os uma probabilidade p de estarem ligados ou n˜ao e a calculamos em cada ponto. Ligando-os ou n˜ ao de acordo com a probabilidade dada. Denotamos esse modelo por G(N, p). Note que o grau ´e dado por N (N2−1) p. No nosso modelo utilizamos um n´ umero fixo de arestas N. Definimos k = N (N2−1) , de modo que o n´ umero de arestas ´e tal que cada arranjamento entre elas ´e igualmente prov´avel, obtendo o modelo de redes aleat´orias dado por G(N, k). Essa abordagem ´e conveniente pois proporciona uma melhor compara¸c˜ao dos nossos resultados entre diferentes tipos de grafos. 2.1.2

Redes mundo pequeno

Observando que redes sociais s˜ ao interdependentes umas das outras, ´e plaus´ıvel presumir que em algum n´ıvel as pessoas estejam ligadas entre si. Em 1960, Stanley Milgram foi o primeiro a realizar um experimento de separa¸c˜ ao entre as pessoas [Degenne e Forse 1999, Barabasi 2003]. Seu experimento consistiu em enviar cartas `a diversos indiv´ıduos, de forma aleat´ oria, solicitando que tentassem enviar a um alvo espec´ıfico. Caso n˜ ao o conhecessem, elas eram solicitadas ent˜ao a enviar uma carta a algu´em que acreditassem estar mais perto dessa pessoa. Isso poderia indicar que as pessoas estariam a poucos graus de separa¸c˜ao uma das outras, vivendo em um ”mundo pequeno”[Recuero 2004]. Al´em disso, em seus estudos, Mark Granovetter (1973), descobriu que la¸cos fracos seriam muito mais importantes que la¸cos fortes os quais recebiam muito mais aten¸c˜ao em estudos anteriores. Al´em disso, Granovetter demonstrou que pessoas que compartilhavam la¸cos fortes (de amigos pr´oximos, por exemplo) em geral participavam de um mesmo c´ırculo social (de um mesmo grupo que seria altamente clusterizado). J´ a pessoas com quem se tinha um la¸co mais fraco, ou seja, conhecidos ou amigos distantes, eram justamente importantes porque conectariam v´ arios grupos sociais. Desse modo, o trabalho de Granovetter real¸ca a importˆancia das tr´ıades nas redes sociais, demonstrando que elas n˜ ao s˜ ao simplesmente aleat´ orias. A partir do experimento de Milgram e das teorias de Granovetter, Ducan Watts e seu orientador Steven Strogatz [Watts 1999] descobriram que as redes sociais apresentavam padr˜oes altamente conectados, tendendo a formar pequenas quantidades de conex˜oes entre cada indiv´ıduo. Eles criaram um modelo semelhante ao de Erd¨ os e R´enyi, onde os la¸cos eram estabelecidos entre as pessoas mais pr´oximas e alguns la¸cos estabelecidos de modo aleat´ orio entre alguns n´ os transformavam a rede em um mundo pequeno [Watts 1999,Recuero 2004]. Uma das propriedades fundamentais de redes pequeno mundo ´e que o diˆametro da rede cresce lentamente com o aumento do tamanho da rede. Especificamente, o crescimento da rede ´e logaritico, e essa ´e uma caracter´ıstica compartilhada com redes aleat´ orias. Por´em, ao contr´ario de redes aleat´orias, elas s˜ao altamente clusterizadas e possuem uma topologia an´ aloga a de redes sociais descritas acima. E tamb´em, ao contr´ario de redes livre escala n˜ ao possuem uma distribui¸c˜ ao de graus que segue a lei das potˆencias de n´os. Elas podem ser criadas a partir do modelo descrito por Watts and Strogatz [1998] come¸cando-se com uma rede regular e sendo aleatoriamente religadas a uma dada fra¸c˜ ao de p de arestas.

6

Os casos limites p=0 e p=1 correspondem, respectivamente, a redes completamente regulares e redes completamente aleat´ orias. Para alguns valores intermedi´ arios de p, a rede resultante tem algumas propriedades de rede aleat´ orias (diˆ ametro com crescimento lento) e outras propriedades que lembram redes regulares (alta clusteriza¸c˜ao).

Figura 3: Redes geradas a partir do modelo de Watts e Strogatz obtidas com diferentes parˆametros de p

2.1.3

Redes livre escala

Um fenˆ omeno frequentemente observado em redes reais ´e que existem n´os com conectividade muito superior ` a m´edia assim como n´ os com conectividade muito inferior `a m´edia. Um exemplo de uma rede desse tipo ´e a rede Web. Um hub ´e, por defini¸c˜ ao, um n´ o com um n´ umero de arestas que excede em muito a m´edia de liga¸c˜oes entre os n´ os da rede. Redes livre escala seguem a lei da potˆencia, ao contr´ario do que acontece nas redes aleat´orias ou pequeno mundo, o grau dos n´ os n˜ ao tem um valor t´ıpico e existem n´os com todos os graus poss´ıveis, tendo uma distribui¸c˜ ao 1 probabil´ıstica de graus dada por P (k) = k r . Esse m´etodo de criar tal rede foi proposto por Barab´asi e Albert [1999] e ´e baseado na adi¸c˜ao em sequˆencia de v´ertices onde cada v´ertice ´e conectado a um dado n´ umero de v´ertices previamente colocados com probabilidade proporcional ` a seus graus, isto ´e, 1. o sistema se expande pela adi¸c˜ ao de novos n´os ligando-os `a n´os j´a existentes na rede; 2. a liga¸c˜ ao ´e feita de forma preferencial, isto ´e, um novas arestas sempre se conectam a n´os que j´a existem. Esse processo acontece com uma maior probabilidade quando as vizinhan¸cas apresentam um grande n´ umeros de n´ os vizinhos. Redes que apresentam essa propriedade s˜ ao chamadas convenientemente de redes livre escala, j´a que n˜ao possuem uma escala caracter´ıstica de conectividade.

Figura 4: Rede complexa gerada a partir do modelo de Barabasi e Albert

7

3

Algoritmo e implementa¸ c˜ ao

3.1

Vari´ aveis de estado e Parˆ ametros

Seja I um indiv´ıduo e Ii o estado do indiv´ıduo, sendo {−1} ∪ {0} ∪ {1, 2, ..., L} respectivamente correspondentes aos est´ agios de resistˆencia, suscetibilidade ou est´agio de infec¸c˜ao. Cada um desses indiv´ıduos possui um parˆ ametro λi ∈ {λ1 , ..., λn } que determina a probabilidade dele transmitir a doen¸ca no est´ agio que se encontra, sendo λi = 0 para os indiv´ıduos resistentes e suscet´ıveis. Pn Para facilitar, normalizamos k de forma que i λi = 1. Introduzimos um parˆametro k que multiplica todos os valores λi quando calculamos as probabilidades de transmiss˜ao. O algoritmo segue as etapas a seguir: 1. O indiv´ıduo suscet´ıvel i se torna infectado (seu estado muda para I1 ) com probabilidade dada por uma soma de pesos dos ´ındices de infectuosidade dos seus vizinhos, de forma que: X Pinf ec (i) = k wij αs (j) j

que ´e a soma de todos os vizinhos infectados j do indiv´ıduo i, wi j ´e o peso das arestas conectando i e j. Temos que s(j) ´e o n´ umero do est´ agio de infec¸c˜ao que o indiv´ıduo j est´a. Nesse trabalho, wij = 1, pois os n´ os n˜ ao tem peso. 2. Indiv´ıduos infectados mudam do estado In para o estado In+1 a menos que esteja no est´agio n = L, quando se torna resistente. 3. Indiv´ıduos resistentes permanescem resistentes. A u ´nica etapa estoc´astica do modelo ´e a transmiss˜ ao da doen¸ca. Depois que um indiv´ıduo se torna infectado, a evolu¸c˜ao do quadro ´e totalmente determin´ıstica e ´e dada por: L L X Y kαn wij = kwij (1 − kαn wij ) ≈ 1− n=1

n=1

O parˆ ametro k tem uma interpreta¸c˜ ao relativamente simples quando k → 0 Ele expressa a probabilidade da doen¸ca se espalhar de um indiv´ıduo para o seu vizinho em algum ponto do tempo. A representa¸c˜ ao canˆ onica de uma rede complexa no computador ´e feita utilizando uma matriz chamada matriz de adjacˆencia ou uma lista de adjacˆencia. Assim, dado um grafo G(E, V ) com E arestas e V v´ertices, temos a seguinte representa¸c˜ ao matricial em uma rede n˜ao-direcionada: aij = 1 aij = 0

se existir aresta de i a j se n˜ ao existir aresta de i at´e j.

Caso rede seja direcionada, aij indica a presen¸ca um grafo com uma aresta indo do n´o i ao n´o j e podemos ter uma matriz n˜ ao-sim´etrica. No caso em estudo nesse trabalho a rede n˜ ao ´e direcionada e a matriz ´e sim´etrica. Podemos ainda atribuir pesos a arestas de modo determin´ıstico ou usando alguma distribui¸c˜ao de probabilidade para cada uma das arestas.Para isso, convencionamos aij seja 0 apenas se n˜ao houver liga¸c˜ao entre os n´ os, e os pesos ent˜ ao podem ser n´ umeros positivos ou negativos.

3.2

Pacotes usados

Neste trabalho utilizamos os pacotes NetworkX e Numpy para, respectivamente, gerar as redes aleat´ orias e a matriz de adjacˆencia na linguagem de programa¸ca˜o Python. O NewtorkX ´e um pacote para a linguagem Python

8

que possibilita a cria¸c˜ ao, manipula¸c˜ ao e o estudo das estruturas, dinˆamicas e fun¸c˜oes de redes complexas. Ele prov´em estrutura para o estudo da estrutura e dinˆamica de fenˆomenos sociol´ogicos, biol´ogicos, econˆomicos em uma interface de programa¸c˜ ao padr˜ ao com implementa¸c˜ao de grafos que pode ser usada para a implementa¸c˜ ao em projetos diversos. Numpy ´e um pacote para a linguagem Python que, entre outras coisas, cont´em um objeto de matrix N-dimensional otimizado, objetos e fun¸c˜ oes para c´ alculos diversos usados em computa¸c˜ao cient´ıfica.

3.3 3.3.1

Implementa¸c˜ ao Fun¸ c˜ ao geradora da rede aleat´ oria

#!/usr/bin/env python # -*- coding: utf-8 -*import random import networkx as nx import numpy as np def rede_aleatoria(n, d): """Retorna a matriz de adjacencia de rede aleatoria G{n,p}. Parametros ---------n : int O numero de nos p : float Probabilidade para a criacao de uma aresta. (default = 0.5). """ G = nx.to_numpy_matrix(nx.random_regular_graph(d,n))

return G 3.3.2

Fun¸ c˜ ao geradora da rede pequeno mundo

#!/usr/bin/env python # -*- coding: utf-8 -*import random import networkx as nx import numpy as np def rede_watts_strogatz(n, k, , p = 0.5): """Retorna uma matriz de adjacencia de do tipo small-world de acordo com o modelo de Watts e Strogatz G{n,m}. Parametros

9

---------n : int O numero de nos k : int Cada no e conectado aos k vizinhos proximos em topologia de anel p: float A probabilidade de religacao de cada aresta """ G = nx.to_numpy_matrix(nx.watts_strogatz_graph(n,k,p))

return G 3.3.3

Fun¸ c˜ ao geradora da rede livre escala

#!/usr/bin/env python # -*- coding: utf-8 -*import random import networkx as nx import numpy as np def rede_sem_escala(n, m): """Retorna uma matriz de adjacencia de do tipo scale-free de acordo com o modelo de Barabasi e Albert G{n,m}. Parametros ---------n : int O numero de nos m : int O numero de arestas """ G = nx.to_numpy_matrix(nx.barabasi_albert_graph(n,m))

return G 3.3.4

Fun¸ c˜ ao o passo epidˆ emico

import numpy as np import random def passo_epidemico(estado_anterior, grafo, doenca, k): """Retorna um vetor com o novo estado dos nos apos uma iteracao do passo de evolucao da epidemia.

10

Parametros ---------estado_anterior : vetor Estado anterior dos nos grafo: matrix n x n Matriz de adjacencia de uma rede complexa doenca: vetor Estagios da doenca k: float Fator de infectuosidade relativa """ novo_estado = np.matrix([[0 for i in xrange(1)] for r in xrange(0,estado_anterior.size)]) infectuosidade = np.matrix([[0.0 for i in xrange(1)] for r in xrange(0, estado_anterior.size)]) for individuo in xrange(0, estado_anterior.size): if estado_anterior.item(individuo) > 0: infectuosidade.itemset(individuo,doenca.item(estado_anterior.item(individuo) -1) )

prob = (grafo*infectuosidade)*k for individuo in range(0, estado_anterior.size):

if(estado_anterior.item(individuo) > 0): if (estado_anterior.item(individuo) == doenca.size): novo_estado.itemset(individuo,-1) else: novo_estado.itemset((individuo), estado_anterior.item(individuo) + 1)

elif (estado_anterior.item(individuo) == 0): if ( random.random() < prob.item(individuo)): novo_estado.itemset(individuo,1) elif (estado_anterior.item(individuo) == -1): novo_estado.itemset(individuo, -1) return novo_estado 3.3.5

Fun¸ c˜ ao para o hist´ orico

import numpy as np from copy import deepcopy

11

import new_state_print import sir def historico(estados_iniciais, grafo, doenca, k): """Retorna uma lista com o historico do numero de nos em cada um dos estados de acordo com o modelo sir Parametros ---------estados iniciais : vetor Informa o estado inicial de cada um dos nos grafo : matriz Matriz de adjacencia da rede complexa doenca : vetor Vetor com o os valores dos diferentes estagios da doenca k: int Coeficiente relativo de infectuosidade """ L = [] estados = deepcopy(estados_iniciais) count = sir.sir(estados_iniciais) estados = new_state_print.passo_epidemico(estados_iniciais, grafo, doenca,k) while (count.item(1) > 0): #L.append(count.transpose().tolist()) estados = new_state_print.passo_epidemico(estados, grafo, doenca,k) count = sir.sir(estados) L.append(count.transpose().tolist()) return L 3.3.6

Fun¸ c˜ ao de estados SIR

import numpy as np def sir(estados): """Retorna um vetor com o numero de individuos nos estado S, I ou R. Parametros ---------estados : vetor com o estado dos nos da rede """ vetor = np.array([0 for i in xrange(3)] ) for individuo in range(0, estados.size): if (estados.item(individuo) == 0): vetor.itemset(0, vetor.item(0) + 1)

12

elif (estados.item(individuo) == -1): vetor.itemset(2, vetor.item(2) + 1) else: vetor.itemset(1, vetor.item(1) + 1) return vetor

13

4

Resultados e Discuss˜ ao

4.1

Parˆ ametros das simula¸c˜ oes

Nosso modelo permite que mudemos diversos parˆametros do sistemas para que possamos estudar a influˆencia dessas mudan¸cas na epidemia. Para um dado tipo de rede esses parˆametros s˜ao o tamanho N da rede, o grau m´edio d de seus v´ertices, e o vetor (α1 , ..., αL ) de infectuosidade da doen¸ca e a constante de infectuosidade relativa, k. Escolhemos um conjunto de parˆ ametros padr˜ ao, a saber: • tamanho da rede: N = 400 • grau m´edio: d = 6.0 • vetor de infectuosidade da doen¸ca: (0.000, 0.000, 0.0250, 0.075, 0.175, 0.225, 0.250, 0.250) Como nos est´ agios 1 e 2 as entradas s˜ ao nulas, a doen¸ca n˜ao ´e propagada nesses dois est´agios que caracterizam o est´ agio de latˆencia do modelo SEIR. • infectuosidade relativa: k = 0.3 e 0.5.

4.2

Simula¸c˜ ao

Na simula¸c˜ ao, azul corresponde ao est´ agio suscet´ıvel, vermelho ao infectado e verde ao resistente. Para cada um dos tipos de rede com k = 0.2 foram obtidos os seguintes gr´aficos:

(a) Redes aleat´ orias

(b) Redes livre escala

(c) Redes pequeno mundo

Para cada um dos tipos de rede com k = 0.5 foram obtidos os seguintes gr´aficos:

14

(d) Redes aleat´ orias

(e) Redes livre escala

(f) Redes pequeno mundo

5

Conclus˜ ao

Utilizamos o Networkx, Numpy e a linguagem Python para implementar um modelo simples de epidemias descrito por redes aleat´ orias, sem escala e pequeno mundo. Para decidir qual classe de redes d´a os resultados mais realista, ´e necess´ ario comparar cuidadosamente a sa´ıda das simula¸c˜oes com os dados de uma epidˆemia no mundo real. Outros parˆ ametros como o n´ umero de n´ os, a varia¸ca˜o do grau e os est´agios de infec¸c˜ao podem ser usados para estudos futuros.

15

ˆncias Refere [1] da Silva, Luiz Jacintho; Angerami, Rodrigo Nogueira ., Viroses emergentes no Brasil. Editora FIOCRUZ. 22 2008,43. [2] Jaquet, V.; Pechal, M., Epidemic spreading in a social network. Swiss Federal Institute of Technology Zurich. [3] G. A. Mendes; L. R. da Silva, Braz. J.Generating more realistic complex networks from power-law distribution of fitness. vol.39 no.2a S˜ ao Paulo Aug. 2009 [4] Costa, Luciano da F.;Rodrigues, Francisco A.; Alexandre S. Cristino, Complex networks: the key to systems biology. Genet. Mol. Biol. vol.31 no.3 S˜ ao Paulo 2008 [5] Batista, Andr´e Filipe de Moraes. Um Estudo sobre a Perspectiva da Modelagem de Sistemas Multiagentes via a Teoria das Redes Sociais. Monografia - Ciˆencia da Computa¸c˜ao, Universidade Federal do ABC, 2009.