O estudo de séries temporais para a geração de conhecimento é uma área que vem crescendo em importância e complexidade ao longo da última década, à medida que a quantidade de dados armazenados cresce exponencialmente. Considerando este cenário, novas técnicas de mineração de dados têm sido constantemente desenvolvidas para lidar com esta situação. Neste trabalho é proposto o estudo de séries temporais baseado em suas características topológicas, observadas em uma rede complexa gerada com os dados da série temporal. Especificamente, o objetivo do modelo proposto é criar um algoritmo de detecção de tendências para séries temporais estocásticas baseado em detecção de comunidades e caminhadas nesta mesma rede. O modelo proposto apresenta algumas vantagens em relação à métodos tradicionais, como o número adaptativo de classes, com força mensurável, e uma melhor absorção de ruídos. Resultados experimentais em bases artificiais e reais mostram que o método proposto é capaz de classificar as séries temporais em padrões locais e globais, melhorando a previsibilidade das séries ao se utilizar métodos de aprendizado de máquina para a previsão das classes / Extracting knowledge from time series analysis has been growing in importance and complexity over the last decade as the amount of stored data has increased exponentially. Considering this scenario, new data mining techniques have continuously developed to deal with such a situation. In this work, we propose to study time series based on its topological characteristics, observed on a complex network generated from the time series data. Specifically, the aim of the proposed model is to create a trend detection algorithm for stochastic time series based on community detection and network metrics. The proposed model presents some advantages over traditional time series analysis, such as adaptive number of classes with measurable strength and better noise absorption. Experimental results on artificial and real datasets shows that the proposed method is able to classify the time series into local and global patterns, improving the predictability of the series when using machine-learning methods

Made available in DSpace on 2017-07-21T19:26:10Z (GMT). No. of bitstreams: 1 Pedro Jeferson Miranda.pdf: 3220140 bytes, checksum: a557a7dc630657c2bc53d73eb4fd7f48 (MD5) Previous issue date: 2014-09-03 / Fundação Araucária de Apoio ao Desenvolvimento Científico e Tecnológico do Paraná / The emergence is a phenomenon that gives sense to the qualitative unity of any substance, consisting the reflex in the ontological act of perception. It is the conceptual key that justifies the use of complex network models to describe systems, which also are complex in nature. Given this key concept, it was desired to apply it on real objects in order to create new analysis methodologies. For this, graph’s theory and random walk’s theory were used as fundamentals for two study cases. One of them consists on an analysis of the mythological social network of Odyssey of Homer. It was found that this network displays structural characteristic of real social network mixed with fictional aspects associated to mythological characters. Another study was the oral tolerance phenomenon modeled as a complex network associated with stochastic dynamics. We applied the random walk as a way to understand the relative importance of each immunological component. Finally, it becomes evidenced that the key concept of emergence allows new forms of analysis using complex network theory as a model which comprises the complexity inherent on the conception of real systems. / A emergência é fenômeno que dá unidade qualitativa a qualquer substância, constituindo o reflexo no ato ontológico da percepção. É a chave conceitual que justifica o uso do modelo em redes complexas para descrever sistemas, que também são complexos naturalmente. Dada essa chave conceitual, buscou-se utilizá-la na geração de novas análises. Para tanto é empregado a teoria de grafos e a caminhada aleatória em dois estudo de caso. Um deles constitui a análise de uma rede mitológica referente à Odisseia de Homero. Foi verificado que a rede mitológica apresenta padrões de redes sociais reais quando excetuados da rede as personagens mitológicas. Em segundo lugar, foi realizado um estudo da tolerância oral como um fenômeno de rede complexa, foi utilizada a caminhada aleatória como modelo estocástico de difusão de estímulos numa rede complexa. Com isso, foi possível conhecer a importância relativa de cada componente imunológica. Por fim, fica evidenciado que o conceito chave de emergência permite a concepção de novas formas de análise, fundamentalmente no uso de redes complexas como modelos que albergam a complexidade inerente na concepção de sistemas reais.

