A vasta quantidade de informações disponível sobre qualquer área de conhecimento torna cada vez mais difícil selecionar e analisar informações específicas e relevantes sobre determinado assunto. Com isso, faz-se necessário o aprimoramento de técnicas automáticas para recuperação, análise e extração de conhecimento em conjuntos de dados, destacando-se dessa forma as pesquisas em Aprendizado de Máquina e em Mineração de Dados. Em aprendizado de máquina e em mineração, a grande maioria das técnicas utiliza-se de uma representação proposicional dos dados, que considera apenas caracter características individuais dos objetos descritos em uma tabela atributo-valor. Porém, existem aplicações nas quais além da descrição dos objetos também estão disponíveis informações sobre relações existentes entre eles. Esses domínios podem ser representados via grafos, nos quais vértices representam objetos e arestas relações entre objetos, possibilitando a aplicação de técnicas relacionais aos dados. Conceitos de Redes Complexas (RC) podem ser utilizados neste contexto. RC é um campo de pesquisa recente e ativo, que estuda o comportamento de diversos sistemas reais, modelados via grafos. Entretanto, ainda há poucos trabalhos que utilizam Redes Complexas em aprendizado de máquina ou mineração de dados. Este projeto apresenta uma proposta de utilização do formalismo de redes complexas e grafos para descoberta de padrões no contexto de aprendizado supervisionado. O formalismo de grafos permite representar as relações entre objetos e características particulares do domínio, permitindo agregar informações estruturais das relações à descoberta de conhecimento. Especificamente, neste trabalho desenvolve-se uma representação relacional baseada em grafos construídos a partir de relações de similaridade entre objetos. Baseado nesta representação são propostas abordagens de classificação relacional. Também é proposto um modelo de rede denominado K-Associados. Propriedades da rede K-Associados foram investigadas. Os resultados experimentais demonstram um grande potencial para classificação utilizando os algoritmos de classificação e de formação de redes propostos / The vast amount of information available on any area of knowledge makes selecting and analyzing information on a specific topic increasingly dificult. Therefore, it is necessary the improvement of techniques for automatic information retrieval, analysis, and knowledge extraction from data sets. In this scenario, especial attention must be addressed for Machine Learning and Data Mining researches. In machine learning and data mining, most of the techniques uses a propositional representation, which considers only the characteristics of the objects described into an attribute-value table. However, there are domains where, in addition to the description of the objects, it is also available information about relationship between them. Such domains can be represented by graphs where vertices represent objects and edges relationship between objects, enabling the application of techniques for relational data. Concepts of complex networks (CN) can be useful in this context. CN is a recent and active research field, which studies the behavior of many real systems modeled by graphs. However, there is little work in machine learning or data mining applying CN concepts. This project presents a proposal to use the formalism of complex networks and graphs to discover patterns in the context of supervised learning. The formalism of graphs can represent relationships between objects and characteristics of the domain, allowing adding structural knowledge embedded in a graph into the data mining process. Specifically, this work develops a relational representation based on graphs constructed taking into consideration the similarity between objects. Based on this representation, relational classification approaches are proposed. It is also proposed a network referred to K-Associate Network. Properties of the K-Associate Network were investigated. The experimental results show great potential for the proposed classification and network construction algorithms

