Дисертації з теми "Complex Networks of treaties"

Master of Science
Department of Electrical and Computer Engineering
Karen Garrett
Bala Natarajan
Caterina Scoglio
In this thesis, we propose a statistical model to predict disease dispersal in dynamic networks. We model the process of disease spreading using discrete time Markov chain. In this case, the vector of probability of infection is the state vector and every element of the state vector is a continuous variable between zero and one. In discrete time Markov chains, state probability vectors in each time step depends on state probability vector in the previous time step and one step transition probability matrix. The transition probability matrix can be time variant or time invariant. If this matrix’s elements are functions of elements of vector state probability in previous step, the corresponding Markov chain is non linear dynamical system. However, if those elements are independent of vector state probability, the corresponding Markov chain is a linear dynamical system. We especially focus on the dispersal of soybean rust. In our problem, we have a network of US counties and we aim at predicting that which counties are more likely to get infected by soybean rust during a year based on observations of soybean rust up to that time as well as corresponding observations to previous years. Other data such as soybean and kudzu densities in each county, daily wind data, and distance between counties helps us to build the model. The rapid growth in the number of Internet users in recent years has led malware generators to exploit this potential to attack computer users around the word. Internet users are frequent targets of malicious software every day. The ability of malware to exploit the infrastructures of networks for propagation determines how detrimental they can be to the network’s security. Malicious software can make large outbreaks if they are able to exploit the structure of the Internet and interactions between users to propagate. Epidemics typically start with some initial infected nodes. Infected nodes can cause their healthy neighbors to become infected with some probability. With time and in some cases with external intervention, infected nodes can be cured and go back to a healthy state. The study of epidemic dispersals on networks aims at explaining how epidemics evolve and spread in networks. One of the most interesting questions regarding an epidemic spread in a network is whether the epidemic dies out or results in a massive outbreak. Epidemic threshold is a parameter that addresses this question by considering both the network topology and epidemic strength.

Mestrado em Física da Matéria Condensada
The study of connectivity correlations between nodes has been somewhat neglected in the study of Complex Networks. We try to correct this by using the correlation function, combined with the concept of shell to calculate the connectivity distribution, P(d)(k) and the average connectivity for the neighbours, of a node as a function of distance d. With these results we create a better idea of how the Internet is organized and structured. We also determine that the time evolution of the Internet is coherent with the results obtained in the literature for the case of accelerated growth by the process of edge copying with a probability p=0.58.
O estudo das correlações de conectividade entre nodos tem sido algo negligenciado no estudo de Redes Complexas. Nós tentamos alterar esta situação usando funções de correlação em conjunto com o concenito de camada para calcular a distribuição de conectividades P(d)(k) e a conectividade média dos vizinhos de um nodo como função da distância d. Com estes resultados criamos uma melhor ideia acerca de como a Internet está organizada e estruturada. Concluimos também que a evolução da Internet é coerente com os resultados obtidos na literatura para o caso de crescimento acelerado devido a um processo de cópia de vértices com probabilidade p=0.58.

The study of network theory is nothing new, as we may find the first example of a proof of network theory back in the 18th century. However, in recent times, many researchers are using their time to investigate networks, giving new life to an old topic. As we are living in the era of information, networks are everywhere, and their complexity is constantly rising. The field of complex networks attempts to address this complexity with innovative solutions. Complex networks all share a series of common topological features, which revolve around the relationship between nodes, where relationship is intended in the most abstract possible way. Nonetheless, it is important to study these relationships because they can be exploited in several scenarios, like web page searching, recommender systems, e-commerce and so on. This thesis presents studies of sociality in complex networks, ranging from the microscale, which focuses the attention on the point of view of single nodes, to the mesoscale, instead shifts the interest in node groups.

Analyzing real-world networks ultimately amounts at com- paring their empirical properties with the outcome of a proper, statistical model. The far most common, and most useful, approach to define benchmarks rests upon the so-called canonical formalism of statistical mechanics which has led to the definition of the broad class of models known as Exponential Random Graphs (ERGs). Generally speaking, employing a model of this family boils down at maximizing a likelihood function that embodies the available information about a certain system, hence constituting the desired benchmark. Although powerful, the aforementioned models cannot be solved analytically, whence the need to rest upon numerical recipes for their optimization. Generally speaking, this is a hard task, since real-world networks can be enormous in size (for example, consisting of billions of nodes and links), hence requiring models with ‘many’ parameters (say, of the same order of magnitude of the number of nodes). This evidence calls for optimization algorithms which are both fast and scalable: the collection of works constituting the present thesis represents an attempt to fill this gap. Chapter 1 provides a quick introduction to the topic. Chapter 2 deals specifically with ERGs: after reviewing the basic concepts constituting the pillars upon which such a framework is based, we will discuss several instances of it and three different numerical techniques for their optimization. Chapter 3, instead, focuses on the detection of mesoscale structures and, in particular, on the formalism based upon surprise: as the latter allows any partition of nodes to be assigned a p-value, detecting a specific, mesoscale structural organization can be understood as the problem of finding the corresponding, most significant partition - i.e. an optimization problem whose score function is, precisely, surprise. Finally, chapter 4 deals with the application of a couple of ERGs and of the surprise-based formalism to cryptocurrencies (specifically, Bitcoin).

A complex system is a system for which the statement "the whole is greater than the sum of its parts" holds. A network can be viewed as a backbone of a complex system. Combining the knowledge about the entities constituting the complex system with the properties of the interaction patterns we can get a better understanding of why the whole is greater than the sum. One of the purposes of network studies, is to relate the particular structural and dynamical properties of the network to the function it is designed to perform. In the present work I am briefly presenting some of the advances that have been achieved in the field of the complex networks together with the contributions which I have been involved in.

Many complex systems such as the Internet can be represented as networks, with vertices denoting the constituent components of the systems and edges denoting the patterns of interactions among the components. In this thesis, we are interested in how the structural properties of a network, such as its average degree, degree distribution, clustering, and homophily affect the processes that take place on it. In the first part of the thesis we focus on evolutionary game theory models for studying the evolution of cooperation in a population of predominantly selfish individuals. In the second part we turn our attention to an evolutionary model of disease dynamics and the impact of vaccination on the spread of infection. Throughout the thesis we use a network as an abstraction for a population, with vertices representing individuals in the population and edges specifying who can interact with whom. We analyze our models for a well-mixed population, i.e., an infinite population with random mixing, and compare the theoretical results with those obtained from computer simulations on model and empirical networks.

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO
FUNDAÇÃO DE APOIO À PESQUISA DO ESTADO DO RIO DE JANEIRO
BOLSA NOTA 10
Esta tese aborda diversos problemas que podem ser tratados mediante modelos de dinâmica de opiniões, segundo os quais os indivíduos, conectados de acordo com redes complexas, interagem mediante regras que moldam as preferências e o posicionamento desses indivíduos com relação a uma determinada questão. A metodologia utilizada para investigar os padrões emergentes dessas interações consiste na utilização de diversas técnicas da física estatística. A tese está organizada em torno de quatro problemas distintos, com uma questão particular a ser respondida em cada caso, buscando sempre a validação empírica dos resultados teóricos e computacionais. No primeiro trabalho, é respondida a seguinte questão básica sobre propriedades da rede que podem ter impacto sobre os processos de propagação: quais são os valores típicos das distâncias, coeficiente de aglomeração e outras grandezas estruturais da rede, quando considerado o ensemble de redes aleatórias com uma assortatividade fixa? No segundo trabalho, investigamos os padrões que surgem na avaliação de filmes, considerando como fonte o IMDb (Internet Movie Database). Encontramos que a distribuição de votos apresenta um comportamento livre de escala com um expoente muito próximo de 3/2. Curiosamente, esse padrão é robusto, independente de atributos dos filmes como nota média, idade ou gênero. A análise empírica aponta para um mecanismo de propagação de adoções simples, que gera uma dinâmica de avalanches de campo médio. No terceiro trabalho, abordamos o problema de múltiplas escolhas por meio de um modelo que inclui a possibilidade de indecisão e onde as escolhas dos indivíduos evoluem segundo uma regra de pluralidade. Mostramos que essa dinâmica em redes com a propriedade de mundo pequeno produz diferentes estados estacionários realísticos, que dependem do número de alternativas e da distribuição de graus: consenso, distribuição de adoções larga similar à reais e situações onde a indecisão predomina, quando o número de alternativas é suficientemente grande. Por último, investigamos o surgimento de posições extremas na sociedade, mediante pesquisas em uma ampla gama de questões. O aumento de atitudes extremas tem como precursor uma relação não linear entre a fração de extremistas e a de moderados. Propomos um modelo, com regras de ativação baseadas na teimosia dos indivíduos, que permite interpretar o início da não linearidade em termos de uma transição abrupta do tipo percolação de inicialização onde acontecem cascatas de extremismo. Como conclusão geral, destacamos que esta tese ilustra como os modelos de opinião, aliados às enormes bases de dados, fornecem resultados com poder de interpretação e predição dos padrões empíricos.
This thesis addresses several problems that can be treated through models of opinion dynamics, according to which individuals, connected according to complex networks, interact through rules that shape their preferences and opinions in relation to a particular issue. The methodology used to investigate the patterns that emerge from those interactions relies on the use of various techniques of statistical physics. The thesis is organized around four distinct problems, with a particular question to be answered in each case, always looking for empirical validation of the theoretical and computational results. In the first work, it is answered the following basic question about network properties that can have impact on the spreading processes: what are the typical values of the distances, clustering coefficient and other structural quantities, when considering the ensemble of random networks with fix assortativity? In the second study, we investigated the patterns that emerge in the ratings of films, considering as source IMDb (Internet Movie Database). We found that the distribution of votes has a scale-free behavior with a exponent close to 3/2. Interestingly, this pattern is robust, independently of movie attributes such as average note, age or gender. The empirical analysis points to a simple mechanism of adoption propagation, that generates mean-field avalanches. In the third study, we discuss the problem of multiple choices by means of a model which includes the possibility of indecision and where the choices of individuals evolve according to a plurality rule. We show that this dynamics on top of networks with the small-world property produces different stationary states that depend on the number of alternatives and on the degree distribution: consensus, wide adoption distributions similar to actual ones and situations where indecision prevails when the number of alternatives is large enough. Finally, we investigate the appearance of extreme positions in society, through the polls on a wide variety of questions. The increase of extreme opinions has as precursor a non-linear relationship between the fraction of extremists and that of moderates. We propose a model with activation rules, based on the stubbornness of the individuals, which enables interpreting the beginning of the non-linearity in terms of an abrupt transition of the class of bootstrap percolation, where activation cascades occur. As a general conclusion, we emphasize that this thesis illustrates how opinion models, combined with huge databases, provide results with power of interpretation and prediction of empirical patterns.

Complex interacting systems permeate the modern world. Many diverse natural, social and human made systems—ranging from food webs to human contact networks, to the Internet—can be studied in the context of network science. This thesis is a compendium of research in applied network science, investigating structural and dynamical patterns behind the formation of networks and processes supported on them. Trophic food webs—networks of who eats whom in an ecosystem—have fascinated network scientists since data from field observations of the gut content of species first became available. The empirical patterns in food webs reveal a rich hierarchy of feeding patterns. We study how global structure of food webs relates to species immediate diet over a range of 46 different ecosystems. Our finding suggest that food webs fall broadly into two different families based on the extent of species tendency towards omnivory. Drawing inspiration from food webs, we investigate how trophic networks support spreading processes on them. We find that the interplay of dynamics and network structure determines the extent and duration of contagion. We uncover two distinct modes of operation—short-lived outbreaks with high incidence and endemic infections. These results could be important for understanding spreading phenomena such as epidemics, rumours, shocks to ecosystems and neuronal avalanches. Finally, we study the emergence of structural order in random network models. Random networks serve as null models to empirical networks to help uncover significant non-random patterns but are also interesting to study in their own right. We study the effect of triadic ties in delaying the formation of extensive giant components— connected components taking over the majority of the network. Our results show that, depending on the network formation process, order in the form of a giant component can emerge even with a significant number of triadic ties.