Este trabalho foca no estudo de duas redes complexas. A primeira é um modelo de Ising com campo aleatório. Este modelo segue uma distribuição de campo gaussiana e bimodal. Uma técnica de conectividade finita foi utilizada para resolvê-lo. Assim como um método de Monte Carlo foi aplicado para verificar os resultados. Há uma indicação em nossos resultados que para a distribuição gaussiana a transição de fase é sempre de segunda ordem. Para as distribuições bimodais há um ponto tricrítico, dependente do valor da conectividade . Abaixo de um certo mínimo de , só existe transição de segunda ordem. A segunda é uma rede neural atratora métrica. Mais precisamente, estudamos a capacidade deste modelo para armazenar os padrões estruturados. Em particular, os padrões escolhidos foram retirados de impressões digitais, que apresentam algumas características locais. Os resultados mostram que quanto menor a atividade de padrões de impressões digitais, maior a relação de carga e a qualidade de recuperação. Uma teoria, também foi desenvolvido como uma função de cinco parâmetros: a relação de carga, a conectividade, o grau de densidade da rede, a relação de aleatoriedade e a correlação do padrão espacial. / This work focus on the study of two complex networks. The first one is a random field Ising model. This model follows a gaussian and bimodal distribution, for the random field. A finite connectivity technique was utilized to solve it. As well as a Monte Carlo method was applied to verify our results. There is an indication in our results that for a gaussian distribution the phase transition is always second-order. For the bimodal distribution there is a tricritical point, tha depends on the value of the connectivity . Below a certain minimum , there is only a second-order transition. The second one is a metric attractor neural network. More precisely we study the ability of this model to learn structured patterns. In particular, the chosen patterns were taken from fingerprints, which present some local features. Our results show that the higher the load ratio and retrieval quality are the lower is the fingerprint patterns activity. A theoretical framework was also developed as a function of five parameters: the load ratio, the connectivity, the density degree of the network, the randomness ratio and the spatial pattern correlation.

Tendo reformulado a mecânica surgida da termoestatística das radiações eletromagnéticas, a física quântica abriu o caminho nas baixas energias para a complexidade dos materiais e da vida, e nas altas energias para as partículas elementares e conexões cosmológicas. Entre as demais ciências, ela fundamenta a química fina, a biologia molecular e inúmeras aplicações práticas. No cotidiano tecnológico, através dos semicondutores e lasers da microeletrônica, a quântica é a alma conceitual das telecomunicações e das redes informáticas, instrumentando todas as atividades humanas, das relações pessoais às práticas médicas, e condicionando a emergência de uma sociedade em rede. Em associação com as tecnologias que promove, o domínio quântico tem sido central na investigação das redes complexas que transforma a compreensão de processos naturais, tecnológicos e sociais. Das redes neurais às sociais, qualquer campo de atividade e de conhecimento está sendo modificado ou desequilibrado pela percepção de seu caráter complexo. Impactada pelo novo ambiente, a educação já se desenvolve com recursos em rede amplamente difundidos e revê a conceituação do aprender como algo complexo e em rede em lugar da velha sequência linear de conteúdos. Sendo convergência e fonte de várias redes, a quântica pode cumprir importante papel na trama de redes de significados no processo de ensino e aprendizagem. Formar os professores com e para tais práticas pode dar mais significado a esse domínio científico já presente em nossa escola básica, mas cujo sentido real frequentemente escapa para quem aprende tanto quanto para quem ensina. Esta tese busca apresentar uma visão em rede do conjunto das redes entretecidas com a física quântica, tendo como contexto prático a formação inicial de professores. / Quantum Physics, a reconceptualization of Mechanics that emerged from the thermo statistics of electromagnetic radiation, has paved the way to the complexity of materials and life, at low energies, and to elementary particles and its cosmological connections, at high energies. Among the other sciences, quantum physics is the foundation to the new fine chemistry, as well as to the molecular biology and to their numerous practical applications. In everyday technology, through semiconductors and lasers of the microelectronic, quantum physics is the conceptual soul of telecommunications and informatics networks, giving tools to all sort of activities, from social relationships to the medical practices, and conditioning the emergency of a network society. In relation with technologies, the quantum domain has been central to the research of complex networks that changes the understanding of natural, technological and social processes. From neural to social networks, every field of activity and knowledge is nowadays modified or unbalanced by the perception of its complex character. Impacted by this new environment, education already develops with highly available network resources and reevaluates the concept of learning, as something complex instead of the old linear sequence of subjects. As convergence and source of many networks, quantum physics can play important role in the network of meanings of teaching and learning process. The training of teachers with and for these practices can give broader meaning to this scientific field already present in our basic school, but whose real meaning frequently is missed both by who learns as well as by who teaches. This tesis wants to presents a network vision of the ensemble of the networks weaved togheter with quantum physics, in the practical context of training future teachers.

