Jos´e Henrique Hildebrand Grisi Filho 5 1 0 2 n a J Caracteriza¸c˜ao de circuitos pecu´arios com base em 9 redes de movimenta¸c˜ao de animais ] M Q . o i b - q [ 1 v 8 7 2 2 0 . 1 0 5 1 : v i X r a S˜ao Paulo 2012 Jos´e Henrique Hildebrand Grisi Filho Caracteriza¸c˜ao de circuitos pecu´arios com base em redes de movimenta¸c˜ao de animais A D Tese apresentada ao Programa de Po´s-Graduac¸˜ao em I Epidemiologia ExperimentalGAplicada a`s Zoonoses da Faculdade de Medicina Veterin´aria e Zootecnia da Uni- I versidade de S˜ao PaRulo para obten¸c˜ao do t´ıtulo de Dou- tor em Ciˆencias R O C Departamento: O Medicina Veterin´aria Preventiva e Sau´de Animal ˜ A S R A´rea de concentra¸c˜ao: E Epidemiologia Experimental Aplicada a`s Zoonoses V Orientador: Prof. Dr. Marcos Amaku De acordo: Orientador(a) S˜ao Paulo 2012 Obs.: A vers˜ao original se encontra dispon´ıvel na Biblioteca da FMVZ/USP FOLHA DE AVALIAC¸A˜O Nome: Grisi Filho, Jos´e Henrique Hildebrand T´ıtulo: Caracterizac¸˜ao de circuitos pecu´arios com base em redes de movimentac¸˜ao de animais Tese apresentada ao Programa de Po´s-Graduac¸˜ao em Epidemiologia Experimental Aplicada a`s Zoonoses da Faculdade de Medicina Veterin´aria e Zootecnia da Uni- versidade de S˜ao Paulo para obten¸c˜ao do t´ıtulo de Dou- tor em Ciˆencias Data: / / BANCA EXAMINADORA Prof. Dr. : Instituic¸a˜o: Julgamento: Prof. Dr. : Instituic¸a˜o: Julgamento: Prof. Dr. : Instituic¸a˜o: Julgamento: Prof. Dr. : Instituic¸a˜o: Julgamento: Prof. Dr. : Instituic¸a˜o: Julgamento: Agradecimentos Ao Prof. Dr. Marcos Amaku, pela orientac¸˜ao, sabedoria, paciˆencia e confian¸ca; Ao Prof. Dr. Fernando Ferreira, por toda a ajuda, sugest˜oes, apoio e amizade; Aos colegas Raul e R´ısia, pelo trabalho em equipe sem o qual esta tese n˜ao seria a mesma; A` todos os colegas do LEB que fazem deste um excelente local de trabalho; A` minha fam´ılia, por tudo; Projeto financiado pela FAPESP e CNPq. Ao Instituto de Defesa Agropecu´aria do Estado do Mato Grosso, pela disponibilizac¸˜ao de dados essenciais ao trabalho. ` A todos que contribu´ıram, de forma direta ou indireta, para a conclus˜ao desta tese. RESUMO GRISI-FILHO, J. H. H. Caracteriza¸c˜ao de circuitos pecu´arios com base em redes de movimenta¸c˜ao de animais. [Characterization of production zones based on animal movement networks.] 2012. 46 f. Tese (Doutorado em Ciˆencias) - Faculdade de Medicina Veterin´aria e Zootecnia, Universidade de S˜ao Paulo, S˜ao Paulo, 2012. Uma rede ´e um conjunto de n´os conectados entre si por um conjunto de arestas. Redes podem representar qualquer conjunto de objetos que possuam relac¸˜oes entre si. Comu- nidades s˜ao conjuntos de n´os relacionados de uma maneira significativa, provavelmente compartilhando propriedades e/ou atuando de forma similar dentro de uma rede. Quando a an´alise de redes ´e aplicada ao estudo de padr˜oes de movimentac¸˜ao animal, as unidades epidemiol´ogicas de interesse (propriedades, estabelecimentos, munic´ıpios, estados, pa´ıses, etc) s˜ao representadas como n´os, enquanto a movimentac¸˜ao animal entre elas ´e repre- sentada por arestas de uma rede. Descobrir a estrutura de uma rede, e portanto as preferˆencias e rotas comerciais, pode ser u´til para um pesquisador ou gestor de sau´de animal. Foi implementado um algoritmo de detecc¸˜ao de comunidades para encontrar gru- pos de propriedades que ´e consistente com a definic¸˜ao de circuito pecua´rio, assumindo que uma comunidade ´e um grupo de n´os (fazendas, abatedouros) no qual um animal vai mais provavelmente permanecer durante sua vida. Este algoritmo foi aplicado na rede in- terna de movimentac¸˜ao animal de 2007 do Estado do Mato Grosso. Esse banco de dados cont´em informa¸c˜ao sobre 87.899 propriedades e 521.431 movimentac¸˜oes durante o ano, totalizando 15.844.779 de animais movimentados. O algoritmo de detecc¸˜ao de comunida- des encontrou uma partic¸˜ao da rede que mostra um claro padra˜o geogr´afico e comercial, duas importantes caracter´ısticas para aplica¸c˜oes em medicina veterin´aria preventiva, al´em de possuir uma interpretac¸˜ao clara e significativa em redes de com´ercio onde ligac¸˜oes se estabelecem a partir da escolha dos n´os envolvidos. Palavras-chave: Epidemiologia. Ana´lise de redes. Ana´lise de comunidades. Circuito pecu´ario. Movimentac¸˜ao animal. ABSTRACT GRISI-FILHO, J. H. H. Characterization of production zones based on animal movement networks. [Caracteriza¸c˜ao de circuitos pecu´arios com base em redes de movimentac¸˜ao de animais.] 2012. 46 f. Tese (Doutorado em Ciˆencias) - Faculdade de Medicina Veterin´aria e Zootecnia, Universidade de S˜ao Paulo, S˜ao Paulo, 2012. A network is a set of nodes that are linked together by a set of edges. Networks can represent any set of objects that have relations among themselves. Communities are sets of nodes that are related in an important way, probably sharing common properties and/or playing similar roles within a network. When network analysis is applied to study the livestock movement patterns, the epidemiological units of interest (farm premises, counties, states, countries, etc.) are represented as nodes, and animal movements between the nodes are represented as the edges of a network. Unraveling a network structure, and hence the trade preferences and pathways, could be very useful to a researcher or a decision-maker. We implemented a community detection algorithm to find livestock communities thatisconsistent withthedefinitionofalivestock productionzone, assuming that a community is a group of farm premises in which an animal is more likely to stay during its life time than expected by chance. We applied this algorithm to the network of within animal movements made inside the State of Mato Grosso, for the year of 2007. This database holds information about 87,899 premises and 521,431 movements throughout the year, totalizing 15,844,779 animals moved. The community detection algorithm achieved a network partition that shows a clear geographical and commercial pattern, two crucial features to preventive veterinary medicine applications, and also has ameaningful interpretation intradenetworks where linksemerge fromthechoice oftrader nodes. Keywords: Epidemiology. Network analysis. Community analysis. Livestock production zone. Animal movement. SUMA´RIO 1 INTRODUC¸A˜O 8 1.1 Redes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2 An´alise de Comunidades em Medicina Veterin´aria . . . . . . . . . . . . 9 1.3 Defini¸c˜ao de Comunidade e Circuitos Pecu´arios . . . . . . . . . . . . . 11 2 MATERIAIS E ME´TODOS 13 2.1 Base de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Detec¸c˜ao de circuitos pecu´arios . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.1 Nu´mero de Bell, ma´ximos locais e ma´ximos globais . . . . . . . . . . . . . . 16 2.2.2 Otimizac¸˜ao da fun¸c˜ao de modularidade . . . . . . . . . . . . . . . . . . . . . 17 2.2.3 Obten¸c˜ao de uma solu¸c˜ao u´nica . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3 Avalia¸c˜ao do desempenho do algoritmo . . . . . . . . . . . . . . . . . . . 21 2.3.1 Escalonamento multidimensional . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4 Softwares utilizados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3 RESULTADOS 24 4 DISCUSSA˜O 30 5 CONCLUSO˜ES 36 REFEREˆNCIAS 37 APEˆNDICE 40 8 1 INTRODUC¸A˜O 1.1 Redes Uma rede ´e um conjunto de n´os (ou v´ertices) conectados entre si por um con- junto de arestas (ou ligac¸˜oes), como demonstrado na figura 1.1. Redes podem representar qualquer conjunto de objetos que possuam relac¸˜oes entre si. Podem, por exemplo, re- presentar as relac¸˜oes sociais entre indiv´ıduos (figura 1.2). Em uma rede ponderada cada aresta possui um valor, que representa a intensidade da ligac¸˜ao entre dois n´os. Redes podem ser direcionadas e n˜ao-direcionadas: uma rede direcionada apresenta a direc¸˜ao da relac¸˜ao entre dois n´os, sendo portanto uma ligac¸˜ao de sa´ıda para um e uma ligac¸˜ao de entrada para o outro; uma rede n˜ao-direcionada assume que a relac¸˜ao entre dois n´os ´e sempre rec´ıproca. Em uma rede direcionada e ponderada, o grau de entrada de um n´o (kin) ´e o nu´mero de n´os conectados a este por ligac¸˜oes de entrada, enquanto o grau de i sa´ıda (kout) ´e o nu´mero de n´os conectados a este por ligac¸˜oes de sa´ıda. Analogamente, o i grau ponderado de entrada (kwin) ´e a soma dos valores das arestas que um n´o recebe, e i o grau ponderado de sa´ıda (kwout) ´e a soma dos valores das arestas que um n´o envia. O i grau ponderado total (kw ) ´e igual `a soma dos graus ponderados de entrada e de sa´ıda, i enquanto o grau total (k ) ´e o nu´mero de n´os ligados ao n´o de interesse, independente da i direc¸˜ao da ligac¸˜ao. Figura 1.1 - Ilustra¸c˜ao de uma rede, com indica¸c˜ao de n´os e arestas Quando a an´alise de redes ´e aplicada ao estudo da movimentac¸˜ao animal dentro de um sistema produtivo, as unidades epidemiol´ogicas de interesse (propriedades, esta- belecimentos, munic´ıpios, estados, pa´ıses, etc) s˜ao representadas como n´os, enquanto a 9 Figura 1.2 - Rede de associa¸c˜oes frequentes entre 62 golfinhos de Doubtful Sound, New Zealand (Lusseau et al., 2003) movimentac¸˜ao animal entre elas ´e representada por arestas de uma rede, onde o valor de cada aresta traz o nu´mero de animais comercializados entre dois n´os. Assim, o grau de entrada de um n´o equivale `a quantidade de unidades que enviaram animais para este e o grau de sa´ıda equivale `a quantidade de estabelecimentos para os quais um n´o enviou animais. O grau ponderado de entrada equivale `a quantidade de animais comprados e o grau ponderado de sa´ıda equivale `a quantidade de animais vendidos por uma propriedade. A an´alise de redes tˆem sido utilizada para estudar uma grande variedade de problemas dentro da medicina veterin´aria, incluindo an´alises de epidemias (Gibbens et al., 2001), an´alises etolo´gicas (Lusseau e Newman, 2004), padr˜oes de distribuic¸˜ao de doenc¸as, mo- delos preditivos (Harvey et al., 2007), an´alises de risco, efic´acia de sistemas de vigilaˆncia entre outros. Mart´ınez-Lo´pez, Perez e S´anchez-Vizca´ıno (2009) fazem uma revisa˜o sobre o assunto. 1.2 An´alise de Comunidades em Medicina Veterin´aria Comunidades s˜ao conjuntos de n´os relacionados entre si de uma maneira signifi- cativa, provavelmente compartilhando propriedades e/ou atuando de forma similar dentro de uma rede. Estudos recentes utilizaram a an´alise de comunidades em redes de traˆnsito animal com o intuito de revelar a estrutura subjacente da rede (Green, Gregory e Munro, 2009; Green et al., 2011; Lentz et al., 2011). 10 Descobrir essa estrutura e portanto as preferˆencias de com´ercio entre proprieda- des pode se mostrar u´til para um pesquisador ou tomador de decisa˜o. Em primeiro lugar, permite a identificac¸˜ao dos fluxos de com´ercio entre zonas de produ¸c˜ao, possibilitando um melhor entendimento do sistema de produ¸c˜ao animal. A existˆencia e funcionalidade de grupos dentro de uma rede pode influenciar o espalhamento de doenc¸as, alterando a velocidade de espalhamento, o tamanho final e a dura¸c˜ao de uma epidemia (Salath´e e Jones, 2010). Ana´lises de comunidade poderiam ser usadas para determinar os grupos de uma amostra estratificada que visa levar em considera¸c˜ao o traˆnsito animal, ou ajudar no planejamento de um sistema de vigilaˆncia voltado ao risco, escolhendo grupos de n´os sob risco que possuam intenso com´ercio entre si. Seria poss´ıvel, na ocasia˜o de erradicac¸˜ao de uma doenc¸a espec´ıfica, dividir um programa sanita´rio em etapas nas quais um grupo de munic´ıpios ´e sanitizado por vez, caso esses munic´ıpios apresentem baixo risco de rein- fecc¸˜ao devido a movimentos oriundos de fora do grupo. Propriedades que compartilham preferˆencias comerciais podem compartilhar pra´ticas de manejo e biosseguran¸ca, e serem selecionadas para um programa sanita´rio direcionado. A Organiza¸c˜ao Mundial de Sau´de Animal(OIE),defineemseuTerrestrialAnimalHealthCode(WorldOrganisationforAni- mal Health, 2010), os conceitos de zoneamento, regionaliza¸c˜ao e compartimento. Dada a dificuldade de estabelecer e manter uma condic¸˜ao livre de doenc¸a para o territo´rio de um pa´ıs inteiro, pode ser vantajoso estabelecer e manter uma subpopula¸c˜ao com condic¸˜ao sanita´ria diferenciada dentro de seu territo´rio. Assim, a delimita¸c˜ao de zonas sanita´rias dentro de uma regia˜o pode levar em considera¸c˜ao n˜ao apenas munic´ıpios com as mesmas condic¸˜oes sanita´rias, mas tamb´em regio˜es que possuam intenso com´ercio com estes. A an´alise de comunidades pode ajudar no planejamento da fronteira deste tipo de a´rea, caso haja isolamento de uma subpopula¸c˜ao (p.ex, com restric¸˜ao de movimentac¸˜ao), bloque- ando o com´ercio entre fazendas de ´areas diferentes: essa abordagem poderia otimizar a divisa˜o de tal regia˜o e avaliar quanta perda econˆomica ´e esperada devido a restric¸˜ao de com´ercio ap´os uma zona espec´ıfica ser estabelecida. Essess˜aoapenasalgunsexemplos. Comoumat´ecnicaexplorat´oria,suasaplica¸c˜oes s˜ao virtualmente infinitas, facilitando a formula¸c˜ao de novas hip´oteses, a avaliac¸˜ao de pre-