Orientadores: Alberto Vazquez Saa, Marcus Aloizio Martinez de Aguiar / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Física Gleb Wataghin / Made available in DSpace on 2018-08-28T03:40:49Z (GMT). No. of bitstreams: 1 Pinto_RafaelSoares_D.pdf: 7979471 bytes, checksum: b344e1e01031709b8b938dbecb572900 (MD5) Previous issue date: 2015 / Resumo: Sincronização está presente em uma miríade de situações, indo desde vaga-lumes piscando em uníssono na copa das árvores, populações de leveduras ajustando seu metabolismo para um ritmo comum, atividades neurais ocorrendo no cérebro, chegando até as redes de distribuição de energia elétrica, as maiores máquinas construídas pelo homem. Neste trabalho, nós analisamos como se dá o processo de sincronização utilizando o bem conhecido modelo de Kuramoto, estudado incansavelmente nas últimas décadas, quando ele se encontra sobre uma rede complexa, que determina os padrões de interação entre os elementos que compõem a população. A topologia dessas interações determina de maneira crucial a dinâmica do sistema, possibilitando, ou não, a sincronização dos seus elementos. Primeiros, nós analisamos o fenômeno da sincronização explosiva: a correlação de propriedades da rede com a frequência natural dos osciladores altera dramaticamente a natureza da transição de fase do estado não sincronizado para o estado sincronizado. Mostramos que sincronização explosiva ocorre mesmo quando apenas uma pequena fração dos vértices da rede possuem tal correlação, a saber, os vértices mais bem conectados da rede. Além do mais, ajustando o número de vértices onde a correlação é válida, podemos controlar propriedades dessa transição de fase. A seguir estudamos o processo de optimização de topologia para favorecer sincronização. Dado um conjunto de vértices/osciladores com frequências naturais conhecidas e um certo número de links, qual é a melhor topologia, ou seja, o padrão de conexões, que favorece a sincronização? Estudamos esse problema numericamente para o modelo de Kuramoto com inércia, que serve como um modelo simples para analisar as redes de transmissão de energia elétrica, obtendo princípios básicos que devem ser utilizados para o design de tais sistemas. Por fim, ainda no problema de optimização de topologia para favorecer sincronização, obtivemos pela primeira vez de forma analítica as condições para optimização para o modelo de Kuramoto, bem como para uma generalização sua, onde há interações positivas e negativas. Esses resultados analíticos ainda servem para criar algoritmos de optimização mais ecientes que os utilizados atualmente / Abstract: Synchronization is present in a myriad of situations, from the unison ashing of reies in trees, populations of yeast adjusting their metabolism to a common rhythm, neural activities in the brain to the largest machines ever built, the power grids. We analysed how the process of synchronization happens using the well known Kuramoto model, tirelessly studied in the last decades, when it is on top of a complex network, that determines the patterns of interaction between the elements of the population. The topology of this network's determines crucially the possible dynamics of the systems, allowing, or not, the synchronization of its elements. We rst discuss the phenomenon of explosive synchronization, where the correlation between properties of the network and the oscillators changes drastically the nature of the phase transition separating the incoherent state from the synchronized state.We show that explosive synchronization can occur even when a small subset of the vertices are correlated. It is necessary that only the hubs, vertices with highest degrees, show the correlation. Moreover, adjust the fraction of correlated vertices allows us to control properties of the phase transition. Next we study the optimization of the topology to favor synchronization. Given a set of vertices/oscillators with know natural frequencies and a certain number of links, which is the best topology, its pattern of interactions, to favor synchronization? We studied this problem to a generalized Kuramoto model (Kuramoto model with inertia) that is used as a simple tool to model power grids, obtaining in this way simple rules that can be applied to the design of such systems that already helps the synchronization of its elements. In our nal contribution, still in the optimization of the topology problem, we were able, for the first time, to obtain analytically the conditions of optimization for the Kuramoto model, as well as for one of its generalizations, where there can exist positive and negative interactions between the elements. Beyond the signicant fact that the conditions can be know analytically, these results can be used to obtain faster optimization algorithms that the current ones / Doutorado / Física / Doutor em Ciências / 2012/09357-9 / CAPES

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