Many real-life systems can be modelled as complex networks, where the agents of the system are represented as nodes and the ties between those agents are represented as edges. Recent advances in data collection technologies give rise to various populations of networks, which capture different aspects of the data. In this thesis we make an essential progress in the modelling and analysis of three different populations of complex networks. First, in real-life systems involving measurements obtained from a population of participants, the system may be described by a population of networks where each participant is himself described by a whole network. We formulate a relevant genomics problem by constructing such a population of complex networks, and address a series of biological hypothesis which involve the clustering and classification of this population of networks. Second, real-life situations are modelled as a multiplex network where each layer of the multiplex captures different type of relationships across the same set of nodes. The nature of the multiplex network raises the question of whether the same connectivity patterns fit all layers. We use a community detection procedure to address this problem, where random walks on the multiplex are used to detect shared and non-shared community structures across the layers of the multiplex. Third, the interactions between the entities of a system that evolve in time are formalized as a temporal network. When the number of entities in the network is very large, different levels of detail and how they change in time are interesting. We use a multi-scale community detection procedure to solve the problems by applying spectral graph wavelets on the temporal network to detect changes in the community structure that occur in more than one scale.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Civil and Environmental Engineering, 2011.
Cataloged from PDF version of thesis.
Includes bibliographical references (p. 43-45).
The emergence of scaling in transport through interconnected systems is a consequence of the topological structure of the network and the physical mechanisms underlying the transport dynamics. We study transport by advection and diffusion in scale-free and Erdős-Rényi networks. Using stochastic particle simulations, we find anomalous (nonlinear) scaling of the mean square displacement with time. We show the connection with existing descriptions of anomalous transport in disordered systems, and explain the mean transport behavior from the coupled nature of particle jump lengths and transition times. Moreover, we study epidemic spreading through the air transportation network with a particle-tracking model that accounts for the spatial distribution of airports, detailed air traffic and realistic (correlated) waitingtime distributions of individual agents. We use empirical data from US air travel to constrain the model parameters and validate the model's predictions of traffic patterns. We formulate a theory that identifies the most influential spreaders from the point of view of early-time spreading behavior. We find that network topology, geography, aggregate traffic and individual mobility patterns are all essential for accurate predictions of spreading.
by Christos Nicolaides.
S.M.

This research study has produced advances in the understanding of communities within a complex network. A community in this context is defined as a subgraph with a higher internal density and a lower crossing density with respect to other subgraphs. In this study, a novel and efficient distance-based ranking algorithm called the Correlation Density Rank (CDR) has been proposed and is utilized for a broad range of applications, such as deriving the community structure and the evolution graph of the organizational structure from a dynamic social network, extracting common members between overlapped communities, performance-based comparison between different service providers in a wireless network, and finding optimal reliability-oriented assignment tasks to processors in heterogeneous distributed computing systems. The experiments, conducted on both synthetic and real datasets, demonstrate the feasibility and applicability of the framework.

The complex network theory has been extensively used to understand various natural and artificial phenomena made of interconnected parts. This representation enables the study of dynamical processes running on complex systems, such as epidemics and rumor spreading. The evolution of these dynamical processes is influenced by the organization of the network. The size of some real world networks makes it prohibitive to analyse the whole network computationally. Thus it is necessary to represent it by a set of topological measures or to reduce its size by means of sampling. In addition, most networks are samples of a larger networks whose structure may not be captured and thus, need to be inferred from samples. In this work, we study both problems: the influence of the structure of the network in spreading processes and the effects of sampling in the structure of the network. Our results suggest that it is possible to predict the final fraction of infected individuals and the final fraction of individuals that came across a rumor by modeling them with a beta regression model and using topological measures as regressors. The most influential measure in both cases is the average search information, that quantifies the ease or difficulty to navigate through a network. We have also shown that the structure of a sampled network differs from the original network and that the type of change depends on the sampling method. Finally, we apply four sampling methods to study the behaviour of the epidemic threshold of a network when sampled with different sampling rates and found out that the breadth-first search sampling is most appropriate method to estimate the epidemic threshold among the studied ones.
Vários fenômenos naturais e artificiais compostos de partes interconectadas vem sendo estudados pela teoria de redes complexas. Tal representação permite o estudo de processos dinâmicos que ocorrem em redes complexas, tais como propagação de epidemias e rumores. A evolução destes processos é influenciada pela organização das conexões da rede. O tamanho das redes do mundo real torna a análise da rede inteira computacionalmente proibitiva. Portanto, torna-se necessário representá-la com medidas topológicas ou amostrá-la para reduzir seu tamanho. Além disso, muitas redes são amostras de redes maiores cuja estrutura é difícil de ser capturada e deve ser inferida de amostras. Neste trabalho, ambos os problemas são estudados: a influência da estrutura da rede em processos de propagação e os efeitos da amostragem na estrutura da rede. Os resultados obtidos sugerem que é possível predizer o tamanho da epidemia ou do rumor com base em um modelo de regressão beta com dispersão variável, usando medidas topológicas como regressores. A medida mais influente em ambas as dinâmicas é a informação de busca média, que quantifica a facilidade com que se navega em uma rede. Também é mostrado que a estrutura de uma rede amostrada difere da original e que o tipo de mudança depende do método de amostragem utilizado. Por fim, quatro métodos de amostragem foram aplicados para estudar o comportamento do limiar epidêmico de uma rede quando amostrada com diferentes taxas de amostragem. Os resultados sugerem que a amostragem por busca em largura é a mais adequada para estimar o limiar epidêmico entre os métodos comparados.

Thesis (Ph.D.)--Boston University
PLEASE NOTE: Boston University Libraries did not receive an Authorization To Manage form for this thesis or dissertation. It is therefore not openly accessible, though it may be available by request. If you are the author or principal advisor of this work and would like to request open access for it, please contact us at open-help@bu.edu. Thank you.
This thesis employs methods of statistical mechanics and numerical simulations to study some aspects of dynamic and interacting complex networks. The mapping of various social and physical phenomena to complex networks has been a rich field in the past few decades. Subjects as broad as petroleum engineering, scientific collaborations, and the structure of the internet have all been analyzed in a network physics context, with useful and universal results. In the first chapter we introduce basic concepts in networks, including the two types of network configurations that are studied and the statistical physics and epidemiological models that form the framework of the network research, as well as covering various previously-derived results in network theory that are used in the work in the following chapters. In the second chapter we introduce a model for dynamic networks, where the links or the strengths of the links change over time. We solve the model by mapping dynamic networks to the problem of directed percolation, where the direction corresponds to the time evolution of the network. We show that the dynamic network undergoes a percolation phase transition at a critical concentration Pc, that decreases with the rate r at which the network links are changed. The behavior near criticality is universal and independent of r. We find that for dynamic random networks fundamental laws are changed: i) The size of the giant component at criticality scales with the network size N for all values of r, rather than as N^(2/3) in static network, ii) In the presence of a broad distribution of disorder, the optimal path length between two nodes in a dynamic network scales as N^(1/2), compared to N^(1/3) in a static network. The third chapter consists of a study of the effect of quarantine on the propagation of epidemics on an adaptive network of social contacts. For this purpose, we analyze the susceptible-infected-recovered model in the presence of quarantine, where susceptible individuals protect themselves by disconnecting their links to infected neighbors with probability w and reconnecting them to other susceptible individuals chosen at random. Starting from a single infected individual, we show by an analytical approach and simulations that there is a phase transition at a critical rewiring (quarantine) threshold We separating a phase (w < wc) where the disease reaches a large fraction of the population from a phase (w > wc) where the disease does not spread out. We find that in our model the topology of the network strongly affects the size of the propagation and that wc increases with the mean degree and heterogeneity of the network. We also find that wc is reduced if we perform a preferential rewiring, in which the rewiring probability is proportional to the degree of infected nodes. In the fourth chapter, we study epidemic processes on interconnected network systems, and find two distinct regimes. In strongly-coupled network systems, epidemics occur simultaneously across the entire system at a critical value f3e· In contrast, in weakly-coupled network systems, a mixed phase exists below f3e, where an epidemic occurs in one network but does not spread to the coupled network. We derive an expression for the network and disease parameters that allow this mixed phase and verify it numerically. Public health implications of communities comprising these two classes of network systems are also mentioned.
2031-01-01

The field of complex systems is a growing body of knowledge, It can be applied to countless different topics, from physics to computer science, biology, information theory and sociology. The main focus of this work is the use of microscopic models to study the behavior of urban mobility, which characteristics make it a paradigmatic example of complexity. In particular, simulations are used to investigate phase changes in a finite size open Manhattan-like urban road network under different traffic conditions, in search for the parameters to identify phase transitions, equilibrium and non-equilibrium conditions . It is shown how the flow-density macroscopic fundamental diagram of the simulation shows,like real traffic, hysteresis behavior in the transition from the congested phase to the free flow phase, and how the different regimes can be identified studying the statistics of road occupancy.

The field of complex systems is a growing body of knowledge, It can be applied to countless different topics, from physics to computer science, biology, information theory and sociology. The main focus of this work is the use of microscopic models to study the behavior of urban mobility, which characteristics make it a paradigmatic example of complexity. In particular, simulations are used to investigate phase changes in a finite size open Manhattan-like urban road network under different traffic conditions, in search for the parameters to identify phase transitions, equilibrium and non-equilibrium conditions . It is shown how the flow-density macroscopic fundamental diagram of the simulation shows,like real traffic, hysteresis behavior in the transition from the congested phase to the free flow phase, and how the different regimes can be identified studying the statistics of road occupancy.

Complex Networks analysis turn out to be a very promising field of research, testified by many research projects and works that span different fields. Those analysis have been usually focused on characterize a single aspect of the system and a study that considers many informative axes along with a network evolve is lacking. We propose a new multidimensional analysis that is able to inspect networks in the two most important dimensions, space and time. To achieve this goal, we studied them singularly and investigated how the variation of the constituting parameters drives changes to the network as a whole. By focusing on space dimension, we characterized spatial alteration in terms of abstraction levels. We proposed a novel algorithm that, by applying a fuzziness function, can reconstruct networks under different level of details. We verified that statistical indicators depend strongly on the granularity with which a system is described and on the class of networks. We keep fixed the space axes and we isolated the dynamics behind networks evolution process. We detected new instincts that trigger social networks utilization and spread the adoption of novel communities. We formalized this enhanced social network evolution by adopting special nodes (called sirens) that, thanks to their ability to attract new links, were able to construct efficient connection patterns. We simulated the dynamics of the system by considering three well-known growth models. Applying this framework to real and synthetic networks, we showed that the sirens, even when used for a limited time span, effectively shrink the time needed to get a network in mature state. In order to provide a concrete context of our findings, we formalized the cost of setting up such enhancement and provided the best combinations of system's parameters, such as number of sirens, time span of utilization and attractiveness.

Complex Networks analysis turn out to be a very promising field of research, testified by many research projects and works that span different fields. Those analysis have been usually focused on characterize a single aspect of the system and a study that considers many informative axes along with a network evolve is lacking. We propose a new multidimensional analysis that is able to inspect networks in the two most important dimensions, space and time. To achieve this goal, we studied them singularly and investigated how the variation of the constituting parameters drives changes to the network as a whole. By focusing on space dimension, we characterized spatial alteration in terms of abstraction levels. We proposed a novel algorithm that, by applying a fuzziness function, can reconstruct networks under different level of details. We verified that statistical indicators depend strongly on the granularity with which a system is described and on the class of networks. We keep fixed the space axes and we isolated the dynamics behind networks evolution process. We detected new instincts that trigger social networks utilization and spread the adoption of novel communities. We formalized this enhanced social network evolution by adopting special nodes (called sirens) that, thanks to their ability to attract new links, were able to construct efficient connection patterns. We simulated the dynamics of the system by considering three well-known growth models. Applying this framework to real and synthetic networks, we showed that the sirens, even when used for a limited time span, effectively shrink the time needed to get a network in mature state. In order to provide a concrete context of our findings, we formalized the cost of setting up such enhancement and provided the best combinations of system's parameters, such as number of sirens, time span of utilization and attractiveness.