Redes são representações poderosas para muitos sistemas complexos, onde vértices representam elementos do sistema e arestas representam conexões entre eles. Redes Complexas podem ser definidas como grafos de grande escala que possuem distribuição não trivial de conexões. Um tópico importante em redes complexas é a detecção de comunidades. Embora a detecção de comunidades tenha revelado bons resultados na análise de agrupamento de dados com grupos de diversos formatos, existem ainda algumas dificuldades na representação em rede de um conjunto de dados. Outro tópico recente é a caracterização de simplicidade em redes complexas. Existem poucos trabalhos nessa área, no entanto, o tema tem muita relevância, pois permite analisar a simplicidade da estrutura de conexões de uma região de vértices, ou de toda a rede. Além disso, mediante a análise de simplicidade de redes dinâmicas no tempo, é possível conhecer como vem se comportando a evolução da rede em termos de simplicidade. Considerando a rede como um sistema dinâmico de agentes acoplados, foi proposto neste trabalho uma medida de distância baseada no tempo de consenso na presença de um líder em uma rede acoplada. Utilizando essa medida de distância, foi proposto um método de detecção de comunidades para análise de agrupamento de dados, e um método de análise de simplicidade em redes complexas. Além disso, foi proposto uma técnica de construção de redes esparsas para agrupamento de dados. Os métodos têm sido testados com dados artificiais e reais, obtendo resultados promissores / Networks are powerful representations for many complex systems, where nodes represent elements of the system and edges represent connections between them. Complex networks can be defined as graphs with no trivial distribution of connections. An important topic in complex networks is the community detection. Although the community detection have reported good results in the data clustering analysis with groups of different formats, there are still some dificulties in the representation of a data set as a network. Another recent topic is the characterization of simplicity in complex networks. There are few studies reported in this area, however, the topic has much relevance, since it allows analyzing the simplicity of the structure of connections between nodes of a region or connections of the entire network. Moreover, by analyzing simplicity of dynamic networks in time, it is possible to know the behavior in the network evolution in terms of simplicity. Considering the network as a coupled dynamic system of agents, we proposed a distance measure based on the consensus time in the presence of a leader in a coupled network. Using this distance measure, we proposed a method for detecting communities to analyze data clustering, and a method for simplicity analysis in complex networks. Furthermore, we propose a technique to build sparse networks for data clustering. The methods have been tested with artificial and real data, obtaining promising results

A pesquisa na area de redes complexas tem evoluido bastante, e e nesta linha que o presente trabalho visa aportar, dando enfase especial no processo epidemico sobre redes. Desse modo, foi feito uma analise geral das redes complexas em conjunto com suas propriedades. Apos isso, desenvolveu-se o processo de contagio da epidemia do tipo suscetivel-infectado sobre uma rede aleatoria uniforme e sobre uma rede aleatoria com ligacoes preferenciais. Ambas abordagens foram desenvolvidas usando equacoes mestras para finalmente fazer sua analise com metodos analiticos e computacionais. / Research in the area of complex networks has evolved greatly, and over this line that this present work aims to contribute, with particular emphasis on the epidemic process over networks. Along these lines, a general review about complex networks is made with their main properties. After that, a susceptible-infected contagion process is developed over a uniform random network and a preferential attachment network. Both approaches were developed using master equations to finally analyze them with analytical and computatio- nal methods.

A pesquisa na area de redes complexas tem evoluido bastante, e e nesta linha que o presente trabalho visa aportar, dando enfase especial no processo epidemico sobre redes. Desse modo, foi feito uma analise geral das redes complexas em conjunto com suas propriedades. Apos isso, desenvolveu-se o processo de contagio da epidemia do tipo suscetivel-infectado sobre uma rede aleatoria uniforme e sobre uma rede aleatoria com ligacoes preferenciais. Ambas abordagens foram desenvolvidas usando equacoes mestras para finalmente fazer sua analise com metodos analiticos e computacionais. / Research in the area of complex networks has evolved greatly, and over this line that this present work aims to contribute, with particular emphasis on the epidemic process over networks. Along these lines, a general review about complex networks is made with their main properties. After that, a susceptible-infected contagion process is developed over a uniform random network and a preferential attachment network. Both approaches were developed using master equations to finally analyze them with analytical and computatio- nal methods.