We explore the role of cooperativity and large deviations on a set of fundamental non-equilibrium many-body systems. In the cooperative asymmetric exclusion process, particles hop to the right at a constant rate only when the right neighboring site is vacant and hop at a faster rate when the left neighbor is occupied. In this model, a host of new heterogeneous density profile evolutions arise, including inverted shock waves and continuous compression waves. Cooperativity also drives the growth of complex networks via preferential attachment, where well-connected nodes are more likely to attract future connections. We introduce the mechanism of hindered redirection and show that it leads to network evolution by sublinear preferential attachment. We further show that no local growth rule can recreate superlinear preferential attachment. We also introduce enhanced redirection and show that the rule leads to networks with three unusual properties: (i) many macrohubs -- nodes whose degree is a finite fraction of the number of nodes in the network, (ii) a non-extensive degree distribution, and (iii) large fluctuations between different realizations of the growth process. We next examine large deviations in the diffusive capture model, where N diffusing predators initially all located at L 'chase' a diffusing prey initially at x<L. The prey survives if it reaches a haven at the origin without meeting any predator. We reduce the stochastic movement of the many predators to a deterministic trajectory of a single effective predator. Using optimized Monte Carlo techniques, we simulate up to 10^500 predators to confirm our analytic prediction that the prey survival probability S ~ N^-z^2, where z=x/L. Last, we quantify `survival of the scarcer' in two-species competition. In this model, individuals of two distinct species reproduce and engage in both intra-species and inter-species competition. Here a well-mixed population typically reaches a quasi steady state. We show that in this quasi-steady state the situation may arise where species A is less abundant than B but rare fluctuations make it more likely that species B first becomes extinct.

Social and computer networks permeate our lives. Large networks, such as the Internet, the World Wide Web (WWW), AND wireless smartphones, have indisputable economic and social importance. These networks have non-trivial topological features, i.e., features that do not occur in simple networks such as lattices or random networks. Estimating characteristics of these networks from incomplete (sampled) data is a challenging task. This thesis provides two frameworks within which common measurement tasks are analyzed and new, principled, measurement methods are designed. The first framework focuses on sampling directly observable network characteristics. This framework is applied to design a novel multidimensional random walk to efficiently sample loosely connected networks. The second framework focuses on the design of measurement methods to estimate indirectly observable network characteristics. This framework is applied to design two new, principled, estimators of flow size distributions over Internet routers using (1) randomly sampled IP packets and (2) a data stream algorithm.

This dissertation contributes to a methodology and a better understanding that can be used to study the effects of strategies during a pandemic, especially in multi-community networks. The dissertation is structured as the following: In the first chapter, we introduce the concept of networks and its properties, and node and link percolation, which is an important process embedded in networks. Then we discuss different epidemic models, among which the SIR model is representative of many infectious diseases, and can also be mapped into a link percolation problem. We bring up two quantities that are most important in evaluating the effectiveness of epidemic strategies, one is the total fraction of individuals ever been infected by the final steady state of the SIR model, the other is the peak fraction of infected throughout the process, the second of which has seldom been studied before. There have been many researches on epidemic models within isolated networks, but recently people start getting more interested in network of networks, due to its better representation of real world systems. So we study those two quantities and their dependence on the fraction of bridge nodes in multi-community networks, in the second and third chapters: In the second chapter, we look at the final steady state of the SIR (Susceptible-Infected-Recovered) model, which can be mapped as one cluster in a link percolation problem. Using the scaling relations for the cluster size distributions around the critical point within isolated networks, we find multiple regimes in a network with two communities so that the total fraction of individuals ever been infected asymptotically follows different power laws with the fraction of bridge nodes within each regime. We also find crossovers between neighbor regimes so that the power law exponent changes from one regime to the other. It is interesting to note that the power-law relations get steeper in regimes with smaller transmissibilities, so those epidemic strategies that reduce connections between communities are more effective in those regimes. In the third chapter, we look at the peak fraction of infected of the SIR model, which also shows power law relations with the fraction of bridge nodes in different regimes, as well as crossovers between regimes. We also find that the power-law relation for the peak fraction of infected with the fraction of bridge nodes is steeper than the one for the total fraction of individuals ever been infected in the same regime, which indicates that the peak fraction of infected is more sensitive to strategies that reduce connections between communities. This explains why strategies to flatten the curve are usually taken when there are limited medical resources.

No description available.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第24039号 / 情博第795号 / 新制||情||134(附属図書館) / 京都大学大学院情報学研究科システム科学専攻 / (主査)教授 下平 英寿, 教授 田中 利幸, 教授 加納 学 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-08-08T13:00:48Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) tese_MariaSibaldo.pdf: 2571529 bytes, checksum: 0d9af192f329870166c194c53541ce82 (MD5) / Made available in DSpace on 2016-08-08T13:00:48Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) tese_MariaSibaldo.pdf: 2571529 bytes, checksum: 0d9af192f329870166c194c53541ce82 (MD5) Previous issue date: 2016-02-23 / CAPEs / Os sistemas de recomendação fazem uso de algoritmos para facilitar a busca de itens de interesse do usuário. Esta tese apresenta uma solução para recomendação através do agrupamento em redes complexas, dado que este encontra padrões que beneficiam a recomendação. É utilizada a métrica de modularidade para auxiliar na divisão de uma rede em grupos e, com base nesse agrupamento, realizar recomendação. Assim, foram propostos dois métodos de recomendação baseados em modularidade, dois algoritmos de agrupamento e uma nova métrica de modularidade. O primeiro método proposto estima o peso da aresta entre dois elementos em uma rede bipartida (usuário e item) após a formação de grupos e faz uso das arestas do grupo do item. O método citado anteriormente serviu de inspiração para o segundo método, o qual faz uso das arestas entre grupos. Para este segundo método foram propostos dois algoritmos: AMV (Agrupamento com Movimento de Vértices), o qual realiza os agrupamentos com diversas métricas existentes; e o AMA (Agrupamento com Movimento de Arestas), o qual realiza agrupamentos apenas com a métrica proposta. O algoritmo AMA tem um tempo de processamento menor que o AMV. Com as observações realizadas na segunda proposta, uma nova métrica de modularidade foi elaborada para melhorar a recomendação. Esta modularidade possui maior valor quando os pesos dos relacionamentos entre os grupos são semelhantes. A primeira proposta se mostrou adequada para o problema e obteve o 6º lugar na competição do RecSys 2014. A segunda proposta obteve resultados comparativos equivalentes ao de métodos de recomendação no estado-da-arte. A métrica proposta mostrou-se adequada para a recomendação. / This thesis uses the modularity metric to assist in dividing a network into groups and, based on this grouping, apply recommendation procedure. We propose two methods of recommendation based on modularity, two grouping algorithm and also a new metric of modularity. The first method proposed estimates the rating between two nodes in a bipartite network after grouping it, for this estimation the item’s group is used. The first method was the inspiration for the second one: which uses the edges between groups to estimate the edges weight. Two algorithms were created for this second method: AMV (grouping with vertex movement), which can be used with different modularity metrics; and AMA (grouping with edges moviment), which makes use of the modularity metric proposed here and is faster than the previous one. A different modularity metric was proposed to improve the recommendation system. This modularity has greater value when the weights of relationships between groups are similar. The first proposal was adequate to the problem and obtained the 6th place in the RecSys Challenge 2014 competition. The second proposal has equivalent results compared to other recommendations methods in the state of the art. The experiments with the proposal metric showed that this metric is adequate to recommender systems.

The search for a satisfactory model for complexity, meant as an intermediate condition between total order and total disorder, is still subject of debate in the scientific community. In this dissertation the emergence of non-Poisson renewal processes in several complex systems is investigated. After reviewing the basics of renewal theory, another popular approach to complexity, called modulation, is introduced. I show how these two different approaches, given a suitable choice of the parameter involved, can generate the same macroscopic outcome, namely an inverse power law distribution density of events occurrence. To solve this ambiguity, a numerical instrument, based on the theoretical analysis of the aging properties of renewal systems, is introduced. The application of this method, called renewal aging experiment, allows us to distinguish if a time series has been generated by a renewal or a modulation process. This method of analysis is then applied to several physical systems, from blinking quantum dots, to the human brain activity, to seismic fluctuations. Theoretical conclusions about the underlying nature of the considered complex systems are drawn.

Doctor of Philosophy / Department of Electrical and Computer Engineering / Pietro Poggi-Corradini / Caterina M. Scoglio / The modulus of a family of walks quanti es the richness of the family by favoring having many short walks over a few longer ones. In this dissertation, we investigate various families of walks to study new measures for quantifying network properties using modulus. The proposed new measures are compared to other known quantities. Our proposed method is based on walks on a network, and therefore will work in great generality. For instance, the networks we consider can be directed, multi-edged, weighted, and even contain disconnected parts. We study the popular centrality measure known in some circles as information centrality, also known as e ective conductance centrality. After reinterpreting this measure in terms of modulus of families of walks, we introduce a modi cation called shell modulus centrality, that relies on the egocentric structure of the graph. Ego networks are networks formed around egos with a speci c order of neighborhoods. We then propose e cient analytical and approximate methods for computing these measures on both directed and undirected networks. Finally, we describe a simple method inspired by shell modulus centrality, called general degree, which improves simple degree centrality and could prove to be a useful tool for practitioners in the applied sciences. General degree is useful for detecting the best set of nodes for immunization. We also study the structure of loops in networks using the notion of modulus of loop families. We introduce a new measure of network clustering by quantifying the richness of families of (simple) loops. Modulus tries to minimize the expected overlap among loops by spreading the expected link-usage optimally. We propose weighting networks using these expected link-usages to improve classical community detection algorithms. We show that the proposed method enhances the performance of certain algorithms, such as spectral partitioning and modularity maximization heuristics, on standard benchmarks. Computing loop modulus bene ts from e cient algorithms for nding shortest loops, thus we propose a deterministic combinatorial algorithm that nds a shortest cycle in graphs. The proposed algorithm reduces the worst case time complexity of the existing combinatorial algorithms to O(nm) or O(hkin2 log n) while visiting at most m - n + 1 cycles (size of cycle basis). For most empirical networks with average degree in O(n1􀀀 ) our algorithm is subcubic.