The introduction provides an overview on complex networks, trying to investigate what apparently different kinds of networks have in common. Some statistical properties are illustrated and a simulation tool for the analysis of complex networks is presented. A weighted directed random graph is used as network model. The graph contains a fixed number N of nodes and a variable number of edges: in particular, each edge is present with probability p. Some statistical properties (such as strong connection, global and local efficiency, cost, etc) are computed and their reliance on probability p is studied. Some probability distributions (such as shortest path, edge/node load) are also drawn and, by using the method of stages, the best fitting curves are computed. The way as parameters characterizing such curves change when p varies is also investigated. The general structure of the proposed fitting technique allows to model several aspects of complex networks and makes possible its use in many different fields. Finally, the tracking control problem of linear time invariant (LTI) systems when the plant and the controller belong to the same network is considered. Time delays can degrade significantly the performance of a networked control system, eventually leading to instability. The problem characterized by constant and known network delays is analytically examined, showing how to construct a plant state predictor in order to compensate the time delays between the plant and the controller, so to allow the tracking of a reference signal. Computer simulations illustrate the effectiveness of the proposed technique, also when time delays slightly vary around a mean value.

One of the main issue in complex networks analysis consists in determining what are the most important nodes in a network. For this reason, researchers have defined several centrality indices in order to measure this concept. In several scenarios, having a high centrality can have a positive impact on the node itself. Hence, in this thesis we study the problem of determining how much a node can increase its centrality by creating a limited amount of new edges incident to it. In particular, we cope with the problem of adopting the best strategy in order to increase the value of two well known centrality indices namely harmonic centrality (cm-h) and betweenness centrality (cm-b). We show that cm-h cannot be approximated in polynomial-time within a factor 1− 1 3e in directed graphs and 1 − 1 15e in undirected graphs, unless P = NP. On the other hand, we prove that cm-b cannot be approximated in polynomial time within a factor 1 − 1 2e in both directed and undirected graphs, unless P = NP. We then propose a greedy approximation algorithm for both problems with an almost tight approximation ratio in all the cases except for cm-b in undirected networks. We test the performance of our algorithms on both synthetic and real-world networks and we show that they provide a good solution in every case. Moreover, we design some heuristics in order to speed up the computation and run the algorithm on large graphs with millions of nodes and edges. We also study the problem of improving the ranking according to harmonic centrality (crmb) and betweenness centrality (crm-b) by adding a limited amount of edges incident to a given node and we prove that it does not admit any polynomial-time constant factor approximation algorithm, unless P = NP. However, we experimentally show that our greedy algorithms allow a node to reach the top positions in the ranking by adding few new edges.

In a time when large amounts of data about social, economical, technological, and biological systems are produced in a daily bases, complex networks have become a powerful tool to represent the structure of complex systems. The advances in complex networks research have been geared towards the study of two main questions: what can we understand from a complex system by looking at its structure, and more importantly, what is the interplay between the topological and dynamical properties of complex systems. The aim of this dissertation is to review and introduce new tools and methods to measure topological and dynamical properties of complex networks. In particular, it covers two specific problems related with the two previously presented questions: the study of the community structure of complex networks, and the analysis of the dynamical properties of a communication process. The first part of the thesis is focused on the study of the community structure of complex networks, that is, how and why the nodes of the network tend to form groups in which they are highly interconnected. The understanding of this problem is key to characterize the internal organization of complex systems, obtaining better insights about the dynamical behavior of their components. In this part we present an exhaustive review of the community structure identification problem, explaining the limitations of the current existing methods, and we introduce a new method to extract the community structure based on the extremal optimization algorithm. We also present several improvements that increase the efficiency and accuracy of current community identification methods and an exhaustive benchmark of the results obtained when applying this new method to the standard network metrics. These results show that the extremal optimization method and its modifications are one of the fastest and most accurate options to identify the community structure of a network. The second part of the thesis is devoted to the study of some dynamical properties of communication processes over complex networks. Using a simple traffic model we analyze the changes observed on some properties when we introduce congestion in the network: the scaling of the fluctuations and the dynamical robustness. First, we present the scaling of the fluctuations in order to provide a large-scale dynamical characterization of the traffic flow. The idea is that there are a large number of real complex systems that show a scaling relation between the average flux and the variability of this flux. The understanding of the scaling relation presented in the dissertation will help us design better traffic models. And second, we study the dynamical robustness of the traffic, defined as the capability of maintaining the efficiency of the communication when we remove a fraction of nodes of the network. We show that there is a dynamical percolation threshold that splits the network due to the congestion before the topological percolation threshold.

Aquesta tesi tracta l’estudi de xarxes quàntiques amb una estructura complexa, les implicacions que aquesta estructura té en la distribució d’entrellaçament i com el seu funcionament pot ser millorat mitjançant operacions en el règim quàntic. Primer considerem xarxes complexes d’estats bipartits, tant purs com mescla, i estudiem la distribució d’entrellaçament a llargues distàncies. Després passem a analitzar xarxes de canals sorollosos i estudiem la creació i distribució de grans estats multipartits. El treball contingut en aquesta tesi està motivat principalment per la idea que la interacció entre la informació quàntica i les xarxes complexes pot donar lloc a una nova comprensió i caracterització dels sistemes naturals. Les xarxes complexes tenen una importància particular en les infraestructures de comunicació, ja que la majoria de xarxes de telecomunicació tenen una estructura complexa. En el cas de xarxes quàntiques, que són el marc necessari per al processament distribuït d’informació i comunicació quàntica, és ben possible que en el futur adquireixin una topologia complexa semblant a la de les xarxes existents, o que fins i tot es desenvolupin mètodes per a utilitzar les infraestructures actuals en el règim quàntic. Una tasca central en les xarxes quàntiques és dissenyar estratègies per distribuir entrellaçament entre els seus nodes. En la primera part d’aquesta tesi, considerem la distribució d’entrellaçament bipartit com un procés de percolació d’entrellaçament en una xarxa complexa. Des d’aquest enfocament, s’estableix entrellaçament perfecte de manera probabilística entre dos nodes arbitraris. Veiem que, per a xarxes grans, la probabilitat d’aconseguir-ho és una constant estrictament major que zero (i independent de la mida de la xarxa) si la quantitat inicial d’entrellaçament està per sobre d’un cert valor crític. La mecànica quàntica ofereix aquí la possibilitat de canviar l’estructura de la xarxa sense necessitat d’establir nous canals “físics”. Mitjançant una transformació local adequada de la xarxa, es pot disminuir l’entrellaçament crític i augmentar la probabilitat. Apliquem aquesta transformació a models de xarxes complexes amb una distribució de graus arbitrària. En el cas de xarxes sorolloses d’estats mescla, veiem que per algunes classes d’estat es pot utilitzar el mateix enfocament de percolació d’entrellaçament. Per a estats mescla generals considerem una percolació de llargada de camí limitada per la quantitat de soroll de les connexions. Veiem com les xarxes complexes ofereixen encara un gran avantatge en la probabilitat de connectar dos nodes. En la segona part, passem a l’escenari multipartit. Estudiem la creació i distribució d’estats graf amb una estructura que imita la de la xarxa de comuicació subjacent. En aquest cas, utilitzem una xarxa complexa arbitrària amb canals sorollosos, i considerem que les operacions i mesures són també sorolloses. Proposem un mètode eficient per a distribuir i purificar petits subgrafs, que després es fusionen per a reproduir l’estat desitjat. Comparem aquest enfocament amb dos protocols bipartits basats en un node central i coneixement complet de l’estructura de la xarxa. Mostrem que la fidelitat dels estats graf generats es pot escriure com la funció de partició d’un sistema desordenat de spins clàssics (un vidre de spins), i la seva taxa de decaïment és l’anàleg de l’energia lliure. Utilitzant els tres protocols en una xarxa unidimensional i en xarxes complexes veiem que són tots comparables, i que en alguns casos el protocol de subgrafs proposat, que necessita només informació local de la xarxa, té inclús un comportament millor.
This thesis deals with the study of quantum networks with a complex structure, the implications this structure has in the distribution of entanglement and how their functioning can be enhanced by operating in the quantum regime. We first consider a complex network of bipartite states, both pure and mixed, and study the distribution of long-distance entanglement. Then, we move to a network with noisy channels and study the creation and distribution of large, multipartite states. The work contained in this thesis is primarily motivated by the idea that the interplay between quantum information and complex networks may give rise to a new understanding and characterization of natural systems. Complex networks are of particular importance in communication infrastructures, as most present telecommunication networks have a complex structure. In the case of quantum networks, which are the necessary framework for distributed quantum processing and for quantum communication, it is very plausible that in the future they acquire a complex topology resembling that of existing networks, or even that methods will be developed to use current infrastructures in the quantum regime. A central task in quantum networks is to devise strategies to distribute entanglement among its nodes. In the first part of this thesis, we consider the distribution of bipartite entanglement as an entanglement percolation process in a complex network. Within this approach, perfect entanglement is established probabilistically between two arbitrary nodes. We see that for large networks, the probability of doing so is a constant strictly greater than zero (and independent of the size of the network) if the initial amount of entanglement is above a certain critical value. Quantum mechanics offer here the possibility to change the structure of the network without need to establish new, "physical" channels. By a proper local transformation of the network, the critical entanglement can be decreased and the probability increased. We apply this transformation to complex network models with arbitrary degree distribution. In the case of a noisy network of mixed states, we see that for some classes of states, the same approach of entanglement percolation can be used. For general mixed states, we consider a limited-path-length entanglement percolation constrained by the amount of noise in the connections. We see how complex networks still offer a great advantage in the probability of connecting two nodes. In the second part, we move to the multipartite scenario. We study the creation and distribution of graph states with a structure that mimic the underlying communication network. In this case, we use an arbitrary complex network of noisy channels, and consider that operations and measurements are also noisy. We propose an efficient scheme to distribute and purify small subgraphs, which are then merged to reproduce the desired state. We compare this approach with two bipartite protocols that rely on a central station and full knowledge of the network structure. We show that the fidelity of the generated graphs can be written as the partition function of a classical disordered spin system (a spin glass), and its decay rate is the analog of the free energy. Applying the three protocols to a one-dimensional network and to complex networks, we see that they are all comparable, and in some cases the proposed subgraph protocol, which needs only local information of the network, performs even better.

