Session H54: Focus Session: Complex and co-evolving networks - Dynamics on Networks

Robustness and Assortativity for Diffusion-like Processes in Scale- free Networks

By analyzing the diffusive dynamics of epidemics and of distress in complex networks, we study the effect of the assortativity on the robustness of the networks. We first determine by spectral analysis the thresholds above which epidemics/failures can spread; we then calculate the slowest diffusional times. Our results shows that disassortative networks exhibit a higher epidemiological threshold and are therefore easier to immunize, while in assortative networks there is a longer time for intervention before epidemic/failure spreads. Moreover, we study by computer simulations a diffusive model of distress propagation (financial contagion). We show that, while assortative networks are more prone to the propagation of epidemic/failures, degree-targeted immunization policies increases their resilience to systemic risk.   

Time scales and dynamical processes in activity driven networks

Network science has undergone explosive growth in the last ten years. This growth has been driven by the recent availability of huge digital databases, which has facilitated the analysis and construction of large-scale networks from real data and the identification of statistical regularities and structural principles common to many systems. Network modeling has played an essential role in this endeavor; however models are chiefly constructed by considering as relevant ingredients only the connectivity and statistical properties of the networks, while disregarding the actual agents' behavior. Here we address this challenge by measuring the agents' interaction activity in real-world networks and defining a minimal model capable of reproducing the intrinsically additive nature of connectivity patterns obtained from time-aggregated network representations. Additionally, we demonstrate that processes such as epidemic and information spreading in highly dynamical networks can be better characterized in terms of agent social activity than by connectivity based approaches   

Network growth dynamics of fire ant ({\em Solenopsis invicta}) nests

We study the construction dynamics and topology of fire ant ({\em Solenopsis invicta}) nests. Fire ants in colonies of hundreds to hundreds of thousands create subterranean tunnel networks through the excavation of soil. We observed the construction of nests in a laboratory experiment. Workers were isolated from focal colony and placed in a quasi 2D, vertically oriented arena with wetted soil. We monitored nest growth using time-lapse photography. We found that nests grew linearly in time through tunnel lengthening and branching. Tunnel path length followed an extended power law distribution, $P ~ (l - l_0)^\beta$. Average degree of tunnel nodes was $k = 2.17 \pm 0.40$ and networks were cyclical. In simulation we model the nest growth as a branching and annihilating levy-flight process. We study this as a function of dimensionality (2D and 3D space considered) and step length distribution function $P(l_s)$. We find that in two-dimensions path length distribution is exponential, independent of the functional form of $P(l_s)$ consistent with a poisson spatial process while in three-dimensions $P(l) = P(l_s)$. Comparing simulation and experiment we attribute the slower than exponential tail of $P(l)$ in experiment as a result of a behavioral component to the ant digging program.   

The Impact of Time Delays in Network Synchronization in a Noisy Environment

Coordinating, distributing, and balancing resources in networks is a complex task and it is very sensitive to time delays. To understand and manage the collective response in these coupled interacting systems, one must understand the interplay of stochastic effects, network connections, and time delays. In synchronization and coordination problems in coupled interacting systems individual units attempt to adjust their local state variables (e.g., pace, orientation, load) in a decentralized fashion. They interact or communicate only with their local neighbors in the network, often with explicit or implicit intention to improve global performance. Applications of the corresponding models range from physics, biology, computer science to control theory. I will discuss the effects of nonzero time delays in stochastic synchronization problems with linear couplings in an arbitrary network. Further, by constructing the scaling theory of the underlying fluctuations, we establish the absolute limit of synchronization efficiency in a noisy environment with uniform time delays, i.e., the minimum attainable value of the width of the synchronization landscape.\footnote{D. Hunt, G. Korniss, and B.K. Szymanski, Phys. Rev. Lett. 105, 068701 (2010).} These results have also strong implications for optimization and trade-offs in network synchronization with delays.   

Predicting the origin of contagion processes on complex, multi-scale networks

Contagion phenomena in space often exhibit complex, multiscale spatio-temporal patterns driven by the interaction of non-local dispersal and nonlinear dynamics. A key challenge is the prediction of dynamic patterns based on information on human interactions, mobility and initial conditions. The development of computational models has thus received considerable attention. However, in many realistic situations, a process has already evolved for some period before detection and identifying the spatial origin is difficult. Surprisingly, this ``inverse problem'' has received little attention in the past. We show in a paradigmatic model for human disease dynamics that despite the spatial complexity of dynamic patterns, the origin of outbreak can be predicted with high fidelity. Based on the technique of shortest path trees in strongly heterogeneous, multi-scale human mobility networks we show that at any point in time the spatial origin can be reconstructed reliably. This novel perspective on complex spatio-temporal dynamics can be applied to systems beyond human disease dynamics for instance the reconstruction of neolithic diffusion of agriculture into Europe and related migration driven historic phenomena.   

Influence and structural balance in social networks

Models on structural balance have been studied in the past with links being categorized as friendly or antagonistic [Ref- T. Antal et al., Phys. Rev. E 72, 036121 (2005)]. However no connection between the nature of the links and states of the nodes they connect has been made. We introduce a model which combines the dynamics of the structural balance with spread of social influence. In this model, every node is in one of the three possible states (e.g. leftist, centrist and rightist) [Ref- F. Vazquez, S. Redner, J. Phys A, 37 (2004) 8479-8494] where links between leftists and rightists are antagonistic while all other links are friendly. The evolution of the system is governed by the rules of structural balance and opinion spread takes place as a result of structural balance process. The dynamics can lead the system to a number of fixed points (absorbing states). We study how the initial density of centrists $n_{c}$ affects the dynamics and probabilities of ending up in different absorbing states. We also study the scaling behavior of the expected time to converge to one of the absorbing states as a function of the initial density of centrists and under some variations of our basic model.   

