Complex technological networks : structure, dynamics and algorithms

Abstract

Networks are all around us; from the simplest forms of life to the complexity of our brain. Also ourselves are part of many networks from the social interaction that we engage or as a result of biochemical interactions inside a single cell. They have demonstrated to be present not only in social or biological contexts but also in technological systems. The major example is the Internet, maybe the biggest technological network. Other examples include highways, transportation systems, power generation and distribution. Thus, the study of the characteristics of the networks is of primary importance for the advance of sciences. In the last decade a new way of thinking about networks arose. Thanks to the availability of huge amounts of digital data, computational power and the quickness in communications a different kind of networks has been analyzed. Such networks are defined as Complex Networks. The aim of this work is to analyze, model and control dynamical systems through complex networks theory. We propose a series of dynamical models on large graphs to represent complex and non linear dynamics. We mainly focus on theoretical models that, at a high level of abstraction, are representations of real world technological and social systems. We focus four different types of dynamics on complex network ranging from social interactions modelled with a game theory approach to epidemic spreading. In the first part of the work we concentrate on the structure and robustness of complex networks and its application to real world problems as sensor networks design. We propose a distributed algorithm for the creation of resilient sensor networks topologies against both random failures and attacks. Numerical evidence show that generated topologies outperform classical random geometric graph structure. Next, we study the emergence of cooperative behavior in a mobile agents environment. We consider a two dimensional plane in which agents can moverandomly and interact with neighbors in their visibility radius. We model social interactions as an evolutionary version of the prisoner’s dilemma and analyze the conditions under which cooperation is an evolutionary stable strategy. Our analysis highlight that, although defection is favoured, there exists a consistent range of parameters space in which cooperation becomes advantageous. Such conditions are fulfilled when agents density is enough to produce small clusters in which cooperation can grow and players velocity is small enough to assure clusters stability for a reasonable amount of time. In the second part we have face a couple of interesting problems on top of communication networks: the study of fluctuations in mean flows in a traffic network and an optimization technique for congestion control. Regarding the first issue we present a model based on random walks theory that incorporates most of the characteristics of real communication systems such as network structure and fluctuations in external systems arrivals. Solving the model a direct relation between flows fluctuations and three factors appears, they are namely: the variations in the number of packets in the network, the degree of the nodes and the length of the time window in which measurements are performed. The second problem is faced introducing a simple traffic model that incorporate some simple traffic control strategies. We show that some simple adaptive strategies can considerably slow down the onset of congestion, but modifying the nature of the transition between free flow regime and the congested state from a smooth to an abrupt one. Then, introducing an empathetic optimization strategy we obtain a delay on the onset of congestion and a smooth transition between the two regimes. On the last part of the work we address a class of spreading processes on networks. Our study start with a simple analytical formulation to model the spreading of a disease in a class of interaction rules. We propose an alternative formulation to the classical heterogeneous mean field to study a SIS model on scale free networks. The model can be integrated numerically and we analytically derive its equivalence with the HMF by recovering the epidemic threshold. In addiction to the HMF the proposed approach permits to predict the single nodes infection probability and can be applied to an entire class of interaction models ranging from contact process to a fully reactive scenario like the HMF. Then, we move on the modeling of a more complex scenario in which interactions are described by traffic flows. In this model packets are seen as quanta of interaction between individuals and as the way the disease can spread in the population. The analytical treatment of the model via an HMF approach show that the epidemic threshold strictly depends on the traffic values of the system and, in case of a bounded delivery rate, it canassume a finite value also for very high traffic intensities. We conclude our analysis with a fully developed metapopulation system in which the impact of human responses to the epidemic spreading is considered. In the first response individuals are allowed to cancel their journey with a probability proportional to the fraction of infected individuals at the destination. In the second we permit them to take a longer but less infected path to the destination. Numerical analysis showed an unexpected result. Although cancelling a journey can only slightly reduce the epidemic incidence a longer but safer path can have a dramatic outcome bringing the disease in places that otherwise will be untouched and raising consistently the epidemic incidence.