L’estudi de les xarxes complexes ha esdevingut un nou paradigma a l’hora d’entendre i modelar sistemes físics. Uns dels principals punts d’interès són les dinàmiques que hi podem modelar. Però com en tot model, la quantitat de informació que podem representar-hi està limitada per la seva complexitat. La motivació principal d’aquesta tesi és l’estudi de l’efecte que un increment de la complexitat estructural, relacional i temporal té sobre tres importants àrees d’estudi: l’evolució de la cooperació, la propagació de malalties, i l’estudi de la mobilitat humana. En aquest treball hem utilitzat dilemes socials per estudiar com evoluciona la cooperació dins d’una població. Incrementant l’ordre de complexitat estructural de les xarxes, permetent que els individus és puguin relacionar en diferents contextos socials, s’ha mostrat cabdal a l’hora d’explicar algunes característiques sobre l’aparició de comportaments altruistes. Utilitzant aquestes noves estructures, les xarxes multicapa, permetem als membres de la població cooperar en determinat contextos i de no fer-ho en d’altres i això, com analíticament demostrem, augmenta l’espectre d’escenaris allà on cooperació i defecció poden sobreviure. Seguidament, estudiem els models de propagació de malalties des de el punt de vista dels enllaços entre individus. Amb aquest augment de la complexitat relacional dels models epidèmics, aconseguim extreure informació que ens permet, entre altres coses, definir una mesura d’influència d’un enllaç a la propagació de l’epidèmia. Utilitzem aquest fet per a proposar una nova mesura de contenció, basada en l’eliminació dels enllaços més influents, que es mostra més eficient que altres mètodes previs. Finalment, proposem un mètode per a descriure la mobilitat que permet capturar patrons recurrents i heterogeneïtats en els temps que els individus estan en un lloc abans de desplaçar-se a un altre. Aquestes propietats són intrínseques a la mobilitat humana i el fet de poder-les capturar, tot i el cost d’augmentar l’ordre temporal, és crític, com demostrem, a l’hora de modelar com les epidèmies és difonen per mitja del moviment de les persones.
El estudio de redes complejas se ha convertido en un nuevo paradigma para comprender y modelar sistemas físicos. Uno de los principales puntos de interés son las dinámicas que podemos modelar. Pero como en todo modelo, la cantidad de información que podemos representar está limitada por su complejidad. La motivación principal de esta tesis es estudiar el efecto que un incremento de la complejidad estructural, relacional y temporal tiene sobre tres importantes áreas de estudio: la evolución de la cooperación, la propagación de enfermedades, y el estudio de la movilidad humana. En este trabajo hemos utilizado dilemas sociales para estudiar cómo evoluciona la cooperación dentro de una población. Incrementando el orden de complejidad estructural de las redes, permitiendo que los individuos se puedan relacionar en diferentes contextos sociales, se ha demostrado capital para explicar algunas de las características sobre la aparición de comportamientos altruistas. Utilizando estas nuevas estructuras, las redes multicapa, permitimos a los miembros de la población cooperar en determinados contextos y no hacerlo en otros, con lo que, como demostramos analíticamente, aumenta el espectro de escenarios en los que la cooperación y la defección pueden sobrevivir. A continuación, estudiamos modelos de propagación de enfermedades desde el punto de vista de los enlaces entre individuos. Con este aumento de complejidad relacional de los modelos epidémicos, conseguimos extraer información que nos permite, entre otras cosas, definir una medida de contención, basada en la eliminación de los enlaces más influyentes, que se muestra más eficaz que otros métodos previos. Finalmente, proponemos un método para describir la movilidad que permite capturar patrones recurrentes y heterogeneidades en los tiempos que los individuos están en un lugar antes de desplazarse a otro. Estas propiedades son intrínsecas a la movilidad humana y el hecho de poder capturarlas, a pesar de incrementar el orden temporal, es crítico, como demostramos, para modelar cómo las epidemias se difunden por medio del movimiento de las personas.
The study of complex networks has become a new paradigm to understand and model physical systems. One of the points of interest is the dynamics that we can model. However, as with any model, the amount of information that we can represent is limited by its complexity. The primary motivation of this thesis is the study of the effect that an increase in structural, relational and temporal complexity has on three critical areas of study: the evolution of cooperation, epidemic spreading and human mobility. In this work, we have used social dilemmas to study how cooperation within a population evolves. Increasing the order of structural complexity of the networks, allowing individuals to interact in different social contexts, has shown to be crucial to explain some features about the emergence of altruistic behaviors. Using these new structures, multilayer networks, we allow members of the population to cooperate in specific contexts and defect in others, and this, as we analytically demonstrate, increases the spectrum of scenarios where both strategies can survive. Next, we study the models of epidemic spreading from the point of view of the links between individuals. With this increase in the relational complexity of the epidemic models, we can extract information that allows us, among other things, to define a measure of the contribution of a link to the spreading. We use this metric to propose a new containment measure, based on the elimination of the most influential links, which is more effective than other previous methods. Finally, we propose a method to describe mobility that allows capturing recurrent and heterogeneous patterns in the times that individuals stay in a place before moving to another. These properties are intrinsic to human mobility, and the fact of being able to capture them, despite the cost of increasing the temporal order is critical, as we demonstrate, when it comes to modeling how epidemics spread through the movement of the people.

Un problema principal de la ciència de xarxes és com reconstruir (inferir) la topologia d’una xarxa real a partir de senyals mesurades de les seves unitats internes. Entendre la arquitectura d’una xarxa complexa és clau, no només per comprendre el seu funcionament, sinó també per predir i controlar el seu comportament. Els mètodes actualment disponibles es centren principalment en la detecció d’enllaços de xarxes no direccio- nals i sovint requereixen suposicions fortes sobre el sistema. Tanmateix, molts d’aquests mètodes no es poden aplicar a xarxes amb connexions direccionals. Per abordar aquest problema, en aquesta tesis ens centrarem en la inferència de xarxes direccionals. Concretament, desenvolupem un mètode de reconstrucció de xarxes basat en models que combina estadístiques de correlacions de derivades amb recuit simulat. A més, desenvolupem un mètode de reconstrucció basat en dades cimentat en una mesura d’interpedendència no lineal. Aquest mètode permet inferir la topologia de xarxes direccionals d’oscil.ladors caòtics de Lorenz per un subordre de la força d’acoblament i la densitat de la xarxa. Finalment, apliquem el mètode basat en dades a gravacions electroencefalogràfiques d’un pacient amb epilèpsia. Les xarxes cerebrals funcionals obtingu- des a partir d’aquest mètode són coherents amb la informació mèdica disponible.
Un problema principal de la ciencia de redes es cómo reconstruir (inferir) la topología de una red real usando la señales medidas de sus unidades internas. Entender la arquitectura de redes complejas es clave, no solo para entender su funcionamiento pero también para predecir y controlar su comportamiento. Los métodos existentes se focalizan en la detección de redes no direccionales y normalmente requieren fuertes suposicio- nes sobre el sistema. Sin embargo, muchos de estos métodos no pueden ser aplicados en redes con conexiones direccionales. Para abordar este problema, en esta tesis estudiamos la reconstrucción de redes direccio- nales. En concreto, desarrollamos un método de reconstrucción basado en modelos que combina estadísticas de correlaciones de derivadas con recocido simulado. Además, desarrollamos un método basado en datos cimentado en una medida d’interdependencia no lineal. Este método permite inferir la topología de redes direccionales de osciladores caóticos de Lorenz para un subrango de la fuerza de acoplamiento y densidad de la red. Finalmente, aplicamos el método basado en datos a grabaciones electroencefalográficas de un paciente con epilepsia. Las redes cerebra- les funcionales obtenidas usando este método son consistentes con la información médica disponible.
A foremost problem in network science is how to reconstruct (infer) the topology of a real network from signals measured from its internal units. Grasping the architecture of complex networks is key, not only to understand their functioning, but also to predict and control their behaviour. Currently available methods largely focus on the detection of links of undirected networks and often require strong assumptions about the system. However, many of these methods cannot be applied to networks with directional connections. To address this problem, in this doctoral work we focus at the inference of directed networks. Specifically, we develop a model-based network reconstruction method that combines statistics of derivative-variable correlations with simulated annealing. We furthermore develop a data-driven reconstruction method based on a nonlinear interdependence measure. This method allows one to infer the topology of directed networks of chaotic Lorenz oscillators for a subrange of the coupling strength and link density. Finally, we apply the data-driven method to multichannel electroencephalographic recordings from an epilepsy patient. The functional brain networks obtained from this approach are consistent with the available medical information.

Complex network theory provides an elegant and powerful framework to statistically investigate the topology of local and long range dynamical interrelationships, i.e., teleconnections, in the climate system. Employing a refined methodology relying on linear and nonlinear measures of time series analysis, the intricate correlation structure within a multivariate climatological data set is cast into network form. Within this graph theoretical framework, vertices are identified with grid points taken from the data set representing a region on the the Earth's surface, and edges correspond to strong statistical interrelationships between the dynamics on pairs of grid points. The resulting climate networks are neither perfectly regular nor completely random, but display the intriguing and nontrivial characteristics of complexity commonly found in real world networks such as the internet, citation and acquaintance networks, food webs and cortical networks in the mammalian brain. Among other interesting properties, climate networks exhibit the "small-world" effect and possess a broad degree distribution with dominating super-nodes as well as a pronounced community structure. We have performed an extensive and detailed graph theoretical analysis of climate networks on the global topological scale focussing on the flow and centrality measure betweenness which is locally defined at each vertex, but includes global topological information by relying on the distribution of shortest paths between all pairs of vertices in the network. The betweenness centrality field reveals a rich internal structure in complex climate networks constructed from reanalysis and atmosphere-ocean coupled general circulation model (AOGCM) surface air temperature data. Our novel approach uncovers an elaborately woven meta-network of highly localized channels of strong dynamical information flow, that we relate to global surface ocean currents and dub the backbone of the climate network in analogy to the homonymous data highways of the internet. This finding points to a major role of the oceanic surface circulation in coupling and stabilizing the global temperature field in the long term mean (140 years for the model run and 60 years for reanalysis data). Carefully comparing the backbone structures detected in climate networks constructed using linear Pearson correlation and nonlinear mutual information, we argue that the high sensitivity of betweenness with respect to small changes in network structure may allow to detect the footprints of strongly nonlinear physical interactions in the climate system. The results presented in this thesis are thoroughly founded and substantiated using a hierarchy of statistical significance tests on the level of time series and networks, i.e., by tests based on time series surrogates as well as network surrogates. This is particularly relevant when working with real world data. Specifically, we developed new types of network surrogates to include the additional constraints imposed by the spatial embedding of vertices in a climate network. Our methodology is of potential interest for a broad audience within the physics community and various applied fields, because it is universal in the sense of being valid for any spatially extended dynamical system. It can help to understand the localized flow of dynamical information in any such system by combining multivariate time series analysis, a complex network approach and the information flow measure betweenness centrality. Possible fields of application include fluid dynamics (turbulence), plasma physics and biological physics (population models, neural networks, cell models). Furthermore, the climate network approach is equally relevant for experimental data as well as model simulations and hence introduces a novel perspective on model evaluation and data driven model building. Our work is timely in the context of the current debate on climate change within the scientific community, since it allows to assess from a new perspective the regional vulnerability and stability of the climate system while relying on global and not only on regional knowledge. The methodology developed in this thesis hence has the potential to substantially contribute to the understanding of the local effect of extreme events and tipping points in the earth system within a holistic global framework.
Die Theorie komplexer Netzwerke bietet einen eleganten Rahmen zur statistischen Untersuchung der Topologie lokaler und langreichweitiger dynamischer Zusammenhänge (Telekonnektionen) im Klimasystem. Unter Verwendung einer verfeinerten, auf linearen und nichtlinearen Korrelationsmaßen der Zeitreihenanalyse beruhenden Netzwerkkonstruktionsmethode, bilden wir die komplexe Korrelationsstruktur eines multivariaten klimatologischen Datensatzes auf ein Netzwerk ab. Dabei identifizieren wir die Knoten des Netzwerkes mit den Gitterpunkten des zugrundeliegenden Datensatzes, während wir Paare von besonders stark korrelierten Knoten als Kanten auffassen. Die resultierenden Klimanetzwerke zeigen weder die perfekte Regularität eines Kristallgitters, noch eine vollkommen zufällige Topologie. Vielmehr weisen sie faszinierende und nichttriviale Eigenschaften auf, die charakteristisch für natürlich gewachsene Netzwerke wie z.B. das Internet, Zitations- und Bekanntschaftsnetzwerke, Nahrungsnetze und kortikale Netzwerke im Säugetiergehirn sind. Besonders erwähnenswert ist, dass in Klimanetzwerken das Kleine-Welt-Phänomen auftritt. Desweiteren besitzen sie eine breite Gradverteilung, werden von Superknoten mit sehr vielen Nachbarn dominiert, und bilden schließlich regional wohldefinierte Untergruppen von intern dicht vernetzten Knoten aus. Im Rahmen dieser Arbeit wurde eine detaillierte, graphentheoretische Analyse von Klimanetzwerken auf der globalen topologischen Skala durchgeführt, wobei wir uns auf das Netzwerkfluss- und Zentralitätsmaß Betweenness konzentrierten. Betweenness ist zwar lokal an jedem Knoten definiert, enthält aber trotzdem Informationen über die globale Netzwerktopologie. Dies beruht darauf, dass die Verteilung kürzester Pfade zwischen allen möglichen Paaren von Knoten in die Berechnung des Maßes eingeht. Das Betweennessfeld zeigt reichhaltige und zuvor verborgene Strukturen in aus Reanalyse- und Modelldaten der erdoberflächennahen Lufttemperatur gewonnenen Klimanetzen. Das durch unseren neuartigen Ansatz enthüllte Metanetzwerk, bestehend aus hochlokalisierten Kanälen stark gebündelten Informationsflusses, bringen wir mit der Oberflächenzirkulation des Weltozeans in Verbindung. In Analogie mit den gleichnamigen Datenautobahnen des Internets nennen wir dieses Metanetzwerk den Backbone des Klimanetzwerks. Unsere Ergebnisse deuten insgesamt darauf hin, dass Meeresoberflächenströmungen einen wichtigen Beitrag zur Kopplung und Stabilisierung des globalen Oberflächenlufttemperaturfeldes leisten. Wir zeigen weiterhin, dass die hohe Sensitivität des Betweennessmaßes hinsichtlich kleiner Änderungen der Netzwerktopologie die Detektion stark nichtlinearer physikalischer Wechselwirkungen im Klimasystem ermöglichen könnte. Die in dieser Arbeit vorgestellten Ergebnisse wurden mithilfe statistischer Signifikanztests auf der Zeitreihen- und Netzwerkebene gründlich auf ihre Robustheit geprüft. In Anbetracht fehlerbehafteter Daten und komplexer statistischer Zusammenhänge zwischen verschiedenen Netzwerkmaßen ist diese Vorgehensweise besonders wichtig. Weiterhin ist die Entwicklung neuer, allgemein anwendbarer Surrogate für räumlich eingebettete Netzwerke hervorzuheben, die die Berücksichtigung spezieller Klimanetzwerkeigenschaften wie z.B. der Wahrscheinlichkeitsverteilung der Kantenlängen erlauben. Unsere Methode ist universell, weil sie zum Verständnis des lokalisierten Informationsflusses in allen räumlich ausgedehnten, dynamischen Systemen beitragen kann. Deshalb ist sie innerhalb der Physik und anderer angewandter Wissenschaften von potentiell breitem Interesse. Mögliche Anwendungen könnten sich z.B. in der Fluiddynamik (Turbulenz), der Plasmaphysik und der Biophysik (Populationsmodelle, neuronale Netzwerke und Zellmodelle) finden. Darüber hinaus ist der Netzwerkansatz für experimentelle Daten sowie Modellsimulationen gültig, und eröffnet folglich neue Perspektiven für Modellevaluation und datengetriebene Modellierung. Im Rahmen der aktuellen Klimawandeldebatte stellen Klimanetzwerke einen neuartigen Satz von Analysemethoden zur Verfügung, der die Evaluation der lokalen Vulnerabilität und Stabilität des Klimasystems unter Berücksichtigung globaler Randbedingungen ermöglicht. Die in dieser Arbeit entwickelten und untersuchten Methoden könnten folglich in der Zukunft, innerhalb eines holistisch-globalen Ansatzes, zum Verständnis der lokalen Auswirkungen von Extremereignissen und Kipppunkten im Erdsystem beitragen.