Tese (Doutorado em Engenharia Elétrica) - Centro Universitário FEI, São Bernardo do Campo, 2016

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Civil e Ambiental, 2016. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2016-05-20T15:55:20Z No. of bitstreams: 1 2016_RafaelRodriguesDiasPereira.pdf: 2369559 bytes, checksum: e5ba8a540d0b74ed5ca4bab7690a798e (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-05-30T18:38:09Z (GMT) No. of bitstreams: 1 2016_RafaelRodriguesDiasPereira.pdf: 2369559 bytes, checksum: e5ba8a540d0b74ed5ca4bab7690a798e (MD5) / Made available in DSpace on 2016-05-30T18:38:09Z (GMT). No. of bitstreams: 1 2016_RafaelRodriguesDiasPereira.pdf: 2369559 bytes, checksum: e5ba8a540d0b74ed5ca4bab7690a798e (MD5) / As redes de transporte aéreo são consideradas uma das infraestruturas críticas que sustentam a dinâmica da sociedade econômica atual, ao lado de diversos outros sistemas essenciais que operam sob uma estrutura de rede, tais como, sistemas de transmissão de energia elétrica, sistemas de abastecimento de água ou de telecomunicações. Nesse contexto, existe a necessidade de melhorar a compreensão da vulnerabilidade dessas redes quando sujeitas a eventos de interrupção. Uma condição climática severa, um acidente na pista de pouso, uma sabotagem do terminal de passageiros ou de uma aeronave em solo, são exemplos da variedade de eventos que podem causar interrupção ou redução da capacidade operacional de um aeroporto e, portanto, podem impactar negativamente uma rede de transporte aéreo. O cenário de interrupção de uma instalação ou serviço componente de um sistema que opera em rede é um ponto de partida para a análise da vulnerabilidade do sistema. Em sistemas de transportes, essa análise pode ser entendida como uma avaliação do comportamento da rede de transporte quando esta sofre interferências de eventos inesperados ou não desejáveis nos elementos que a compõem. Considerando o conjunto de preocupações decorrentes dessa perspectiva, a pesquisa investiga as formas de avaliar a vulnerabilidade de uma rede de transporte aéreo e propõe um método para essa avaliação em cenários de interrupção operacional de aeroportos. A teoria das redes complexas proporciona um ferramental teórico e técnico que tem se mostrado adequado pela capacidade de integração de diferentes abordagens metodológicas. O método foi implementado na linguagem e ambiente R e aplicado para análise da rede de transporte aéreo brasileira, onde foi possível: (1) descrever as características topológicas e funcionais da rede; (2) avaliar o seu grau de vulnerabilidade (3) identificar a importância e criticidade dos aeroportos que compõe a rede e (4) avaliar a validade do método proposto. Por fim, destaca-se o potencial do método em contribuir para o aprimoramento do processo de gerenciamento de risco das organizações públicas e privadas do setor de aviação. _______________________________________________________________________________________________ ABSTRACT / Air transport networks are considered one of the critical infrastructure that support the dynamics of the current economic society, along with many other essential systems that operate under a network structure, such as electric power transmission systems, water supply systems or telecommunications systems. In this context, there is a need to enhance the understanding of the vulnerability of these networks when subjected to events of interruption. A severe weather condition, an accident on the runway, and a sabotage of the terminal or of the aircraft on the ground are examples of the variety of events that may cause interruption or reduction of the operational capacity of an airport and therefore may negatively impact an air transport network. The scenario of interruption of a facility or service that is part of a networked system is a starting point for the analysis of the system's vulnerability. In transport systems, this analysis may be seen as an assessment of the behavior of the transport network when it is interfered by unexpected or undesirable events on the elements that compose it. Considering the set of concerns arising from this perspective, the research investigates ways to evaluate the vulnerability of an air transport network and proposes a method for this assessment in scenarios of operational disruption of airports. The theory of complex networks provides a theoretical and technical tool that has been shown to be suitable because of the integration capacity of different methodological approaches. The method was implemented on the R language and environment and applied in the analisys of the Brazilian air transport network, where it was possible: (1) to describe the topological and functional characteristics of the network; (2) to assess the network’s level of vulnerability (3) to identify the importance and criticality of the airports that make up the network and (4) to evaluate the validity of the proposed method. Finally, it is important to highlight the potencial of the method in contributing to the improvement of the risk management process in public and private aviation organizations.

Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2017-08-18T16:10:57Z No. of bitstreams: 1 texto completo.pdf: 1352100 bytes, checksum: ea0a2db33035ef9c6c2173991ca91d78 (MD5) / Made available in DSpace on 2017-08-18T16:10:57Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1352100 bytes, checksum: ea0a2db33035ef9c6c2173991ca91d78 (MD5) Previous issue date: 2016-09-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Transições de fase para estados absorventes (TFEAs) são um tópico de fronteira na física estatís- tica. A comunidade científica tem dedicado esforços ao estudo de processos que exibem TFEAs em redes complexas, já que tais redes tem sido alvo de crescente interesse por descreverem uma grande variedade de sistemas com relevância tanto tecnológica quanto intelectual. Levando em conta a natureza dinâmica e o enorme tamanho das redes reais, a abordagem da mecânica esta- tística mostra-se conveniente devido a sua ligação com a teoria de grafos e a caracterização de fenômenos macroscópicos emergentes em termos da dinâmica de elementos básicos que com- poem o sistema. Em um dos tópicos apresentados nesta tese, utilizamos o tempo de vida da atividade nos vértices mais conectados (hubs) de uma rede sem escala para investigar a relação entre mecanismos de ativação de fases epidêmicas em redes complexas, baseando-se princi- palmente no modelo infectado-suscetível-recuperado-suscetível (SIRS) para redes sem escala sintéticas e para redes reais. Foi desenvolvido um critério geral para identificar a natureza do limiar epidêmico em redes, seja ele devido a um processo de ativação e reativação mútua dos hubs, levando a um limiar epidêmico nulo no limite termodinâmico, ou devido a uma ativação coletiva que gera um estado endêmico no qual a atividade encontra-se espalhada por toda a ex- tensão da rede, correspondendo a uma transição de fase padrão ocorrendo para um valor finito da taxa de infecção. Também comparamos diferentes métodos quase-estacionários de simula- ção para contornar o(s) estado(s) absorvente(s) do sistema (conservando o limite termodinâmico da dinâmica original para os processos analisados), a saber, o método quase-estacionário (QE) padrão, o método de condição de fronteira refletora, em que a dinâmica retorna à configuração pré-absorvente e o método de reativação de hubs, no qual os nós mais conectados são reativados após uma visita a um estado absorvente. Este trabalho foi exemplificado por meio dos já bem conhecidos processo de contato (PC) e modelo suscetível-infectado-suscetível (SIS). Todas as técnicas investigadas fornecem o mesmo limiar epidêmico para ambos os modelos. Mostramos que, para o PC, os métodos são equivalentes, enquanto para o modelo SIS apenas o método QE padrão e de reativação de hubs são capazes de capturar fases endêmicas localizadas. Por fim, verificamos a equivalência entre o método de condição de fronteira refletora e um campo externo fraco que gera atividade espontânea na rede. / Phase transitions to absorbing states (APTs) are a topic at the frontier of statistical physics. The scientific community has dedicated efforts to the study of processes exhibiting APTs in complex networks, since such networks have been subject of increasing interest to describe a wide variety of systems with both technological and intelectual relevances. Considering the dynamic nature and huge size of real networks, the statistical mechanics approach has proved to be conveni- ent due to its connection with graph theory and the characterization of emerging macroscopic phenomena in terms of the dynamics of basic elements constituting the system. In one of the topics presented on this thesis, we used the lifespan of the activity at the most connected ver- tices (hubs) of a scale-free network to investigate the relation between activation mechanisms of epidemic phases in complex networks, based mainly on the susceptible-infected-recovered- susceptible (SIRS) model in synthetic and real scale-free networks. We developed a general criterion to identify the nature of the epidemic threshold on networks, due to a collective activa- tion and reactivation process of the hubs, leading to a vanishing threshold at the thermodynamic limit, or due to a collective activation which generates an endemic state where activity spre- ads out through the whole network, corresponding to a standard phase transition taking place at a finite value of the infection rate. We also compared different quasi-stationary simulation methods to circumvent the absorbing state(s) of the system (preserving the thermodynamic limit of the original dynamics for the analyzed processes), namely, the standard quasi-stationary (QS) method, the reflecting boundary condition, in which the dynamics returns to the pre-absorbing configuration and the hub reactivation method, in which the most connected vertices are reacti- vated after a visit to an absorbing state. These methods were applied to the well-known contact process (CP) and susceptible-infected-susceptible (SIS) models. All the investigated techniques provide the same epidemic threshold for both models. We showed that, for the CP, all methods are equivalent, while for the SIS model only the standard QS and hub reactivation methods are able to capture localized endemic phases. Finally, we verified the equivalence between the reflecting boundary condition method and a weak external field which generates spontaneous activity in the network.

Made available in DSpace on 2014-12-17T15:14:58Z (GMT). No. of bitstreams: 1 ClaudiaPTC_TESE.pdf: 1287750 bytes, checksum: ae4c352716f477b85814812c8c372a8a (MD5) Previous issue date: 2013-05-23 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / In this thesis we deal with a class of composed networks that are formed by two tree networks, TP and TA, whose end points touches each other through a bipartite network BPA. We explore this network using a functional approach. We are interested in what extend the topology, or the structure, of TX (X = A or P) determines the links of BPA. This composed structure is an useful model in evolutionary biology, where TP and TA are the phylogenetic trees of plants and animals that interact in an ecological community. We use in this thesis two cases of mutualist interactions: frugivory and pollinator networks. We analyse how the phylogeny of TX determines or is correlated with BPA using a Monte Carlo approach. We use the phylogenetic distance among elements that interact with a given species to construct an index κ that quantifies the influence of TX over BPA. The algorithm is based in the assumption that interaction matrices that follows a phylogeny of TX have a total phylogenetic distance smaller than the average distance of an ensemble of Monte Carlo realizations generated by an adequate shuffling data. We find that the phylogeny of animals species has an effect on the ecological matrix that is more marked than plant phylogeny / Nesta tese tratamos com uma classe de redes compostas que s?o formadas por duas redes tipo ?rvore, TP e TA, cujos pontos extremos se tocam em uma rede bipartida BPA. Esta rede composta ? analisada usando uma abordagem funcional. Estamos interessados em estudar o quanto a topologia, ou a estrutura, de TX (X = A ou P) determina as conex?es BPA. Esta estrutura composta de rede ? ?til em biologia evolutiva onde TP e TA s?o ?rvores filogen?ticas de plantas e animais que interagem em uma comunidade ecol?gica. Estudamos dois casos de redes ecol?gicas de intera??o mutual?stica: redes de Intera??es do tipo frugivoria e intera??es do tipo poliniza??o. Analisamos o quanto a filogenia de TX determina, ou est? correlacionada, com BPA usando uma abordagem do tipo Monte Carlo. Para tanto estimamos a dist?ncia filogen?tica entre elementos que interagem com uma dada esp?cie para construir um ?ndice κ que quantifica a influ?ncia de TX sobre BPA. O algoritmo ? baseado na premissa de que matrizes de intera??o que seguem a filogenia de TX v?o apresentar uma dist?ncia filogen?tica menor do que a m?dia das dist?ncias obtidas por Monte Carlo constru?do via um adequado embaralhamento de dados. Encontramos que a filogenia dos animais tem um efeito mais marcante sobre a matriz de intera??o do que a filogenia das plantas

Por muitos anos, a ciência tratou todas as redes como se seus relacionamentos fossem estabelecidos de forma randômica, ou seja, a maioria dos nós teriam aproximadamente o mesmo número de relacionamentos. Porém, o mapeamento de uma variedade de sistemas revelou que a maioria dos nós tinha poucos relacionamentos, enquanto alguns nós têm uma grande quantidade de conexões. Processos microscópicos dinâmicos e estatísticos são duas facetas de sistemas complexos, que estão intimamente ligadas, e a compreensão da sua interdependência é importante tanto para a previsão quanto planejamento estratégico. Os exemplos mais proeminentes incluem o ruído do tráfego em redes de comunicação, sinais ruidosos em sistemas desordenados e auto-organizados, e as séries temporais das flutuações dos preços nos mercados financeiros. Neste trabalho foram analisadas não apenas características globais do tráfego de pacotes em redes complexas, como a presença ou não de congestionamento na rede como um todo, mas também as características locais (isto é, de roteadores específicos) do tráfego no ponto de transição entre a fase livre e a fase de congestionamento. Os resultados mostram, entre outros, que a transição de um estado livre de congestionamento para o estado congestionado de um nó ocorre quando o coeficiente de detrended fluctuation analysis da série temporal do número de pacotes na fila de espera do nó é próximo do valor crítico de 1. / For many years the science networks all treated as if their relationships were set at random, that is, most of us have approximately the same number of relationships. However, the mapping in a variety of systems revealed that most of us had a few relationships, while some of us have a lot of connections. Dynamic and statistical microscopic processes are two facets of complex systems, which are closely linked, and understanding of their interdependence is important both for predicting as strategic planning. Prominent examples include traffic noise in communication networks, noisy signals in disordered systems and self-organized, and the time series of price fluctuations in financial markets. This work analyzed not only the overall characteristics of package traffic in complex networks and the presence or absence of congestion on the network as a whole, but also the local characteristics (ie, specific routers) of the traffic at the point of transition from the free phase, and congested phase. The results show, among others, that the transition from free to congested traffic in a node happens when the detrended fluctuation analysis coefficient of the time series of the number of waiting packets is close to the critical value of 1.

A extinção de grandes mamíferos terrestres no final do Pleistoceno (entre 50 e 11 mil anos atrás) é um dos temas mais debatidos em ecologia. A maioria dos estudos sobre as causas das extinções do Pleistoceno tem como foco o papel de fatores externos como mudanças climáticas e a chegada do homem. Entretanto, a forma como uma comunidade ecológica responde a perturbações depende de suas propriedades, como o número e composição de espécies e a forma como essas espécies interagem. O objetivo final dos estudos reunidos nessa tese foi entender como estavam organizadas as interações ecológicas entre os mamíferos do Pleistoceno e o possível papel dessas interações no episódio de extinção da megafauna. Em primeiro lugar adaptei modelos de teias tróficas para reproduzir redes formadas por diferentes tipos de interações entre consumidores e recursos. Em seguida, utilizei esses modelos para reconstruir redes de interação entre predadores e presas da megafauna do Pleistoceno e examinei as propriedades estruturais e dinâmicas dessas redes. Por fim, investiguei uma das possíveis consequências da extinção da megafauna: a perda de serviços de dispersão de sementes. Os resultados aqui apresentados mostram que (i) diferentes tipos de redes de interação entre consumidores e recursos compartilham características estruturais e podem ser reproduzidas por modelos de teias tróficas; (ii) redes de interação entre grandes mamíferos do Pleistoceno estavam, provavelmente, estruturadas de forma similar aos sistemas atuais na África. Entretanto, as comunidades do Pleistoceno seriam especialmente vulneráveis às mudanças estruturais e na dinâmica causadas pela chegada de um predador como o homem; (iii) entre as consequências da extinção do Pleistoceno está a reorganização de outros tipos de rede de interação como as redes de dispersão de sementes. Em conjunto os resultados apresentados aqui enfatizam a importância de considerarmos o possível papel das interações ecológicas em modular os efeitos de perturbações ao estudarmos eventos de extinção / The extinction of large terrestrial mammals during the late Pleistocene (between 50 and 11 kyrs ago) is one of the most debated topics in ecology. Most studies on the causes of Pleistocene extinctions focus on the role of external factors such as climate changes and the arrival of humans. Nevertheless, the way an ecological community responds to perturbations depends on its properties, such as its number of species, species composition and the way these species interact. This thesis encloses studies with the final objective of understanding how ecological interactions between Pleistocene large mammals were organized and the potential role of such interactions in the Pleistocene extinction episode. First, I adapted food-web models to reproduce networks depicting different types of ecological interactions between consumers and resources. Then, I used these models to reconstruct predator-prey interaction networks between Pleistocene large mammals and examined the structural and dynamic properties of these systems. Finally, as an overview of the ecological impacts of Pleistocene extinctions, I discuss one of the possible consequences of the demise of Pleistocene large mammals: the loss of seed-dispersal services. The results presented here show that (i) different types of interaction networks between consumers and resources share structural properties and can be reproduced by food-web models; (ii) interactions between Pleistocene large mammals were most likely structured in a similar way to modern large-mammals assemblages in Africa, but the former were especially vulnerable to the changes in structure and dynamics caused by a newly arriving predator such as humans; (iii) among the consequences of Pleistocene extinctions is the reconfiguration of other types of interaction networks such as seed-dispersal networks. Taken together these findings emphasize how important it is to consider the role of ecological interactions in modulating the effects of perturbations when studying extinctions events