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

The global financial system is an intricate network of networks, and recent financial crises have laid bare our insufficient understanding of its complexity. In response, within the five chapters of this thesis we study how interconnectedness, interdependency and mutual influence impact financial markets and systemic risk. In the first part, we investigate the community formation of global equity and currency markets. We find remarkable changes to correlation structure and lead-lag relationships in times of economic turmoil, implying significant risks to diversification based on historical data. The second part focuses on banks as creators of credit. Bank portfolios generally share some overlap, and this may introduce systemic risk. We model this using European stress test data, finding that the system is stable across a broad range of asset liquidity and risk tolerance. However, there exists a phase transition: If banks become sufficiently risk averse, even small shocks may inflict great losses. Failure to address portfolio overlap thus may leave the banking system ill-prepared. Complete knowledge of the financial network is prerequisite to such systemic risk analyses. When lacking this knowledge, maximum entropy methods allow a probabilistic reconstruction. In the third part of this thesis, we consider Japanese firm-bank data and find that reconstruction methods fail to generate a connected network. Deriving an analytical expression for connection probabilities, we show that this is a general problem of sparse graphs with inhomogeneous layers. Our results yield confidence intervals for the connectivity of a reconstruction. The maximum entropy approach also proves useful for studying dependencies in financial markets: On its basis, we develop a new measure for the information content in foreign exchange rates in part four of this thesis and use it to study the impact of macroeconomic variables on the strength of currency co-movements. While macroeconomic data and the law of supply and demand drive financial markets, foreign exchange rates are also subject to policy interventions. In part five, we classify the roles of currencies within the market with a clustering algorithm and study changes after political and monetary shocks. This methodology may further provide a quantitative underpinning to existing qualitative classifications. / 2019-12-11T00:00:00Z

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.