An interaction in a complex network is any kind of information or process that can propagate between network units or components along network links. Complex networks, which represent the structural skeleton of our societal, technological and infrastructural systems, play a major role in the propagation of processes. These processes include for example the case of epidemic spreading, the diffusion process, synchronisation, the consensus process and many others. It is usually assumed that interactions in networks propagate only from a node to its nearest neighbours. This thesis is about interactions that can be transmitted from a node to others that are not directly connected to it. These types of interactions are here called long-range interactions (LRI). The thesis is about those long-range interactions in complex networks. We will focus on the case of infection or epidemic spreading in complex networks. An "infection", understood here in a very broad sense, can be propagated through the network of social contacts among individuals. These social contacts include both "close" contacts and "casual" encounters among individuals in transport, leisure, shopping, etc. Knowing the first through the study of the social networks is not a difficult task, but having a clear picture of the network of casual contacts is a very hard problem in a society of increasing mobility. Here we assume, on the basis of several pieces of empirical evidence, that the casual contacts between two individuals are a function of their social distance in the network of close contacts. Then, we assume that we know the network of close contacts and infer the casual encounters by means of nonrandom long-range (LR) interactions determined by the social proximity of the two individuals. This approach is then implemented in a susceptible-infected-susceptible (SIS) model accounting for the spread of infections in complex networ ks. A parameter called "conductance" controls the feasibility of those casual encounters. In a zero conductance network only contagion through close contacts is allowed. As the conductance increases the probability of having casual encounters also increases. We show here that as the conductance parameter increases, the rate of propagation increases dramatically and the infection is less likely to die out. This increment is particularly marked in networks with scale-free degree distributions, where infections easily become epidemics. We show that the epidemic threshold of the model is given by the inverse of the largest eigenvalue of the generalised graph matrix that represents all the social contacts in the network. We point out that, from a Statistical Mechanical point of view, the epidemic threshold is also seen as the negative of the inverse of the free energy of the network when the system is frozen at extremely low temperatures. The proposed model is able to reproduce the age-assortativity or homophily observed in many social networks. Our model provides a general framework for studying epidemic spreading in networks with arbitrary topology with and without casual contacts accounted for by means of LR interactions.

Doctor of Philosophy
Department of Electrical and Computer Engineering
Caterina Scoglio
Critical infrastructures are repeatedly attacked by external triggers causing tremendous amount of damages. Any infrastructure can be studied using the powerful theory of complex networks. A complex network is composed of extremely large number of different elements that exchange commodities providing significant services. The main functions of complex networks can be damaged by different types of attacks and failures that degrade the network performance. These attacks and failures are considered as disturbing dynamics, such as the spread of viruses in computer networks, the spread of epidemics in social networks, and the cascading failures in power grids. Depending on the network structure and the attack strength, every network differently suffers damages and performance degradation. Hence, quantifying the robustness of complex networks becomes an essential task. In this dissertation, new metrics are introduced to measure the robustness of technological and social networks with respect to the spread of epidemics, and the robustness of power grids with respect to cascading failures. First, we introduce a new metric called the Viral Conductance ($VC_{SIS}$) to assess the robustness of networks with respect to the spread of epidemics that are modeled through the susceptible/infected/susceptible ($SIS$) epidemic approach. In contrast to assessing the robustness of networks based on a classical metric, the epidemic threshold, the new metric integrates the fraction of infected nodes at steady state for all possible effective infection strengths. Through examples, $VC_{SIS}$ provides more insights about the robustness of networks than the epidemic threshold. In addition, both the paradoxical robustness of Barab\'si-Albert preferential attachment networks and the effect of the topology on the steady state infection are studied, to show the importance of quantifying the robustness of networks. Second, a new metric $VC_$ is introduced to assess the robustness of networks with respect to the spread of susceptible/infected/recovered ($SIR$) epidemics. To compute $VC_$, we propose a novel individual-based approach to model the spread of $SIR$ epidemics in networks, which captures the infection size for a given effective infection rate. Thus, $VC_$ quantitatively integrates the infection strength with the corresponding infection size. To optimize the $VC_$ metric, a new mitigation strategy is proposed, based on a temporary reduction of contacts in social networks. The social contact network is modeled as a weighted graph that describes the frequency of contacts among the individuals. Thus, we consider the spread of an epidemic as a dynamical system, and the total number of infection cases as the state of the system, while the weight reduction in the social network is the controller variable leading to slow/reduce the spread of epidemics. Using optimal control theory, the obtained solution represents an optimal adaptive weighted network defined over a finite time interval. Moreover, given the high complexity of the optimization problem, we propose two heuristics to find the near optimal solutions by reducing the contacts among the individuals in a decentralized way. Finally, the cascading failures that can take place in power grids and have recently caused several blackouts are studied. We propose a new metric to assess the robustness of the power grid with respect to the cascading failures. The power grid topology is modeled as a network, which consists of nodes and links representing power substations and transmission lines, respectively. We also propose an optimal islanding strategy to protect the power grid when a cascading failure event takes place in the grid. The robustness metrics are numerically evaluated using real and synthetic networks to quantify their robustness with respect to disturbing dynamics. We show that the proposed metrics outperform the classical metrics in quantifying the robustness of networks and the efficiency of the mitigation strategies. In summary, our work advances the network science field in assessing the robustness of complex networks with respect to various disturbing dynamics.

Due to a large amount of textual information available on the Internet, the task of automatic document summarization has gained significant importance. Document summarization became important because its focus is the development of techniques aimed at finding relevant and concise content in large volumes of information without changing its original meaning. The purpose of this Masters work is to use network theory concepts for extractive document summarization for both Single Document Summarization (SDS) and Multi-Document Summarization (MDS). In this work, the documents are modeled as networks, where sentences are represented as nodes with the aim of extracting the most relevant sentences through the use of ranking algorithms. The edges between nodes are established in different ways. The first approach for edge calculation is based on the number of common nouns between two sentences (network nodes). Another approach to creating an edge is through the similarity between two sentences. In order to calculate the similarity of such sentences, we used the vector space model based on Tf-Idf weighting and word embeddings for the vector representation of the sentences. Also, we make a distinction between edges linking sentences from different documents (inter-layer) and those connecting sentences from the same document (intra-layer) by using multilayer network models for the Multi-Document Summarization task. In this approach, each network layer represents a document of the document set that will be summarized. In addition to the measurements typically used in complex networks such as node degree, clustering coefficient, shortest paths, etc., the network characterization also is guided by dynamical measurements of complex networks, including symmetry, accessibility and absorption time. The generated summaries were evaluated by using different corpus for both Portuguese and English language. The ROUGE-1 metric was used for the validation of generated summaries. The results suggest that simpler models like Noun and Tf-Idf based networks achieved a better performance in comparison to those models based on word embeddings. Also, excellent results were achieved by using the multilayered representation of documents for MDS. Finally, we concluded that several measurements could be used to improve the characterization of networks for the summarization task.
Devido à grande quantidade de informações textuais disponíveis na Internet, a tarefa de sumarização automática de documentos ganhou importância significativa. A sumarização de documentos tornou-se importante porque seu foco é o desenvolvimento de técnicas destinadas a encontrar conteúdo relevante e conciso em grandes volumes de informação sem alterar seu significado original. O objetivo deste trabalho de Mestrado é usar os conceitos da teoria de grafos para o resumo extrativo de documentos para Sumarização mono-documento (SDS) e Sumarização multi-documento (MDS). Neste trabalho, os documentos são modelados como redes, onde as sentenças são representadas como nós com o objetivo de extrair as sentenças mais relevantes através do uso de algoritmos de ranqueamento. As arestas entre nós são estabelecidas de maneiras diferentes. A primeira abordagem para o cálculo de arestas é baseada no número de substantivos comuns entre duas sentenças (nós da rede). Outra abordagem para criar uma aresta é através da similaridade entre duas sentenças. Para calcular a similaridade de tais sentenças, foi usado o modelo de espaço vetorial baseado na ponderação Tf-Idf e word embeddings para a representação vetorial das sentenças. Além disso, fazemos uma distinção entre as arestas que vinculam sentenças de diferentes documentos (inter-camada) e aquelas que conectam sentenças do mesmo documento (intra-camada) usando modelos de redes multicamada para a tarefa de Sumarização multi-documento. Nesta abordagem, cada camada da rede representa um documento do conjunto de documentos que será resumido. Além das medições tipicamente usadas em redes complexas como grau dos nós, coeficiente de agrupamento, caminhos mais curtos, etc., a caracterização da rede também é guiada por medições dinâmicas de redes complexas, incluindo simetria, acessibilidade e tempo de absorção. Os resumos gerados foram avaliados usando diferentes corpus para Português e Inglês. A métrica ROUGE-1 foi usada para a validação dos resumos gerados. Os resultados sugerem que os modelos mais simples, como redes baseadas em Noun e Tf-Idf, obtiveram um melhor desempenho em comparação com os modelos baseados em word embeddings. Além disso, excelentes resultados foram obtidos usando a representação de redes multicamada de documentos para MDS. Finalmente, concluímos que várias medidas podem ser usadas para melhorar a caracterização de redes para a tarefa de sumarização.

