Monday 28 March 2016

Extinction and Cascading failures: Prediction of resilience in complex network systems


1. Real world complex networks:

(a) Supply chain networks

With globalization and the development of technology for cost efficient operation of supply chains, supply chains are evolving and becoming complex networks.  These networks connect suppliers to consumers, whose daily life depends on these supply chains which distribute goods and services, such as fuel, electricity, water, and food items. Any disruption in network may have impact on only one or few nodes, but its impact may propagate further other connected nodes. It is important to assess the impact of the events as the disruptions could lead to catastrophic disasters. Prediction models, which assess the impact, have to consider with enormous complexity of the networks.

(b) Financial networks

Financial networks represent lending decisions of the banks and the resulting relations between different banks and agencies. In today’s world, financial network is highly fragile because the adverse effects of on one of the node would impact on all the nodes in the networks as each one of them inter connected each other, and would lead financial crisis. How do we predict impact of actions/decisions of the bank leading to catastrophic events in such complex network system?

(c) Ecological networks

Eco systems are dynamic and changing. External forces like climate change and pollution have huge impact on how ecosystems adapt, in some cases many species would extinct. Darwin used the metaphor of a ‘tangled bank’ to describe the complex interactions between species, hinting that complexity of these interactions is impossible to understand. With advances in complex network theory, attempts are made to represent ecosystems as complex networks where each node can be described as plant, species, or whole population of one kind, and each link is weighted depending on their interaction in that system.

2. Resiliency of the complex network system

2.1 What is it?

Consider a tiny ecosystem in Australia, consisting of ants and plants. Plant species is guarded by the ant from the insects, and the plant in return offers food and shelter to the ants. As shown in the following picture, each ant species can visit multiple plant species, and each plant species offers shelters for multiple ant species. By considering interactions between just two entities, network already became complex.




Fig: (a). Interaction between each ant species (left column) with different tree species (Right column). (b) Connection between plant species if both plant species offer shelter to the same kind of ant species.

In this ecological network, each plant species is treated as node where size of the node represents abundance of the species in that network, and each link represents common kind of ant species visitors. The high abundance of one tree species (ability to shelter large number of ant species) would help to more ants, and so these ants would help more number of tree species. In this way, each tree is helping one another.


Fig (2): Network representation: Plants as nodes (Size refers to abundance), and Link refers to both plants are visited by same kind of Ant species (Link strength depending on number of common ants species)

This network would adapt to the changes in the networks depending on number of links between species, strength of the links, and size of the nodes. Let us see how network dynamics change as we remove ant species one by one randomly. As more kind of ant species disappear, some plant species would disappear and abundance levels of those remaining plant species would decrease as shown in the following picture. 

 (a)         

(b)



(c)                                                                                                      


(d)                                                                                                                  

Fig 3. From (a) to (d): Dynamics of networks as ant kinds disappear randomly from the network. After certain stage, population of plant species suddenly disappears from the ecosystem. Scale at the bottom refers to randomly removed ant species from the network at each step

There is key point where remaining population suddenly crashes. Network can no longer compensate for the further changes, and would lead to irreversible change on the ecosystem. How to predict those triggering points, and ability of existing complex systems to compensate for the changes before these networks collapse?

Resilience is network property, and it can be defined as ability of the network to adapt its activity and interactions so that it retains functionality without any significant impact on its nodes or agents of the network.

Following sections describes mathematical formulation for prediction of resilience of the network. Resilience could be measure population of the species in the ecological network, continuation of supply chain network in case of unwanted event, power supply connectivity in power grid.

2.2 Single node one dimensional system


Although analysis of network resilience helps in understanding consequences of the events on human health, world economy, operations and services, and ecological systems, events leading loss of resilience are rarely predicted in advance. 
Let us consider simple one node system. The traditional mathematical treatment of resilience approximates the behavior of a complex system with non-linear equation:


β – Parameters that captures changing environmental conditions (example: Temperature, rain fall)

x - refers to resilience function possible states the possible states of the system depending on β (example: plant population)

