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.

This work reports on stable (or invariant) topological properties and textual differentiation in human interaction networks, with benchmarks derived from public email lists. Activity along time and topology were observed in snapshots in a timeline, and at different scales. Our analysis shows that activity is practically the same for all networks across timescales ranging from seconds to months. The principal components of the participants in the topological metrics space remain practically unchanged as different sets of messages are considered. The activity of participants follows the expected scale-free outline, thus yielding the hub, intermediary and peripheral classes of vertices by comparison against the Erdös-Rényi model. The relative sizes of these three sectors are essentially the same for all email lists and the same along time. Typically, 3-12% of the vertices are hubs, 15-45% are intermediary and 44-81% are peripheral vertices. Texts from each of such sectors are shown to be very different through direct measurements and through an adaptation of the Kolmogorov-Smirnov test. These properties are consistent with the literature and may be general for human interaction networks, which has important implications for establishing a typology of participants based on quantitative criteria. For guiding and supporting this research, we also developed a visualization method of dynamic networks through animations. To facilitate verification and further steps in the analyses, we supply a linked data representation of data related to our results. / Este trabalho relata propriedades topológicas estáveis (ou invariantes) e diferenciação textual em redes de interação humana, com referências derivadas de listas públicas de e-mail. A atividade ao longo do tempo e a topologia foram observadas em instantâneos ao longo de uma linha do tempo e em diferentes escalas. A análise mostra que a atividade é praticamente a mesma para todas as redes em escalas temporais de segundos a meses. As componentes principais dos participantes no espaço das métricas topológicas mantêm-se praticamente inalteradas quando diferentes conjuntos de mensagens são considerados. A atividade dos participantes segue o esperado perfil livre de escala, produzindo, assim, as classes de vértices dos hubs, dos intermediários e dos periféricos em comparação com o modelo Erdös-Rényi. Os tamanhos relativos destes três setores são essencialmente os mesmos para todas as listas de e-mail e ao longo do tempo. Normalmente, 3-12% dos vértices são hubs, 15-45% são intermediários e 44-81% são vértices periféricos. Os textos de cada um destes setores são considerados muito diferentes através de uma adaptação dos testes de Kolmogorov-Smirnov. Estas propriedades são consistentes com a literatura e podem ser gerais para redes de interação humana, o que tem implicações importantes para o estabelecimento de uma tipologia dos participantes com base em critérios quantitativos. De modo a guiar e apoiar esta pesquisa, também desenvolvemos um método de visualização para redes dinâmicas através de animações. Para facilitar a verificação e passos seguintes nas análises, fornecemos uma representação em dados ligados dos dados relacionados aos nossos resultados.