A inferência de redes gênicas (GN) a partir de dados de expressão gênica temporal é um problema crucial e desafiador em Biologia Sistêmica. Os conjuntos de dados de expressão geralmente consistem em dezenas de amostras temporais e as redes consistem em milhares de genes, tornando inúmeros métodos de inferência inviáveis na prática. Para melhorar a escalabilidade dos métodos de inferência de GNs, esta tese propõe um arcabouço chamado GeNICE, baseado no modelo de redes gênicas probabilísticas. A principal novidade é a introdução de um procedimento de agrupamento de genes, com perfis de expressão relacionados, para fornecer uma solução aproximada com complexidade computacional reduzida. Os agrupamentos definidos são usados para reduzir a dimensionalidade permitindo uma busca exaustiva mais eficiente pelos melhores subconjuntos de genes preditores para cada gene alvo de acordo com funções critério multivariadas. GeNICE reduz consideravelmente o espaço de busca porque os candidatos a preditores ficam restritos a um gene representante por agrupamento. No final, uma análise multivariada é realizada para cada subconjunto preditor definido, visando recuperar subconjuntos mínimos para simplificar a rede gênica inferida. Em experimentos com conjuntos de dados sintéticos, GeNICE obteve uma redução substancial de tempo quando comparado a uma solução anterior sem a etapa de agrupamento, preservando a precisão da predição de expressão gênica mesmo quando o número de agrupamentos é pequeno (cerca de cinquenta) e o número de genes é grande (ordem de milhares). Para um conjunto de dados reais de microarrays de Plasmodium falciparum, a precisão da predição alcançada pelo GeNICE foi de aproximadamente 97% em média. As redes inferidas para os genes alvos da glicólise e do apicoplasto refletem propriedades topológicas de redes complexas do tipo \"mundo pequeno\" e \"livre de escala\", para os quais grande parte das conexões são estabelecidas entre os genes de um mesmo módulo e algumas poucas conexões fazem o papel de estabelecer uma ponte entre os módulos (redes mundo pequeno), e o grau de distribuição das conexões entre os genes segue uma lei de potência, na qual a maioria dos genes têm poucas conexões e poucos genes (hubs) apresentam um elevado número de conexões (redes livres de escala), como esperado. / Gene network (GN) inference from temporal gene expression data is a crucial and challenging problem in Systems Biology. Expression datasets usually consist of dozens of temporal samples, while networks consist of thousands of genes, thus rendering many inference methods unfeasible in practice. To improve the scalability of GN inference methods, this work proposes a framework called GeNICE, based on Probabilistic Gene Networks; the main novelty is the introduction of a clustering procedure to group genes with related expression profiles, to provide an approximate solution with reduced computational complexity. The defined clusters were used to perform an exhaustive search to retrieve the best predictor gene subsets for each target gene, according to multivariate criterion functions. GeNICE greatly reduces the search space because predictor candidates are restricted to one representative gene per cluster. Finally, a multivariate analysis is performed for each defined predictor subset to retrieve minimal subsets and to simplify the network. In experiments with in silico generated datasets, GeNICE achieved substantial computational time reduction when compared to an existing solution without the clustering step, while preserving the gene expression prediction accuracy even when the number of clusters is small (about fifty) relative to the number of genes (order of thousands). For a Plasmodium falciparum microarray dataset, the prediction accuracy achieved by GeNICE was roughly 97% on average. The inferred networks for the apicoplast and glycolytic target genes reflects the topological properties of \"small-world\"and \"scale-free\"complex network models in which a large part of the connections is established between genes of the same functional module (smallworld networks) and the degree distribution of the connections between genes tends to form a power law, in which most genes present few connections and few genes (hubs) present a large number of connections (scale-free networks), as expected.