f - refers function defining the system dynamics (like governing laws that describe market conditions, plant species growth)

 Solution for resilience function x(β), which represents can be solved by using following equations:

Equation 2 provides the systems steady state condition at x0 . Equation 3 ensures its linear stability. X vs β are plotted in following graph: In the following plots, blue line refers preferred state where as red line refers to undesired state. (For example, undesired state in ecological system is extinction of the node)


 Fig (4): All three plots represent three different possible cases how resilience function varies with β . (a) Tunable parameter, which captures changes in the environment, reaches critical point the possible states for x are two or more. Blue (desirable state) exists for β > βc.   (blue) and two (or more) stable fixed points, a desired (blue) and an undesired (red) forβ < βc   . (b) Possible state for X is only red below for β < βc   (c) Resilience function with a stable solution for β < βc and no solution above βc, resulting in an uncontrolled divergent or chaotic behavior
Limitation with 1D non-linear network: Although it is powerful conceptually, complex network system is controlled by large number of variables. Resiliency function which refers to possible states should be defined by non linear equations that capture the interaction between various nodes of the complex network system. The resulting resilience function is therefore required to solve equations in multidimensional manifold over the complex parameter space.

2.3 Multi-node multi dimensional system


Consider system consisting of N components, and each component activity is explained as the vector:



First term: Self dynamics of each component at the state, Xi

Second term: Interaction between component I and its interacting partners

G(xi, xj): Dynamical laws that govern systems components/nodes (Factors that influence changes in the network like global warming, financial market conditions, metabolism)
Matrix Aij: Interaction between nodes/Link weights

In multi dimensional system, resilience function is dependent on N x N parameters of the weighted network Aij , each referring to changes in the network.

Example for multi dimensional formulation: (plants species and pollinators interaction)

To understand above formulation, consider a example where xi(t) refers to  the abundance  of species i, and equation(4) is written as follows: 


The first term: The incoming migration of I at a rate Bi from neighboring ecosystems.(Positive growth)

2nd term: Logistic growth with the system carrying capacity Ki, and the Allee effect, according to which for low abundance (xi < Ci) the system features negative growth

3rd term: Mutual interactions. (Plant-pollinator where such interaction helps in growth of the plant species to certain extent depending on the state of xi and xj)

In this example, we can study randomly removing fraction of nodes (deleting plant species from the network), or we can remove fraction of pollinators (removing some of the pollinators from the network) or change the weights of Aij  to mimic the global environmental changes. 

Limitations in multi-dimensional model: 

When the changes in the network exceeds a certain threshold, a bifurcation occurs and results in two stable fixed points: the desired  state  and an undesired low-abundance state (catastrophic event). Under these conditions the system loses its resilience, potentially transitioning to the undesired state. The precise bifurcation point marking this loss of resilience is, however, highly unpredictable. Limitation of our ability to predict the network resilience could be due to transition depends on the network topology, the form, and the nature of perturbation applied.

 2.4 Single universal resilience function


Authors in the paper suggest single universal resilience function to overcome ability predict precise bifurcation point where complex network system loses its resilience.
The hypothesis behind this formulation is,

In a network environment, the state of each node is affected by the state of its immediate neighbors. Therefore, the effective state of the system can be characterized using the average nearest-neighbor activity.

where   is the vector of outgoing weighted degrees
 is the vector of incoming weighted degrees,
  ,   is the average weighted degree, and 1 is the unit vector 1 = (1,…,1)T. 
where
averages over the product of the outgoing and incoming degrees of all nodes. This reduction maps the multi-dimensional complex system (4) into an effective 1D equation of the form of equation (1), where
Mapping of equation (4) to the 1D equation (7) allows taking advantage of the theoretical tools developed for low-dimensional systems and applying them to a broad range of complex systems.
In summary of the resilience pattern of complex network systems is very difficult to predict in manifold multi dimensional space (x, Aij). If the system is mapped into β-space as explained above, it is possible to predict the system’s response to diverse changes in the network and correctly identify the point where system loses its resilience.
3. References:

2. Video on Network Earth  http://www.mamartino.com/index.html





No comments:

Post a Comment