Machine learning enables machines to learn automatically from data. In literature, graph-based methods have received increasing attention due to their ability to learn from both local and global information. In these methods, each data instance is represented by a vertex and is linked to other vertices according to a predefined affinity rule. However, they usually have unfeasible time cost for large problems. To overcome this problem, techniques can employ a heuristic to find suboptimal solutions in a feasible time. Early heuristic optimization methods exploit nature-inspired collective processes, such as ants looking for food sources and swarms of bees. Nowadays, advances in the field of complex systems provide powerful tools to assess and to understand dynamical systems. Complex networks, which are graphs with nontrivial topology, are among these theoretical tools capable of describing the interplay of topology, structure, and dynamics of complex systems. Therefore, machine learning methods based on complex networks and collective dynamics have been proposed. They encompass three steps. First, a complex network is constructed from the input data. Then, the simulation of a distributed collective system in the network generates rich information. Finally, the collected information is used to solve the learning problem. The coordination of the individuals in the system permit to achieve dynamics that is far more complex than the behavior of single individuals. In this research, I have explored collective dynamics in machine learning tasks, both in unsupervised and semi-supervised scenarios. Specifically, I have proposed a new collective system of competing particles that shifts the traditional vertex-centric dynamics to a more informative edge-centric one. Moreover, it is the first particle competition system applied in machine learning task that has deterministic behavior. Results show several advantages of the edge-centric model, including the ability to acquire more information about overlapping areas, a better exploration behavior, and a faster convergence time. Also, I have proposed a new network formation technique that is not based on similarity and has low computational cost. Since addition and removal of samples in the network is cheap, it can be used in real-time application. Finally, I have conducted analytical investigations of a flocking-like system that was needed to guarantee the expected behavior in community detection tasks. In conclusion, the result of the research contributes to many areas of machine learning and complex systems. / Aprendizado de máquina permite que computadores aprendam automaticamente dos dados. Na literatura, métodos baseados em grafos recebem crescente atenção por serem capazes de aprender através de informações locais e globais. Nestes métodos, cada item de dado é um vértice e as conexões são dadas uma regra de afinidade. Todavia, tais técnicas possuem custo de tempo impraticável para grandes grafos. O uso de heurísticas supera este problema, encontrando soluções subótimas em tempo factível. No início, alguns métodos de otimização inspiraram suas heurísticas em processos naturais coletivos, como formigas procurando por comida e enxames de abelhas. Atualmente, os avanços na área de sistemas complexos provêm ferramentas para medir e entender estes sistemas. Redes complexas, as quais são grafos com topologia não trivial, são uma das ferramentas. Elas são capazes de descrever as relações entre topologia, estrutura e dinâmica de sistemas complexos. Deste modo, novos métodos de aprendizado baseados em redes complexas e dinâmica coletiva vêm surgindo. Eles atuam em três passos. Primeiro, uma rede complexa é construída da entrada. Então, simula-se um sistema coletivo distribuído na rede para obter informações. Enfim, a informação coletada é utilizada para resolver o problema. A interação entre indivíduos no sistema permite alcançar uma dinâmica muito mais complexa do que o comportamento individual. Nesta pesquisa, estudei o uso de dinâmica coletiva em problemas de aprendizado de máquina, tanto em casos não supervisionados como semissupervisionados. Especificamente, propus um novo sistema de competição de partículas cuja competição ocorre em arestas ao invés de vértices, aumentando a informação do sistema. Ainda, o sistema proposto é o primeiro modelo de competição de partículas aplicado em aprendizado de máquina com comportamento determinístico. Resultados comprovam várias vantagens do modelo em arestas, includindo detecção de áreas sobrepostas, melhor exploração do espaço e convergência mais rápida. Além disso, apresento uma nova técnica de formação de redes que não é baseada na similaridade dos dados e possui baixa complexidade computational. Uma vez que o custo de inserção e remoção de exemplos na rede é barato, o método pode ser aplicado em aplicações de tempo real. Finalmente, conduzi um estudo analítico em um sistema de alinhamento de partículas. O estudo foi necessário para garantir o comportamento esperado na aplicação do sistema em problemas de detecção de comunidades. Em suma, os resultados da pesquisa contribuíram para várias áreas de aprendizado de máquina e sistemas complexos.