Mathematical modeling of spreading processes have been largely studied in the literature, and its presented a boom in the past few years. This is a fundamental task on the understanding and prediction of real spreading processes on top of a population and are subject to many structural and dynamical constraints. Aiming at a better understanding of this processes, we focused in two task: the modeling and the analysis of both dynamical and structural aspects of these processes. Initially, we proposed a new and general model that unifies epidemic and rumor spreading. Besides, regarding the analysis of these processes, we extended the classical formalism to multilayer networks, in which the theory was lacking. Interestingly, this study opened up new challenges concerning the understanding of multilayer networks. More specifically, regarding their spectral properties. In this thesis, we analyzed such processes on top of single and multilayer networks. Thus, throughout our analysis, we followed three complementary approaches: (i) analytical, (ii) numerical and (iii) simulations, mainly Monte Carlo simulations. Our main results are: (i) a new unifying model, enabling us to model and understand spreading processes on large systems, (ii) characterization of new phenomena on multilayer networks, such as layer-wise localization and the barrier effect and (iii) an spectral analysis of multilayer systems, suggesting a universal parameter and proposing a new analytical tool for its analysis. Our contributions enable further research on modeling of spreading processes, also emphasizing the importance of considering the complete multilayer structure instead of any coarse-graining. Additionally, it can be directly applied on the prediction and modeling real processes. Thus, aside from the theoretical interest and its mathematical implications, it also presents important social impact.
A modelagem matemática dos processos de disseminação tem sido amplamente estudada na literatura, sendo que o seu estudo apresentou um boom nos últimos anos. Esta é uma tarefa fundamental na compreensão e previsão de epidemias reais e propagação de rumores numa população, ademais, estas estão sujeitas a muitas restrições estruturais e dinâmicas. Com o objetivo de entender melhor esses processos, nos concentramos em duas tarefas: a de modelagem e a de análise de aspectos dinâmicos e estruturais. No primeiro, propomos um modelo novo e geral que une a epidemia e propagação de rumores. Também, no que diz respeito à análise desses processos, estendemos o formalismo clássico às redes multicamadas, onde tal teoria era inexistente. Curiosamente, este estudo abriu novos desafios relacionados à compreensão de redes multicamadas, mais especificamente em relação às suas propriedades espectrais. Nessa tese, analisamos esses processos em redes de uma e múltiplas camadas. Ao longo de nossas análises seguimos três abordagens complementares: (i) análises analíticas, (ii) experimentos numéricos e (iii) simulações de Monte Carlo. Assim, nossos principais resultados são: (i) um novo modelo que unifica as dinâmicas de rumor e epidemias, nos permitindo modelar e entender tais processos em grandes sistemas, (ii) caracterização de novos fenômenos em redes multicamadas, como a localização em camadas e o efeito barreira e (iii) uma análise espectral de sistemas multicamadas, sugerindo um parâmetro de escala universal e propondo uma nova ferramenta analítica para sua análise. Nossas contribuições permitem que novas pesquisas sobre modelagem de processos de propagação, enfatizando também a importância de se considerar a estrutura multicamada. Dessa forma, as nossas contribuições podem ser diretamente aplicadas à predição e modelagem de processos reais. Além do interesse teórico e matemático, nosso trabalho também apresenta implicações sociais importantes.

The phenomenon of neural synchronisation, a simultaneous and repeated firing of clusters of neurons, underlies many physiological functions and pathological manifestations in the brain of humans and animals, ranging from information encoding to epileptic seizures. Neural synchronisation, as a general phenomenon, can be approached theoretically in the framework of Dynamical Systems on Networks. In the present work, we do so by considering complex networks of FitzHugh-Nagumo model neurons. In the first part we consider the most understood models where each neuron treats its presynaptic neurons all on an equal footing, normalising signals with its in-degree. We study the stability of the synchronous state by devising an algorithm that destabilises it by selecting and removing links from the network, so to obtain a bipartite network. The selection is performed using a perturbative expression, which can be regarded as a specialisation of a previously introduced Spectral Centrality measure. The algorithm is tested on Erdős-Renyi, Watts-Strogatz and Barabási-Albert networks, and its behaviour is assessed from a dynamical and from a structural point of view. In the second part we consider the less studied case in which each neuron divides equally its output among the postsynaptic neurons, so to reproduce schematically the situation where a fixed quantity of neurotransmitter is subdivided between several efferent neurons. In this context a self-consistent approach is formulated and its limitations are explored. In order to extend its application to larger networks, a Mean Field Approximation is presented. The predictivity of the Mean Field Approach is then tested on the different random network models, and the results are discussed in terms of the original network properties.

Les interactions entre les composants des systèmes complexes font émerger différents types de réseaux. Ces réseaux peuvent jouer le rôle d’un substrat pour des processus dynamiques tels que la diffusion d’informations ou de maladies dans des populations. Les structures de ces réseaux déterminent l’évolution d’un processus dynamique, en particulier son régime transitoire, mais aussi les caractéristiques du régime permanent. Les systèmes complexes réels manifestent des interactions hétérogènes en type et en intensité. Ces systèmes sont représentés comme des réseaux pondérés à plusieurs couches. Dans cette thèse, nous développons une équation maîtresse afin d’intégrer ces hétérogénéités et d’étudier leurs effets sur les processus de diffusion. À l’aide de simulations mettant en jeu des réseaux réels et générés, nous montrons que les dynamiques de diffusion sont liées de manière non triviale à l’hétérogénéité de ces réseaux, en particulier la vitesse de propagation d’une contagion basée sur un effet de seuil. De plus, nous montrons que certaines classes de réseaux sont soumises à des transitions de phase réentrantes fonctions de la taille des “global cascades”. La tendance des réseaux réels à évoluer dans le temps rend difficile la modélisation des processus de diffusion. Nous montrons enfin que la durée de diffusion d’un processus de contagion basé sur un effet de seuil change de manière non-monotone du fait de la présence de “rafales” dans les motifs d’interactions. L’ensemble de ces résultats mettent en lumière les effets de l’hétérogénéité des réseaux vis-à-vis des processus dynamiques y évoluant
Networks arise frequently in the study of complex systems, since interactions among the components of such systems are critical. Net- works can act as a substrate for dynamical process, such as the diffusion of information or disease throughout populations. Network structure can determine the temporal evolution of a dynamical process, including the characteristics of the steady state. The simplest representation of a complex system is an undirected, unweighted, single layer graph. In contrast, real systems exhibit heterogeneity of interaction strength and type. Such systems are frequently represented as weighted multiplex networks, and in this work we in- corporate these heterogeneities into a master equation formalism in order to study their effects on spreading processes. We also carry out simulations on synthetic and empirical networks, and show that spread- ing dynamics, in particular the speed at which contagion spreads via threshold mechanisms, depend non-trivially on these heterogeneities. Further, we show that an important family of networks undergo reentrant phase transitions in the size and frequency of global cascades as a result of these interactions. A challenging feature of real systems is their tendency to evolve over time, since the changing structure of the underlying network is critical to the behaviour of overlying dynamical processes. We show that one aspect of temporality, the observed “burstiness” in interaction patterns, leads to non-monotic changes in the spreading time of threshold driven contagion processes. The above results shed light on the effects of various network heterogeneities, with respect to dynamical processes that evolve on these networks

Mestrado em Engenharia Física
In this thesis we study analytically and numerically the bootstrap percolation process in random uncorrelated directed complex networks. We formulate and analyze the bootstrap percolation process on both unweighted and weighted networks and also study a probability based percolation process. The considered percolation process has an associated activation threshold k where a node only gets active if it has at least k active neighboring nodes. We compare our results with analytical and numerical results obtained for undirected complex networks. We also analyze how topological properties of the directed network components, such as the giant strongly connected component and the periphery, influence on the bootstrap percolation process. We apply our theoretical approach for studying the bootstrap percolation on real complex networks. We show that our theoretical approach developed for the case of random uncorrelated directed networks is in a good agreement with numerical simulations of the bootstrap percolation process on real complex networks which actually are correlated and clustered.
Nesta tese estudamos analiticamente e numericamente o processo de bootstrap percolation em redes complexas direcionadas. Formulamos e analisamos o processo de bootstrap percolation em ambas redes com pesos e sem pesos e também estudamos um processo de bootstrap percolation baseado em probabilidades. O processo de bootstrap percolation considerado tem um parâmetro de ativação associado k onde um nó é ativado se tiver pelo menos k nó vizinhos ativos. Comparamos os nossos resultados com resultados analíticos e numéricos obtidos para redes complexas não direcionadas. Analisamos também como as propriedades topológicas dos componentes das redes complexas direcionadas, como o giant strongly connected component e a periferia, influenciam o processo de bootstrap percolation. Aplicamos a nossa teoria no estudo do processo de bootstrap percolation em redes complexas reais. Mostramos que a nossa teoria desenvolvida para redes complexas aleatórias e não correlacionadas está em bom acordo com simulações numéricas do processo de bootstrap percolation em redes complexas reais que são correlacionas e agrupadas.

The first chapter of this thesis provides an introduction to fundamental concepts concerning econophysics, Ising model, and opinion networks. After a glance in a field of econophysics, Chapter 2 illustrates the economic behaviour via the implementation of two methods. The statistical analysis of real economic data will be briefly stated and followed by the agent-based dynamic model describing the commercial activities. Agent-based dynamic model investigates the intrinsic dynamics of trading behaviour and individual income by modelling transaction processes among agents as a network in the economic system. To take a further look into the network, we introduce a mathematical model of ferromagnetism in statistical mechanics which is called Ising model. Every element in the network can be treated as a two-state ({+1,-1} or sometimes {+1,0}) node. The similar methodology is used in the three-or-more-state situation. This kind of modelling method is widely applied in networks of neurosciences, economics, and social sciences. Chapter 3 implements and modifies Ising model of a random neuron network with two types of neurons: inhibitory and excitatory. We numerically studied two mutually coupled networks through mean-field interactions. After 3-step alternation, the model provides some fascinating insights into the neuronal behavior via simulation. In particular, it determinates factors that lead to emergent phenomena in dynamics of neural networks. On the other hand, it also plays a vital role in building up the opinion network. We first show the development of Ising model to opinion network. Then the coupled opinion network model and some of the analytical results are carefully given in Chapter 4. Two opinion networks are interfering each other in the system. This model can describe the opinion network more precisely and give more accurate predictions of the final state. At last, a case of U.S. presidential campaign in 2016 is studied. To investigate a complex system which is associated with a multi-party election campaign, we have focused on the situation when we have two competing parties. We compare the prediction of the theory with data describing the dynamics of the average opinion of the U.S. population collected on a daily basis by various media sources during the last 500 days before the final Trump-Clinton election. The qualitative outcome is in reasonable agreement with the prediction of our theory. In fact, the analyses of these data made within the paradigm of our theory indicate that even in this campaign there were chaotic elements where the public opinion migrated in an unpredictable chaotic way. The existence of such a phase of social chaos reflects the main feature of the human beings associated with some doubts and uncertainty and especially associated with contrarians which undoubtedly exist in any society. Besides, a modern tool, Twitter, with rapid information spreading speed affects the whole procedure substantially. We also take a closer look at the influence of the usage of Twitter on competitors, Trump and Clinton. Once the first sign from Trump began stirring on Twitter, it quickly began to ferment. Using Twitter not only brings strength to Trump as he wished, but also sending potentially backward to Clinton in this nationwide competition.