Esta dissertação apresenta um estudo detalhado do comportamento do modelo de Sznajd, um modelo de interações microscópicas entre sítios empregado com freqüência para representar o processo de formação de opinião em uma comunidade. Neste modelo cada sítio tentará convencer seus vizinhos a assumir o mesmo estado em que está, com uma regra que privilegia a existência de pares de sítios já em um mesmo estado, ou seja, caso um par de vizinhos esteja no mesmo estado, a probabilidade dos outros vizinhos assumirem este estado será maior. Analisamos o papel das condições iniciais do sistema (particularmente do grau dos eleitores iniciais) e tentamos, através de representações gráficas e outros métodos, enteder que caracteríticas determinam o resultado final do processo. Os resultados previstos pelo modelo na rede de Barabási-Albert são também comparados com dados obtidos no TRE para eleições para casas legislativas brasileiras, e generalizamos o método da estimação via máxima verossimilhança para o caso em que a distribuição apresenta efeitos de tamanho finito nos dois extremos. Estudamos também os resultados de duas alterações da dinâmica do modelo, ainda na rede de Barabási-Albert. Na primeira, inserimos inomogeneidades na rede (que podem ser, por exemplo, cabos eleitorais) e vemos como a introdução destes defeitos na rede afetam o resultado final. Na segunda estudamos como a introdução de uma influência externa, não local, (que mimetizaria, por exemplo, a campanha publicitária) afeta a dinâmica, e encontramos uma transição de fase de primeira ordem no comportamento do sistema. As previsões da aproximação de campo médio para o modelo com ruído, por nós desenvolvida, descrevem qualitativamente bem a transição. Por fim, investigamos a influência de alterações na rede em que se dá a dinâmica do modelo, utilizando reticulados, cadeias regulares e a rede de Watts-Strogatz. Comparamos o comportamento do modelo nessas redes com a dinâmica de Glauber a temperatura nula e com o modelo do votante. / This work studies in detail the Szajd model, a dynamical model based on microscopic local interactions between sites, usually employed to simulate rumor spreading and opinion formation in a community.