Majority-vote model on a dynamic small-world square lattice

Majority-vote models are often used to study consensus building, coarsening dynamics, and phase transitions, among other phenomena. In addition to the microscope rules governing a particular model, it is well known that the relevant properties of each system depend crucially on the underlying lattice structure. Here we investigate a majority-vote with noise model on a square lattice with dynamic small-world rewiring via Monte Carlo simulation and finite size scaling analyses. We construct the order-disorder phase diagram and find the critical exponents associated with the continuous phase transition. We compare our results to those obtained from two-dimensional static small-world networks, as well as the isotropic lattice and mean-field limiting cases.   

Underlying mechanisms for commuting and migration processes

Both frequent commuting and long-term migration are complex human processes that strongly depend on socio-demographic, spatial, political, and even economic factors. We can describe both processes using weighted networks, in which nodes represent geographic locations and link weights denote the flux of individuals who commute (or migrate) between locations. Although both processes concern the movements of individuals, they are very different: commuting takes place on a daily (or weekly) basis and always between the same two locations, while migration is a rare, one-way displacement. Despite these differences, a recently proposed stochastic model, the Radiation model, provides evidence that both processes may be successfully described by the same underlying mechanism. For example, quantities of interest for either process, such as the distributions of trip length and destination populations, appear remarkably similar to the model's predictions. We explore the similarities and differences between commuting and migration both empirically, using census data for the United States, and theoretically, by comparing these commuting and migration networks to the predictions given by the Radiation model.   

A quantitative measure for organization of complex and co-evolving networks

To define evolution and self-organization in complex networks a quantitative measure for organization is necessary. Two systems should be numerically distinguishable by their degree of organization and their rate of self-organization. Here we apply as a measure for quantity of organization the inverse of the average sum of physical actions of all elements in a system per unit motion multiplied by the Planck's constant. The meaning of quantity of organization here is the number of quanta of action per one unit motion of an element. For example, a unit motion for electrons on a computer chip is the one necessary for one computation. This definition can be applied to the organization in any complex system. Systems self-organize to decrease the average action per element per unit motion in them. This is the attractor for a dynamical, nonlinear system evolving in time. Constraints increase this average action, so constraint minimization is a basic mechanism for action minimization. Increase of quantity of elements in the network, leads to faster constraint minimization through grouping, decrease of average action per element and motion and therefore faster self-organization and evolution.   

Identification of Interventions to Control Network Crises

Large-scale crises in financial, social, infrastructure, genetic and ecological networks often result from the spread of disturbances that in isolation would only cause limited damage. Here we present a method to identify and schedule interventions that can mitigate cascading failures in general complex networks. When applied to competition networks, our method shows that the system can often be rescued from global failures through actions that satisfy restrictive constraints typical of real-world conditions. However, under such constraints, interventions that can rescue the system from a propagating cascade exist over specific periods of time that do not always include the early postperturbation period, suggesting that scheduling is critical in the control of network cascades.   

Effect of degree correlations on controlability of complex networks

While significant effort was made during the past decade to understanding the structure, evolution and function of complex networks, little is known about our ability to control them. A system is considered controllable if by imposing appropriate external signals on a set of its nodes, called driver nodes, the system can be driven from any initial state to any desired final state in finite time. The controllability of a network can be quantified by calculating the minimal number of driver nodes needed to obtain complete control. We study the effect of degree correlations on network controllability via both numerical simulations and analytical calculations. Numerical simulations are preformed by systematically adding correlations to model networks using appropriate rewiring schemes inspired by simulated annealing. Analytical results are derived using the cavity method originally developed in spin glass theory. The numerical and analytical results enable us to give qualitative predictions of controllability for any networks based on their degree correlation profiles. We test our predictions on several real networks and find consistent results.   

Control Capacity in Complex Networks

By combining tools from control theory and network science, an efficient methodology was proposed to identify the minimum sets of driver nodes, whose time-dependent control can guide the whole network to any desired final state. Yet, this minimum driver set (MDS) is usually not unique, but one can often achieve multiple potential control configurations with the same number of driver nodes. Given that some nodes may appear in some MDSs but not in other, a crucial question remain unanswered: what is the role of individual node in controlling a complex system? We first classify a node as critical, redundant, or ordinary if it appears in all, no, or some MDSs. Then we introduce the concept of control capacity as a measure of the frequency that a node is in the MDSs, which quantifies the importance of a given node in maintaining Controllability. To avoid impractical enumeration of all MDSs, we propose an algorithm that uniformly samples the MDS. We use it to explore the control capacity of nodes in complex networks and study how it is related to other characteristics of the network topology.   

Controlling Complex Networks with Compensatory Perturbations

The response of complex networks to perturbations is of critical importance in areas as diverse as ecosystem management, power system design, and cell reprogramming. These systems have the property that localized perturbations can propagate through the network, causing the system as a whole to change behavior and possibly collapse. We will show how this same mechanism can actually be exploited to prevent such failures and, more generally, control a network's behavior. This strategy is based on counteracting a deleterious perturbation through the judicious application of additional, compensatory perturbations---a prospect recently demonstrated heuristically in metabolic and food-web networks. Here, we introduce a method to identify such compensatory perturbations in general complex networks, under arbitrary constraints that restrict the interventions one can actually implement in real systems. Our method accounts for the full nonlinear time evolution of real complex networks, and in fact capitalizes on this behavior to bring the system to a desired target state even when this state is not directly accessible. Altogether, these results provide a new framework for the rescue, control, and reprogramming of complex networks in various domains.