Thesis (Ph.D.)--Boston University PLEASE NOTE: Boston University Libraries did not receive an Authorization To Manage form for this thesis or dissertation. It is therefore not openly accessible, though it may be available by request. If you are the author or principal advisor of this work and would like to request open access for it, please contact us at open-help@bu.edu. Thank you.
To design complex networks with optimal transport properties such as flow efficiency, we consider three approaches to understanding transport and percolation in complex networks. We analyze the effects of randomizing the strengths of connections, randomly adding longrange connections to regular lattices, and percolation of spatially constrained networks. Various real-world networks often have links that are differentiated in terms of their strength, intensity, or capacity. We study the distribution P(σ) of the equivalent conductance for Erdös-Rényi (ER) and scale-free (SF) weighted resistor networks with N nodes, for which links are assigned with conductance σi = e^-axi, where xi is a random variable with 0 < xi < 1. We find, both analytically and numerically, that P(σ) for ER networks exhibits two regimes: (i) For σ < e^-apc, P(σ) is independent of N and scales as a power law P(σ) ~ σ^(k)/a-1. Here pc = 1/(k) is the critical percolation threshold of the network and (k) is the average degree of the network. (ii) For σ > e^-apc, P(σ) has strong N dependence and scales as P(σ) ~ f(σ,apc/N^1/3). Transport properties are greatly affected by the topology of networks. We investigate the transport problem in lattices with long-range connections and subject to a cost constraint, seeking design principles for optimal transport networks. Our network is built from a regular d-dimensional lattice to be improved by adding long-range connections with probability Pij ~ rij^-α, where Tij is the lattice distance between site i and j. We introduce a cost constraint on the total length of the additional links and find optimal transport in the system for α = d + 1, established here for d = 1, 2 and 3 for regular lattices and df for fractals. Remarkably, this cost constraint approach remains optimal, regardless of the strategy used for transport, whether based on local or global knowledge of the network structure. To further understand the role that long-range connections play in optimizing the transport of complex systems, we study the percolation of spatially constrained networks. We now consider originally empty lattices embedded in d dimensions by adding long-range connections with the same power law probability p(r) ~ r^-α. We find that, for a ≤ d, the percolation transition belongs to the universality class of percolation in ER networks, while for α > 2d it belongs to the universality class of percolation in regular lattices (for one-dimensional linear chain, there is no percolation transition). However for d < α < 2d, the percolation properties show new intermediate behavior different from ER networks, with critical exponents that depend on α.

This thesis is focused on the study of new techniques of analysis coming from diverse fields (Complex Networks Analysis, Data Mining, and Big Data). Main aim is to better understand systems characterized by a high level of complexity. Markets are the chosen application scenario. In these complex systems, to find the right balance between the forces of demand and supply is very challenging, especially considering that they are characterized by imperfect but massive and fast information. In this context, the thesis presents approaches to face several open questions: how to find the general pattern of shopping behavior, how to mine the product space to find the best product/service that meets the demand, what is the role of the social influence between customers, and so on. The methods and techniques, belonging to the field of Complex Networks Analysis, are complementary to the usual ones of Data Mining. While in Data Mining the purpose is to search patterns and special distributions in a large dataset, here the purpose is to give a focus to the relations between entities of the markets, looking more to the whole system than to the single behavior. The thesis, finally, presents results of experiments performed on real world high quality datasets, providing, in addition to the theoretic results, practical application scenarios.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico
Este dissertaÃÃo foi dividida em duas partes, na primeira parte nÃs propomos um modelo de crescimento competitivo de gregados em redes complexas para simular a propagaÃÃo de idÃias ou opiniÃes em comunidades. Investigamos como as distribuiÃÃes de tamanhos de agregados variam com a topologia de construÃÃo da rede e com o nÃmero de sementes aleatoriamente dispersas na estrutura. Para tal, analisamos redes do tipo de Erdos-RÃnyi, redes de contato preferencial e a chamada rede Apoloniana. Esta Ãltima apresenta distribuiÃÃes de tamanho de agregado em forma de uma lei de potÃncia com um expoente aproximadamente 1. Resultados similares sÃo observados com as distribuiÃÃes obtidas para as fraÃÃes de votos por candidato Ãs eleiÃÃes proporcionais para deputados no Brasil. Na segunda parte, analisamos o comportamento temporal da atividade neural em redes com caracterÃsticas de mundo pequeno e em redes construÃdas segundo o modelo do contato preferencial. Nesta primeira topologia, estudamos como a sÃrie temporal se comporta com a variaÃÃo do alcance das conexÃes. Em ambas as topologias, observamos a formaÃÃo de perÃodos e investigamos como estes variam com o tamanho da rede.
The process by which news trends and ideas propagate in social communities can have a profound impact in the life of individuals. To understand thi process, we introduce a competitive cluster growth model in complex networks. In our model, each cluster represents the set of individuals with a certain opinion or preference. We investigate how the cluster size distribution depends on the topology of the network and how it is affected by the number of initial seeds dispersed in the structure. We study our model using different network models, namely, the Erdos-Renyi geometry, the preferential attachment model, and the so-called Apollonian network. This last complex geometry displays a cluster size distribution that follows a power-law with an exponent 1.0. Similar results have been obtained for the distributions of number of votes per candidate in the proportional elections for federal representation in Brazil. In the second part of this work, we investigate the temporal behavior of neural networks with small world topology and in networks built according to the preferential attachment model. In the first case we study the effect of the range of connections on the behavior of the time series. In both topologies, we detect the existence of cycles and investigate how their periods depend on the size of the system.

Quantum entangled networks represent essential tools for Quantum Communication, i.e. the exchange of Quantum Information between parties. This work consists in the theoretical study of continuous variables (CV) entangled networks - which can be deterministically generated via multimode squeezed light - with complex topology. In particular we investigate CV complex quantum networks properties for quantum communication protocols. We focused on the role played by the topology in the implementation and the optimization of given characteristics of our entangled resource that are useful for a specific quantum communication task, i.e. the creation of an entanglement link between two arbitrary nodes of the resource we are provided with. We implemented an analytical procedure for the generation of entangled complex networks, their optimization and their manipulation via global linear optics operations. We also developed a numerical procedure, based on an evolutionary algorithm, for manipulating entanglement connections via local linear optics operations. Finally, we analyzed the re-shaping of our entangled resource via homodyne measurements.