A time series is a time-ordered dataset. Due to its ubiquity, time series analysis is interesting for many scientific fields. Time series data mining is a research area that is intended to extract information from these time-related data. To achieve it, different models are used to describe series and search for patterns. One approach for modeling temporal data is by using complex networks. In this case, temporal data are mapped to a topological space that allows data exploration using network techniques. In this thesis, we present solutions for time series data mining tasks using complex networks. The primary goal was to evaluate the benefits of using network theory to extract information from temporal data. We focused on three mining tasks. (1) In the clustering task, we represented every time series by a vertex and we connected vertices that represent similar time series. We used community detection algorithms to cluster similar series. Results show that this approach presents better results than traditional clustering results. (2) In the classification task, we mapped every labeled time series in a database to a visibility graph. We performed classification by transforming an unlabeled time series to a visibility graph and comparing it to the labeled graphs using a distance function. The new label is the most frequent label in the k-nearest graphs. (3) In the periodicity detection task, we first transform a time series into a visibility graph. Local maxima in a time series are usually mapped to highly connected vertices that link two communities. We used the community structure to propose a periodicity detection algorithm in time series. This method is robust to noisy data and does not require parameters. With the methods and results presented in this thesis, we conclude that network science is beneficial to time series data mining. Moreover, this approach can provide better results than traditional methods. It is a new form of extracting information from time series and can be easily extended to other tasks. / Séries temporais são conjuntos de dados ordenados no tempo. Devido à ubiquidade desses dados, seu estudo é interessante para muitos campos da ciência. A mineração de dados temporais é uma área de pesquisa que tem como objetivo extrair informações desses dados relacionados no tempo. Para isso, modelos são usados para descrever as séries e buscar por padrões. Uma forma de modelar séries temporais é por meio de redes complexas. Nessa modelagem, um mapeamento é feito do espaço temporal para o espaço topológico, o que permite avaliar dados temporais usando técnicas de redes. Nesta tese, apresentamos soluções para tarefas de mineração de dados de séries temporais usando redes complexas. O objetivo principal foi avaliar os benefícios do uso da teoria de redes para extrair informações de dados temporais. Concentramo-nos em três tarefas de mineração. (1) Na tarefa de agrupamento, cada série temporal é representada por um vértice e as arestas são criadas entre as séries de acordo com sua similaridade. Os algoritmos de detecção de comunidades podem ser usados para agrupar séries semelhantes. Os resultados mostram que esta abordagem apresenta melhores resultados do que os resultados de agrupamento tradicional. (2) Na tarefa de classificação, cada série temporal rotulada em um banco de dados é mapeada para um gráfico de visibilidade. A classificação é realizada transformando uma série temporal não marcada em um gráfico de visibilidade e comparando-a com os gráficos rotulados usando uma função de distância. O novo rótulo é dado pelo rótulo mais frequente nos k grafos mais próximos. (3) Na tarefa de detecção de periodicidade, uma série temporal é primeiramente transformada em um gráfico de visibilidade. Máximos locais em uma série temporal geralmente são mapeados para vértices altamente conectados que ligam duas comunidades. O método proposto utiliza a estrutura de comunidades para realizar a detecção de períodos em séries temporais. Este método é robusto para dados ruidosos e não requer parâmetros. Com os métodos e resultados apresentados nesta tese, concluímos que a teoria da redes complexas é benéfica para a mineração de dados em séries temporais. Além disso, esta abordagem pode proporcionar melhores resultados do que os métodos tradicionais e é uma nova forma de extrair informações de séries temporais que pode ser facilmente estendida para outras tarefas.

The implementation of energy policies oriented to incentive the adoption of efficient lighting technologies in the residential sector requires analytic tools able to describe the market conditions necessary for a successful penetration of the innovations. This article describes, using an agent-based model, the relationship between the micro behaviors of householder\'s adoption of lighting technologies and the aggregated macro patterns of diffusion in the Brazilian residential sector. The model also studies the dynamic between the interaction network parameters and the emerging diffusion characteristics in different economic scenarios for energy and technologic prices / A implementação de políticas públicas orientadas a incentivar a adopção de tecnologias de iluminação mais eficientes no setor residencial precisa de ferramentas analíticas capazes de descrever assertivamente as condições de mercado necessárias para uma penetração exitosa destas inovações. Este documento descreve, utilizando modelagem baseado em agentes, a relação entre os micro comportamentos dos usuários ao adotar as tecnologias de iluminação e as macro tendências agregadas de difusão no setor residencial brasileiro. O modelo também estuda a dinâmica existente entre a relação dos parâmetros das redes de interação e as caraterísticas emergentes no processo de difusão em diferentes cenários econômicos para os custos energéticos e tecnológicos.

