In contrast to established approaches that analyze networks based on their structural properties, networks can also be studied by investigating the patterns that are evolved by a discrete dynamical system built upon them, such as cellular automata (CAs). Combined with networks these tools can be used to map the relationship between the network architecture and its impact on the patterns evolved by the governing spatially discrete dynamical system. This thesis focuses on the investigation of discrete spatially explicit models (SEMs), among which are CAs, for network analysis and characterization. The relationship between network architecture and its dynamic aspects concerning pattern formation is studied. Additionally, this work aims at the development of evolutionary methods that can be employed for extracting features from such patterns and then be used as network descriptors. In order to achieve this goal, methods that integrate the network structure with the SEMs were proposed, implemented and analyzed. The proposed family of network automata is characterized by birth-survival dynamics that results in different categories of spatio-temporal patterns. Such patterns were quantitatively assessed and used to characterize different network topologies and perform classification tasks in the context of pattern recognition. Inspired by the classic Life-like CA, the proposed Life-like Network Automata (LLNA) illustrate how such tasks can be performed in real-world applications. In addition, the rock-paper-scissors (RPS) model, normally implemented on square lattices, was investigated by defining it on networks. The obtained results confirm the potential of the proposed quantitative analysis of the spatio-temporal patterns for network classification. This quantitative analysis was performed for a set of different pattern recognition tasks and for the majority of them, the classification performance improved. In addition, the reliability of LLNA as a general tool for pattern recognition applications was demonstrated in a diverse scope of classification tasks. The applicability of structural network descriptors was also highlighted in the context of shape characterization in computer vision. Through the proposed approach, the link between these network descriptors and the shape properties, such as angle and curvature, was illustrated. Moreover, when chosen adequately, the network descriptors led to a better classification performance for different shape recognition tasks. Regarding the RPS model, we demonstrated that the presence of long-range correlations in some networks directly influence the RPS dynamics. Finally, it was shown how a commuter network can be used to predict influenza outbreaks. All the proposed methods use different aspects of network analysis and contribute to the study of CAs and other SEMs on irregular tessellations, in contrast to the commonly used regular topologies. In addition, new insights were obtained concerning pattern recognition in networks through the use of spatio-temporal patterns as network descriptors. / Em contraste às abordagens clássicas que analisam redes com base em suas propriedades estruturais, as redes também podem ser estudadas investigando-se os padrões desenvolvidos por um sistema dinâmico discreto construído sobre essas redes, como os autômatos celulares (CAs). Combinadas às redes, essas ferramentas podem ser usadas para se mapear a relação entre a arquitetura da rede e seu impacto nos padrões obtidos pelo sistema dinâmico subjacente. Esta tese está focada na investigação de modelos discretos espacialmente explícitos (SEMs), entre os quais os CAs, para análise e caracterização de redes. A relação entre a arquitetura da rede e seu aspecto dinâmico em relação à formação de padrões é investigada. Além disso, este trabalho visa o desenvolvimento de métodos evolutivos que podem ser usados para extrair características de tais padrões para, então, serem usados como descritores de redes. Para atingir este objetivo, métodos que integram a estrutura da rede com os SEMs foram propostos, implementados e analisados. A família de redes-autômatos proposta é caracterizada por uma dinâmica de nascimento-sobrevivência que resulta em diferentes categorias de padrões espaço-temporais. Tais padrões foram avaliados quantitativamente e utilizados para caracterizar diferentes topologias de redes e realizar tarefas de classificação no contexto do reconhecimento de padrões. Inspirados pelo clássico Life-Like CA, a rede-autômato proposta, Life-like (LLNA), ilustra como tais tarefas podem ser realizadas em aplicações mais realistas. Além disso, o modelo de rock-paper-scissors (RPS), normalmente implementado em reticulados quadrados, foi investigado usando-se redes como tesselações. Os resultados obtidos confirmam o potencial da análise quantitativa proposta dos padrões espaço-temporais para classificação de redes. Essa análise quantitativa foi realizada para um conjunto de tarefas de reconhecimento de padrões, e, para a maioria dessas tarefas, o desempenho da classificação melhorou. Além disso, a confiabilidade do LLNA como uma ferramenta genérica para reconhecimento de padrões foi demonstrada para várias tarefas de classificação de diferentes escopos. A aplicabilidade de descritores estruturais de redes também foi destacada no contexto de caracterização de formas em visão computacional. Através da abordagem proposta, a ligação entre esses descritores de rede e as propriedades da forma, como ângulo e curvatura, foi ilustrada. Além disso, quando escolhidos adequadamente, os descritores de rede levam a um melhor desempenho de classificação para diferentes tarefas de categorização de formas. No que diz respeito ao modelo RPS, demonstramos que a presença de correlações de longo alcance nas redes afeta diretamente a dinâmica do modelo. Finalmente, foi apresentado como uma rede de transporte pode ser usada para prever surtos de gripe. Todos os métodos propostos utilizam diferentes aspectos da análise de redes e contribuem para o estudo de CAs e outras SEMs em tesselações irregulares, uma vez que estes modelos são geralmente descritos em topologias regulares. Além disso, uma nova metodologia foi proposta em relação ao reconhecimento de padrões em redes através do uso de padrões espaço-temporais como descritores da rede.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-28082019-104837 |
| Date | 28 May 2019 |
| Creators | Miranda, Gisele Helena Barboni |
| Contributors | Bruno, Odemir Martinez |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | English |
| Detected Language | English |
| Type | Tese de Doutorado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0031 seconds