During the last decades, it has become clear that systems formed by many interacting parts show emergent dynamical properties which are inherently related to the topology of the underlying pattern of connections among the constituent parts. Such systems, usually known as complex systems, are in general suitably described through their networks of contacts, that is, in terms of nodes (representing the system's components) and edges (standing for their interactions), which allows to catch their essential features in a simple and general representation. In recent years, increasing interest on this approach, thanks also to a favorable technological progress, led to the accumulation of an increasing amount of data. This situation has allowed the arising of new questions and, therefore, the diversification of the scientific work. Among them, we can point out three general issues that have been receiving a lot of interest: (i) is the available information always reliable and complete? (ii) how does a complex interaction pattern affect the emergence of collective behavior in complex systems? And (iii) which is the role of mobility within the framework of complex networks? This thesis has been developed along these three lines, which are strictly interrelated. We expand on three case-studies, each one of which deals with two the above mentioned macro-issues. We consider the issue of the incompleteness of the available information both in the case of natural (Chapter 2) and artificial (Chapter 3) networks. As a paradigmatic emergent behavior, we focus on the synchronization of coupled phase oscillators (Chapter 2 and Chapter 4), deeply investigating how different patterns of connections can affect the achievement of a globally coherent state. Finally, we include moving agents in two different frameworks, using them as explorers of unknown networks (Chapter 3) and considering them as interacting units able to establish connections with their neighbors (Chapter 4). In Chapter 2, we study the problem of the reconstruction of an unknown interaction network, whose nodes are Kuramoto oscillators. Our aim is to extract topological features of the connectivity pattern from purely dynamical measures, based on the fact that in a heterogeneous network the global dynamics is not only affected by the distribution of the natural frequencies but also by the location of the different values. The gathered topological information ranges from local features, such as the single node connectivity, to the hierarchical structure of functional clusters, and even to the entire adjacency matrix. In Chapter 4, instead, we present a model of integrate and fire oscillators that are moving agents, freely displacing on a plane. The phase of the oscillators evolves linearly in time and when it reaches a threshold value they fire at their neighbors. In this way, the interaction network is a dynamical object by itself since it is re-created at each time step by the motion of the units. Depending on the velocity of the motion, the average number of neighbors, the coupling strength and the size of the agents population, we identify different regimes. Moving agents are employed also in Chapter 3 where they play the role of explorers of unknown artificial networks, having the mission to recover information about their structures. We propose a model in which random walkers with previously assigned home nodes navigate through the network during a fixed amount of time. We consider that the exploration is successful if the walker gets the information gathered back home, otherwise, no data is retrieved. We show that there is an optimal solution to this problem in terms of the average information retrieved and the degree of the home nodes and design an adaptive strategy based on the behavior of the random walker.
Durante las últimas décadas, se ha empezado a poner de manifiesto que sistemas formados por muchos elementos en interacción pueden mostrar propiedades dinámicas emergentes relacionadas con la topología del patrón de conexiones entre las partes constituyentes. Estos sistemas, generalmente conocidos como sistemas complejos, en muchos casos pueden ser descritos a través de sus redes de contactos, es decir, en términos de nodos (que representan los componentes del sistema) y de enlaces (sus interacciones). De esta manera es posible capturar sus características esenciales en una representación simple y general. En esta última década, el creciente interés en este enfoque, gracias también a un progreso tecnológico favorable, ha llevado a la acumulación de una cantidad ingente de datos. Eso, a su vez, ha permitido el surgimiento de nuevas preguntas y, por lo tanto, la diversificación de la actividad científica. Entre ellas, podemos destacar tres cuestiones generales que son objeto de mucho interés: (i) ¿la información disponible es siempre fiable y completa? (ii) ¿cómo un patrón de interacción complejo puede afectar el surgimiento de comportamientos colectivos? Y (iii) ¿cual es el papel de la movilidad en el marco de las redes complejas? Esta tesis se ha desarrollado siguiendo estas tres líneas, que están íntimamente relacionadas entre sí. Hemos profundizado en tres casos de estudio, cada uno de los cuales se ocupa de dos de los macro-temas mencionados. Consideramos la cuestión del carácter incompleto de la información disponible tanto en el caso de redes naturales (Capítulo 2) como de redes artificiales (Capítulo 3). Nos centramos en la sincronización de los osciladores de fase acoplados (Capítulos 2 y 4) en cuanto comportamiento emergente paradigmático, investigando en profundidad cómo los diferentes patrones de conexión puedan afectar la consecución de un estado coherente a nivel global. Por último, analizamos el rol de la movilidad incluyendo agentes móviles en dos marcos diferentes. En un caso, los utilizamos como exploradores de redes desconocidas (Capítulo 3), mientras que en otro los consideramos como unidades que interaccionan y son capaces de establecer conexiones con sus vecinos (Capítulo 4).

Communication via air routes is an important issue in a world organized around a web-like city network. In this context, the robustness of network infrastructures, e.g. air transport networks, are a central issue in transport geography. Disruption of communication links by intentional causes (e.g., terrorist attack on an airport) or unintentional (e.g., weather inclemency) could be a serious drawback for countries, regions and airlines. Policymakers and the management of airlines and alliances should be able to reduce the effects of such interruptions in order to ensure good communication through air transport (i.e., maximize the robustness of their network at a reasonable cost). The literature review of the study of air transport route networks through an analysis of complex networks has highlighted a lack of contributions to the study of the topology and the robustness of such networks, which contrasts with advances undertaken for other transport networks or communication systems. The literatura survey suggests areas in which research should be undertaken, based on the existing literature in other areas and from three different perspectives: global route networks, airline alliances and airlines. The aim of this research is to develop a better understanding of air traffic and, in particular, to be able to assess the potential damage of any airport being inoperative for a continent, country or airline.

Network science has significantly advanced in the last decade, providing insights into the underlying structure and dynamics of complex networks. Critical infrastructures such as telecommunication networks play a pivotal role in ensuring the smooth functioning of modern day living. These networks have to constantly deal with failures of their components. In multiple failure scenarios, where traditional protection and restoration schemes are not suitable because of the quantity of resources that would be required, the concept of robustness is used in order to quantify just how good a network is under such a large-scale failure scenario. The aim of this thesis is to, firstly, investigate the current challenges that might lead to multiple failure scenarios of present day networks and, secondly, to propose novel metrics able to quantify the network robustness.
La ciència de les xarxes (o network science) ha avançat significativament en l'última dècada, proporcionant coneixement sobre l'estructura subjacent i la dinàmica de les xarxes complexes (o complex networks). Infraestructures crítiques com xarxes de telecomunicacions, juguen un paper fonamental per garantir el bon funcionament de la vida moderna. Aquestes xarxes han de lidiar constantment amb fallades dels seus components. En escenaris de fallades múltiples, on els esquemes de protecció i restauració tradicionals no són adequats degut a la gran quantitat de recursos que serien necessaris, el concepte de robustesa (o robustness) s'utilitza per tal de quantificar com de bona és una xarxa quan es produeix una fallada a gran escala. L'objectiu d'aquesta tesi és, en primer lloc, investigar les amenaces actuals de les xarxes d'avui en dia que poden portar a escenaris de fallades múltiples i, en segon lloc, proposar nous indicadors capaços de quantificar la robustesa d'aquestes xarxes.

A shuman beings, we are continuously struggling to comprehend the mechanism of dierent natural systems. Many times, we face a complex system where the emergent properties of the system at a global level can not be explained by a simple aggregation of the system's components at the micro-level. To better understand the macroscopic system eects, we try to model microscopic events and their interactions. In order to do so, we rely on specialized tools to connect local mechanisms with global phenomena. One such tool is network theory. Networks provide a powerful way of modeling and analyzing complex systems based on interacting elements. The interaction pattern links the elements of the system together and provides a structure that controls how information permeates throughout the system. For example, the passing of information about job opportunities in a society depends on how social ties are organized. The interaction pattern, therefore, often is essential for reconstructing and understanding the global-scale properties of the system. In this thesis, I describe tools and models of network theory that we use and develop to analyze the organization of social or transportation systems. More specifically, we explore complex networks by asking two general questions: First, which mechanistic theoretical models can better explain network formation or spreading processes on networks? And second, what are the signi cant functional units of real networks? For modeling, for example, we introduce a simple agent-based model that considers interacting agents in dynamic networks that in the quest for information generate groups. With the model, we found that the network and the agents' perception are interchangeable; the global network structure and the local information pathways are so entangled that one can be recovered from the other one. For investigating signi cant functional units of a system, we detect, model, and analyze signi cant communities of the network. Previously introduced methods of significance analysis suer from oversimpli ed sampling schemes. We have remedied their shortcomings by proposing two dierent approaches: rst by introducing link prediction and second by using more data when they are available. With link prediction, we can detect statistically signi cant communities in large sparse networks. We test this method on real networks, the sparse network of the European Court of Justice case law, for example, to detect signi cant and insigni cant areas of law. In the presence of large data, on the other hand, we can investigate how underlying assumptions of each method aect the results of the signi cance analysis. We used this approach to investigate dierent methods for detecting signi cant communities of time-evolving networks. We found that, when we highlight and summarize important structural changes in a network, the methods that maintain more dependencies in signi cance analysis can predict structural changes earlier. In summary, we have tried to model the systems with as simple rules as possible to better understand the global properties of the system. We always found that maintaing information about the network structure is essential for explaining important phenomena on the global scale. We conclude that the interaction pattern between interconnected units, the network, is crucial for understanding the global behavior of complex systems because it keeps the system integrated. And remember, everything is connected, albeit not always directly.

In cells, complex networks of interacting biomolecules process both environmental and endogenous signals to control gene expression and other cellular processes. This poses a challenge to researchers who attempt to develop mathematical and computational models of biochemical networks that reflect this complexity. In this thesis, I propose methods that help manage complexity by exploiting the finding that, as for other biological systems, cellular networks are characterized by a modularity that appears at all levels of organization.The first part of this work focuses on the modular properties of proteins and how their function can be characterized through their structure and allosteric properties. I develop a modular rule-based framework and formal modelling language that describes the computations performed by allosteric proteins and that is rooted in biophysical principles. Rule-based modelling conventionally addresses the problem of combinatorial complexity, whereby protein interactions can generate a combinatorial explosion of protein complex states. However, I explore how these same interactions can potentially require a combinatorial number of parameters to describe them. I demonstrate that my rule-based framework effectively addresses this problem of regulatory complexity, and describes allosteric proteins and networks in a unified, consistent, and modular fashion. I use the framework in three applications. First, I show that allostery can make macromolecular assembly more efficacious when a protein that joins two separable parts of a complex is present in excessively high concentrations. Second, I demonstrate that I can straightforwardly analyze the complex cooperative interactions that arise when competitive ligands bind to a multimeric protein. Third, I analyze a new model of G protein-coupled receptor signalling and demonstrate that it explains the functional selectivity of these receptors while being parsimonious in the number of parameters used. Overall, I find that my rule-based modelling framework, implemented as the Allosteric Network Compiler software tool, can ease of modelling and analysis of complex allosteric interactions.If cellular networks are modular, this implies that small sub-systems can be studied in isolation, provided that external inputs and perturbations to the system can be modelled appropriately. However, cellular networks are subject to both intrinsic noise, which is endogenous to the system, but also extrinsic noise, arising from noisy inputs. Furthermore, many inputs may be dynamic, whether due to experimental protocols or perhaps reflecting the cyclic process of cell division. This motivates my development, in the second part of this work, of efficient stochastic simulation algorithms for biochemical networks that can accommodate time-varying biochemical parameters. Starting from Gillespie's well-known First Reaction Method and Gibson and Bruck's Next Reaction Method, I develop two new algorithms that allow time-varying inputs of arbitrary functional form while scaling well to systems comprising many biochemical reactions. I analyze their scaling properties and find that a modified First Reaction Method may scale better than a modified Next Reaction Method in some applications.The third and last part of this thesis introduces a new software tool, Facile, that eases the creation, update and simulation of biochemical network models. Models created through a simple and intuitive textual language are automatically converted into a form usable by downstream tools, for example ordinary differential equations for simulation by Matlab. Also, Facile conveniently accommodates mathematical and time-varying expressions in rate laws.
Au niveau cellulaire, des réseaux complexes d'interaction biomoléculaire traitent les signaux tant environnementaux qu'endogènes dans le but de contrôler l'expression génétique ainsi que d'autres processus cellulaires. Ceci est un défi pour les chercheurs qui veulent concevoir des modèles mathématiques et calculatoires des réseaux biochimiques. Dans cette thèse, je propose des méthodes qui facilitent la gestion de cette complexité en exploitant la constatation que, tout comme d'autres systèmes biologiques, les réseaux cellulaires se caractérisent par une modularité qui transparaît à tous les niveaux d'organisation.Dans la première partie, je mets l'accent sur les propriétés modulaires des protéines et sur la façon de caractériser leur fonction, compte tenu de leur structure et de leurs propriétés allostériques. J'ai mis au point un cadre modulaire à base de règles ainsi qu'un langage formel de modélisation qui permet de décrire les calculs effectués par les protéines allostériques et qui découle de principes biophysiques. La modélisation à base de règles s'adresse conventionnellement au problème de la complexité combinatoire, où les interactions entre les protéines peuvent générer une explosion combinatoire d'états des complexes protéiques. J'examine, cependant, comment il peut s'avérer nécessaire d'utiliser un nombre combinatoire de paramètres pour décrire ces mêmes interactions. Je démontre que notre cadre à base de règles peut régler efficacement ce problème de la complexité régulatoire, et permet de décrire les protéines et les réseaux allostériques de façon unifiée, cohérente et modulaire. J'utilise le cadre développé dans trois applications. Tout d'abord, je montre que l'allostérie peut rendre l'assemblage macromoléculaire plus efficace lorsqu'une protéine qui unit deux parties distinctes d'un complexe protéique est présente en concentration excessive. Deuxièmement, je démontre qu'il est relativement simple d'analyser les interactions coopératives complexes qui surviennent lorsque des ligands compétitifs se lient à une protéine multimérique. En troisième lieu, j'analyse un nouveau modèle de la signalisation des récepteurs couplés aux protéines G qui explique leur sélectivité fonctionnelle tout en limitant le nombre des paramètres utilisés. Globalement, je montre que ce cadre basé sur des règles, qui est implémenté dans le logiciel ‘Allosteric Network Compiler', peut faciliter la modélisation et l'analyse d'interactions allostériques complexes.Si les réseaux cellulaires sont modulaires, il en résulte que des sous-systèmes peuvent être étudiés séparément, à la condition que les entrées et les perturbations externes du système puissent être modélisées adéquatement. Cependant, ces réseaux sont soumis à l'influence du bruit intrinsèque, qui est endogène au système, mais également au bruit extrinsèque, venant des entrées bruyantes. De plus, de nombreuses entrées peuvent être dynamiques. Cela motive, dans la deuxième partie de ce travail, le développement d'algorithmes efficients de simulation stochastique pour les réseaux biochimiques qui peuvent tenir compte de paramètres biochimiques dynamiques. En me fondant sur la méthode maintenant célèbre de Gillespie, d'appellation ‘First Reaction Method', et sur celle de Gibson et Bruck, la ‘Next Reaction Method', j'ai développé deux nouveaux algorithmes qui permettent des entrées dynamiques de forme fonctionnelle arbitraire tout en s'échelonnant bien sur les systèmes qui comportent de nombreuses réactions biochimiques. J'analyse leurs propriétés d'échelonnement et je constate que, pour certaines applications, la ‘First Reaction Method' modifiée s'échelonne mieux que la ‘Next Reaction Method' modifiée.La troisième et dernière partie cette thèse est la présentation d'un nouvel outil informatique, Facile, qui simplifie la création, la mise à jour et la simulation de modèles de réseaux biochimiques.

It has been observed that real-world random networks like the WWW, Internet, social networks, citation networks, etc., organize themselves into closely-knit groups that are locally dense and globally sparse. These closely-knit groups are termed communities. Nodes within a community are similar in some aspect. For example in a WWW network, communities might consist of web pages that share similar contents. Mining these communities facilitates better understanding of their evolution and topology, and is of great theoretical and commercial significance. Community related research has focused on two main problems: community discovery and community identification. Community discovery is the problem of extracting all the communities in a given network, whereas community identification is the problem of identifying the community, to which, a given set of nodes belong. We make a comparative study of various existing community-discovery algorithms. We then propose a new algorithm based on bibliographic metrics, which addresses the drawbacks in existing approaches. Bibliographic metrics are used to study similarities between publications in a citation network. Our algorithm classifies nodes in the network based on the similarity of their neighborhoods. One of the drawbacks of the current community-discovery algorithms is their computational complexity. These algorithms do not scale up to the enormous size of the real-world networks. We propose a hash-table-based technique that helps us compute the bibliometric similarity between nodes in O(m ?) time. Here m is the number of edges in the graph and ?, the largest degree. Next, we investigate different centrality metrics. Centrality metrics are used to portray the importance of a node in the network. We propose an algorithm that utilizes centrality metrics of the nodes to compute the importance of the edges in the network. Removal of the edges in ascending order of their importance breaks the network into components, each of which represent a community. We compare the performance of the algorithm on synthetic networks with a known community structure using several centrality metrics. Performance was measured as the percentage of nodes that were correctly classified. As an illustration, we model the ucf.edu domain as a web graph and analyze the changes in its properties like densification power law, edge density, degree distribution, diameter, etc., over a five-year period. Our results show super-linear growth in the number of edges with time. We observe (and explain) that despite the increase in average degree of the nodes, the edge density decreases with time.
Ph.D.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Science