O tributo é cobrado dos cidadãos porque ele é o custo do contrato social, um acordo entre pessoas para uma vida em sociedade. Diretamente, há um retorno para a sociedade na forma de serviços públicos; indiretamente, é um instrumento do governo para intervir na economia, como na condução de política fiscal e na redução das desigualdades sociais. Um contribuinte está obrigado a pagá-lo porque essa obrigação decorre de uma regra formal (lei) determinada pelas instituições públicas; e estas são criadas para estruturar as interações humanas, por meio de incentivos. Pretendemos apresentar uma alternativa na análise da relação cidadão-governo na arrecadação tributária e no custo relacionado ao combate à sonegação (por meio da fiscalização de tributos), tendo como objeto de estudo a obediência tributária no âmbito da escolha do contribuinte. Propõe-se uma modelagem baseada em agentes para a análise do comportamento do contribuinte quanto à sonegação, apresentando um modelo de evasão fiscal em redes complexas aleatórias. Nossa principal contribuição é incluir a evolução da percepção do contribuinte sobre as ações de fiscalização do governo em um modelo com abordagem em complexidade. A partir da convergência de fatores individuais (risco aceitável), sociais (interação social) e ambientais (dinâmica com o governo) na adoção de comportamento de sonegação pelo contribuinte, serão comparadas a evolução da evasão fiscal (quantidade de declarações de imposto recebidas) e a da fiscalização do governo (número aproximado de contribuintes fiscalizados) a fim de compreender a dinâmica entre contribuinte e governo. / Taxes are charged to citizens because they are the cost of the social contract, that is an agreement between people to a life in society. Directly, they convert to society into public goods and services; indirectly, are a means of the government to intervene in the economy, for example, the reduction of social inequalities in the regulation of domestic and foreign trade etc. A taxpayer is required to pay a tax because of a formal rule (law) determined by the public institutions. Institutions are created to structure human interactions through incentives. Our intention is to present an alternative analysis of the state-citizen relations in tax revenue and cost related to tax avoidance and tax audit. The object of study is tax compliance under taxpayer behavior. We present an agent-based simulation for analyzing the evasion behavior of the taxpayer, a model of tax evasion in random complex networks. Our main contribution is to include the evolution of the taxpayer perceptions on the government actions oversight in a model with the complexity approach. From the convergence of individual aspects (agents decision under acceptable risk), social influences (social interaction) and environmental factors (dynamic with the government) to tax evasion behavior, is analized the evolution of tax compliance (by tax declaration) and tax audit in order to understand the dynamic behavior between taxpayer and government.

A complexidade é uma característica de grande importância em processos de reconhecimento de padrões, especialmente naqueles que envolvem imagens biológicas. Este trabalho tem como objetivo estudar métodos que realizam a análise de imagens por meio da análise de sua complexidade. Os métodos a serem estudados foram selecionados com base na similaridade de seus algoritmos e metodologia: dimensão fractal, Caminhada Determinística do Turista e Redes Complexas. Estes métodos permitem realizar a análise e segmentação de formas ou texturas contidas em uma imagem com base na sua variação de complexidade. Dos três métodos considerados, dois deles fazem parte do estado da arte em análise de complexidade, enquanto que a dimensão fractal já é aplicada a mais tempo na análise de formas e texturas. Os trabalhos aqui desenvolvidos visam comparar e analisar os métodos selecionados por meio de experimentos com imagens de forma e texturas, sendo utilizadas texturas naturais e de Brodatz, freqüentemente utilizadas na literatura como benchmark para texturas. Com base no conhecimento adquirido, novas técnicas voltadas para a análise e segmentação de formas e texturas foram desenvolvidas, assim como foram analisadas as deficiências e propostas melhorias às técnicas estudadas. Além disso, diversos experimentos com estas metodologias foram realizados em aplicações de Bioinformática / Complexity is a feature of great importance in pattern recognition processes, especially those involving biological images. This work aims to study methods that perform image analysis by the analysis of its complexity. The methods to be studied were selected based on similarity of their algorithms and methodology: fractal dimension, Deterministic Tourist Walk and Complex Networks. These methods enable us to perform the analysis and segmentation of shapes and textures contained in an image based on the variation of its complexity. Of the three methods considered, two of them are part of the state of the art in complexity analysis, while the fractal dimension is already applied in shapes and textures analysis. The work developed here aims to compare and analyze the selected methods through experiments with shape and texture images, utilizing for this natural and Brodatz textures samples, often used in literature as benchmark for textures analysis. Based on the knowledge acquired, new techniques for analysis and segmentation of shapes and textures were developed, as also were analyzed the deficiencies and proposed improvements to the techniques studied. Moreover, several experiments with these methods were performed in bioinformatics applications