Orientadores: André Franceshi de Angelis, José Geraldo Pena de Andrade / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-24T15:13:51Z (GMT). No. of bitstreams: 1 Paiva_WilliamRobertode_M.pdf: 3222455 bytes, checksum: 4ba3e5407135ec1d8483e94ec4c11749 (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, propõe-se a avaliação de quatro métodos que possam melhorar a resiliência de redes de alta tensão através da adição de linhas de transmissão, utilizando-se a Teoria das Redes Complexas. Criou-se um modelo da rede brasileira de geração e transmissão de energia elétrica em forma de grafo para testar os métodos. O primeiro deles consiste em ligar pares de vértices que possuam menor grau em toda a rede. O segundo liga os vértices de menor betweenness. O terceiro efetua ligações entre pares de vértices de menor grau que estejam ligados aos vértices de maior carga em toda a rede. O último, faz ligações entre os dois vértices de betweenness mediano. Todos os métodos foram testados com e sem o auxílio do procedimento "min-cut", capaz de identificar as arestas que, ao serem removidas, dividem a rede em duas sub-redes, permitindo assim efetuar ligações que reduzam o risco dessa divisão. Além dos testes no modelo da rede brasileira, utilizaram-se também 1000 redes Scale-Free e 1000 aleatórias para verificar o aumento de eficiência trazidos. Todos os métodos foram capazes de aumentar a eficiência, tanto no modelo da rede real quanto nos modelos artificiais. A estratégia de ligar os vértices de betweenness mediano com auxílio do min-cut trouxe o maior aumento. A resiliência da rede, diante de falhas planejadas e falhas aleatórias, foi aumentada em poucos casos, porém, em nenhum houve redução da mesma. Conclui-se que as estratégias propostas podem ser utilizadas para melhorar a eficiência de redes de alta tensão, mantendo ou aumentando sua resiliência, bem como podem ser usadas para trazer os mesmos atributos para redes complexas em geral / Abstract: In this work we purpose to assess four methods to improve high-voltage networks resilience against failures and attacks, using the Complex Network Theory to do it. To test these methods, we created a network model in graph format, based on the Brazilian generation and transmission electrical network. The first of these methods consist in to link pairs of nodes which have the lowest degree in the network. The second creates a link betweenn the lowest betweenness nodes. The third method is to link the two lowest degree nodes which are linked to the highest load nodes. The last one creates a link betweenn the two nodes which has the median betweenness. All methods were tested with and without the use of the "min-cut" procedure. This procedure finds the lowest number of necessary links that, when removed, divide the network in two sub-networks. It allows us to identify these links and reduce the risk of this partitioning the network by adding new links. We also test the strategies in 1000 artificial Scale-Free networks and 1000 artificial Random networks to validate those methods. All strategies were able to increase efficiency, in the real and artificial networks models. The strategy which links the median betweenness nodes using the "min-cut" procedure brought the best results. The network resilience against planned and random failures was increased in in few cases, but no decreases was registered. We conclude that our strategies can be used to improve high-voltage network efficiency, keeping or improving its resilience, as they can be used to bring the same attribute to any type of complex networks / Mestrado / Tecnologia e Inovação / Mestre em Tecnologia

Orientador: André Munhoz de Argollo Ferrão / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Civil, Arquitetura e Urbanismo / Made available in DSpace on 2018-08-24T02:42:02Z (GMT). No. of bitstreams: 1 Goncalves_CaioMarcio_D.pdf: 5196417 bytes, checksum: 1b5a11393ecc1446ad09d0f9dc71f419 (MD5) Previous issue date: 2013 / Resumo: Os métodos, técnicas e abordagens clássicas de identificação e caracterização de problema parecem não satisfazer e responder plena e prontamente aos problemas complexos da sociedade contemporânea. A complexidade dos problemas atuais requer a adoção de ferramentas inovadoras, centradas no problema e não em efeitos ou soluções pré-concebidas. O desenvolvimento da humanidade é um processo empreendedor das sociedades que a compõem e deve estar orientado ao ser humano e seu contexto. Esse escopo enfatiza a noção de processo, da possibilidade, da lógica difusa, do complexo, do transdisciplinar, bem como o emprego de estratégias investigativas, inclusive do tipo pesquisa-ação. O propósito da pesquisa converge para um tipo de engenharia social que visa a definição de elementos estratégicos para a definição de uma abordagem voltada para a real identificação do problema. A "Abordagem de Resolução de Problema Complexo Orientada aos Princípios de Processo" [ARPCOOP] é o resultado da pesquisa e está fundamentada no arcabouço teórico existente sobre resolução de problema e nos princípios da visão de mundo em processo, lançando luzes sobre o problema e não sobre a solução / Abstract: The methods, techniques, and classical approaches for the identification and characterization of a problem does not seem to neither please, nor fully answer the complex problems of contemporary society in a speedy manner. The complexity of today's problems requires the adoption of innovative tools, problem-centered rather than in effects or preconceived solutions. The human development is an entrepreneurial process by the comprising societies, and should be directed to the human being and its context. This scope emphasizes the notion of process, the complex, the trans disciplinary, as well as the use of strategic action research investigations. The purpose of the research converges to a type of social engineering aimed at defining strategic elements to form an approach directed at identifying the real problem. Known as "The Approach to Complex Problem Solving Oriented toward the Principles of Process" [ARPCOOP], the proposal is based on existing theoretical framework of a problem and on the principles of the world view in the process, casting light on the problem and not the solution / Doutorado / Recursos Hidricos, Energeticos e Ambientais / Doutor em Engenharia Civil

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.

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

Com o desenvolvimento e barateamento dos equipamentos de aquisição de imagens, principalmente na área médica, tem sido geradas muitas imagens, as quais devem ser analisadas pelos especialistas. Esta tarefa pode ser muitas vezes cansativa e demorada, levando a possíveis erros no diagnóstico, pois a leitura das imagens depende da experiência e do estado físico e emocional do médico. Assim, sistemas de auxílio ao diagnóstico por computador (Computer-aided diagnosis - CAD) têm se tornado grandes aliados no processo de diagnóstico, realizando uma segunda leitura da imagem, servindo como uma segunda opinião ao especialista. Por isso, é necessário o desenvolvimento de técnicas de mineração de imagens para o aumento da precisão e da velocidade da análise das imagens. Assim, o objetivo deste trabalho foi desenvolver métodos de representação de imagens e de classificação associativa para aumentar a precisão da classificação de sistemas de auxílio ao diagnóstico médico por imagens. Para a representação de imagens foram desenvolvidas técnicas para reduzir a lacuna que há entre a representação numérica das imagens e seu significado semântico, a qual é chamada de `gap semântico\'. Para isso, foi usada a teoria das redes complexas para modelar as imagens em redes livres de escala, e os descritores das imagens foram compostos pelas medidas topológicas extraídas rede modelada. Os vetores de características gerados foram bem compactos, o que possibilitou também evitar o problema da `maldição da alta dimensionalidade\'. Para a classificação, foi desenvolvido o classificador associativo SACMiner, por meio do uso de regras de associação estatísticas, o qual evita a fase de discretização de dados, lidando diretamente com dados contínuos. Este foi um passo importante, já que a discretização pode causar a perda de informações e gerar inconsistência na base de dados. Além do SACMiner, foi desenvolvido o classificador MinSAR, o qual, além de não demandar a fase de discretização, também evita que o usuário tenha que fornecer parâmetros de entrada ao algoritmo responsável por gerar as regras. As técnicas até aqui listadas foram aplicadas em um sistema de auxílio ao diagnóstico de mama e comparadas com técnicas descritas na literatura, e os resultados mostram que as técnicas aqui propostas sobrepujaram as atuais da literatura. E por fim, foram sugeridas novas medidas para caracterizar imagens de pacientes com epilepsia no lobo temporal mesial, por meio do uso de medidas de espessura cortical, as quais melhoraram a precisão do sistema para este tipo de diagnóstico / The complexity of medical images and the high volume of exams per radiologist in a screening program can lead to a scenario prone to mistakes. Hence, it is important to inforce double reading and effective analysis, but those are costly measures. The computer-aided diagnosis (CAD) technology offers an alternative to double reading, because it can provide a computer output as a `second opinion\' to assist radiologists in interpreting images. Using this technology, the accuracy and consistency of radiological diagnoses can be improved, and also the image reading time can be reduced. Therefore, the need of classification and image representation methods and to speed-up and to assist the radiologists in the image analysis task has been increased. These methods must be more accurate and demand low computational cost, in order to provide a timely answer to the physician. The aim of this thesis was to developed image representation and associative classifiers methods to improve the classification of computer-aided diagnosis systems. Considering the image representation, in this work, we present some approaches to reduce the gap between the numeric representation of the images and their semantic, which is called `semantic gap\'. For this, we used the complex network theory to produce an image model based on scale-free networks. The image descriptors were composed of topological measures of the modeled network. The feature vectors produced were quite compact, which also allowed to avoid the problem called as `curse of dimensionality\'. Considering the classification task, we proposed the SACMiner classifier, which uses statistical association rules in order to avoid the discretization step when working with continuous attributes. It is important because the discretization step can disturb the dataset and cause lost of information. We also proposed de MinSAR classifier, which mines the rules not requiring a discretization step neither input thresholds, as most of the other association rules methods do. These approaches were applied in a breast cancer computer-aided diagnosis system. And finally, we developed an automatic technique which can aid in distinguishing between controls and patients with mesial temporal lobe epilepsy, based on cortical thickness, and potentially identifying abnormalities in tissue integrity in cases where atrophy cannot be visualized

As redes sociais se tornaram um novo e importante meio de intercâmbio de informações, ideias e comunicação que aproximam parentes e amigos sem importar as distâncias. Dada a natureza aberta da Internet, as informações podem fluir muito fácil e rápido na população. A rede pode ser representada como um grafo, onde os indivíduos ou organizações são o conjunto de vértices e os relacionamentos ou conexões entre os vértices são o conjunto de arestas. Além disso, as redes sociais representam intrinsecamente a estrutura de um sistema mais complexo que é a sociedade. Estas estruturas estão relacionadas com as características dos indivíduos. Por exemplo, os indivíduos mais populares são aqueles com maior número de conexões. Em particular, é aceito que a estrutura da rede pode afetar a forma como a informação se propaga nas redes sociais. No entanto, ainda não está claro como a estrutura influencia na propagação, como medir seu impacto e quais as possíveis estratégias para controlar o processo de difusão. Nesta tese buscamos contribuir nas análises da interação entre as dinâmicas de propagação de informações e rumores e a estrutura da rede. Propomos um modelo de propagação mais realista considerando a heterogeneidade dos indivíduos na transmissão de ideias ou informações. Nós confirmamos a presença de propagadores mais influentes na dinâmica de rumor e observamos que é possível melhorar ou reduzir expressivamente a difusão de uma informação ao selecionar uma fração muito pequena de propagadores influentes. No caso em que se objetiva selecionar um conjunto de propagadores iniciais que maximizem a difusão de informação, a melhor opção é selecionar os indivíduos mais centrais ou importantes nas comunidades. Porém, se o padrão de conexão dos vértices está negativamente correlacionado, a melhor alternativa é escolher entre os indivíduos mais centrais de toda a rede. Por outro lado, através de abordagens topológicas e de técnicas de aprendizagem máquina, identificamos aos propagadores menos influentes e mostramos que eles atuam como um firewall no processo de difusão. Nós propomos um método adaptativo de reconexão entre os vértices menos influentes para um indivíduo central da rede, sem afetar a distribuição de grau da rede. Aplicando o nosso método em uma pequena fração de propagadores menos influentes, observamos um aumento importante na capacidade de propagação desses vértices e da rede toda. Nossos resultados vêm de uma ampla gama de simulações em conjuntos de dados artificiais e do mundo real e a comparação com modelos clássicos de propagação da literatura. A propagação da informação em redes é de grande relevância para as áreas de publicidade e marketing, educação, campanhas políticas ou de saúde, entre outras. Os resultados desta tese podem ser aplicados e estendidos em diferentes campos de pesquisa como redes biológicas e modelos de comportamento social animal, modelos de propagação de epidemias e na saúde pública, entre outros. / On-line Social networks become a new and important medium of exchange of information, ideas and communication that approximate relatives and friends no matter the distances. Given the open nature of the Internet, the information can flow very easy and fast in the population. The network can be represented as a graph, where individuals or organizations are the set of vertices and the relationship or connection among the vertices are the set of edge. Moreover, the social networks are also intrinsically representing the structure of a more complex system that is the society. These structures are related with characteristics of the subjects, like the most popular individuals have many connections, the correlation in the connectivity of vertices that is a trace of homophily phenomenon, among many others. In particular, it is well accepted that the structure of the network can affect the way the information propagates on the social networks. However, how the structure impacts in the propagation, how to measure that impact and what are the strategies for controlling the propagation of some information, it is still unclear. In this thesis, we seek to contribute in the analysis of the interplay between the dynamics of information and rumor spreading and the structure of the networks. We propose a more realistic propagation model considering the heterogeneity of the individuals in the transmission of ideas or information. We confirm the presence of influential spreaders in the rumor propagation process and found that selecting a very small fraction of influential spreaders, it is possible to expressively improve or reduce de diffusion of some information on the network. In the case we want to select a set of initial spreaders that maximize the information diffusion on the network, the simple and best alternative is to select the most central or important individuals from the networks communities. But, if the pattern of connection of the networks is negatively correlated, the best alternative is to choose from the most central individuals in the whole network. On the other hand, we identify, by topological approach and machine learning techniques, the least influential spreaders and show that they act as a firewall in the propagation process. We propose an adaptative method that rewires one edge for a given vertex to a central individual, without affecting the overall distribution of connection. Applying our proposed method in a little fraction of least influential spreaders, we observed an important increasing in the capacity of propagation of these vertices and in the overall network. Our results are from a wide range of simulations in artificial and real-world data sets and the comparison with the classical rumor propagation model. The propagation of information is of greatest relevance for publicity and marketing area, education, political or health campaigns, among others. The results of this these might be applicable and extended in different research fields like biological networks and animal social behavior models.

This work applies complex network theory to the problem of semi-supervised and unsupervised learning in networks that are representations of multivariate datasets. Complex networks allow the use of nonlinear dynamical systems to represent behaviors according to the connectivity patterns of networks. Inspired by behavior observed in nature, such as competition for limited resources, dynamical system models can be employed to uncover the organizational structure of a network. In this dissertation, we develop a technique for classifying data represented as interaction networks. As part of the technique, we model a dynamical system inspired by the biological dynamics of resource competition. So far, similar methods have focused on vertices as the resource of competition. We introduce edges as the resource of competition. In doing so, the connectivity pattern of a network might be used not only in the dynamical system simulation but in the learning task as well. / Este trabalho aplica a teoria de redes complexas para o estudo de uma técnica aplicada ao problema de aprendizado semissupervisionado e não-supervisionado em redes, especificamente, aquelas que representam conjuntos de dados multivariados. Redes complexas permitem o emprego de sistemas dinâmicos não-lineares que podem apresentar comportamentos de acordo com os padrões de conectividade de redes. Inspirado pelos comportamentos observados na natureza, tais como a competição por recursos limitados, sistema dinâmicos podem ser utilizados para revelar a estrutura da organização de uma rede. Nesta dissertação, desenvolve-se uma técnica aplicada ao problema de classificação de dados representados por redes de interação. Como parte da técnica, um sistema dinâmico inspirado na competição por recursos foi modelado. Métodos similares concentraram-se em vértices como o recurso da concorrência. Neste trabalho, introduziu-se arestas como o recurso-alvo da competição. Ao fazê-lo, utilizar-se-á o padrão de conectividade de uma rede tanto na simulação do sistema dinâmico, quanto na tarefa de aprendizado.