Network Robustness

• The breakdown of a complex network is not gradual. Removing a small number of nodes only has a limited impact on integrity, but once a fraction of removed nodes reaches a critical threshold, the network abruptly breaks into disconnected components.
  • Random node failures induce a phase transition from a connected to disconnected network.
  • Percolation Theory is applicable mostly for random and regular networks

Random Networks §

• Let be the fraction of nodes that were removed in an inverse percolation process.

  For sufficiently large , we break the giant component in the network. In this sense, we can use an inverse percolation process to understand the robustness of a network.

• As it turns out, the fragmentation of the network is not gradual, but characterized by a threshold function determined by coefficient .

  If , then the giant component persists. However, once , the giant component vanishes.

  This is illustrated by the dependence on of the order parameter

  In fact, we can analyze using the same critical exponents for the order parameter, correlation length and average cluster size This can be done by setting .

Scale Free Networks §

• Following an inverse percolation process during a breakdown, scale-free networks tend to have their largest component decrease in size gradually, vanishing in the vicinity of

• This implies that scale-free networks have an unusual robustness to random node failures, which is different from the collapse of random networks (see above).

• Intuitively, the robustness of a Scale Free Network against random attacks comes from the fact that many nodes are of small-degree, and these do not impact the overall connectivity of the network.

• By the Molloy-Reed Criterion of Scale Free Networks, the critical threshold only depends on the average degree and the second moment of the degree distribution.

• This helps us understand the source of the robustness of scale-free networks.

  • If the degree exponent , we have that the second moment diverges as .

    Inserting this yields that

    Which is what is observed empirically.

  • We can extend by expressing and in terms of the degree exponent and the minimum and maximum degree

  • Because real networks tend to bee finite, we can introduce the relation based on the fact that scale free networks have large hubs.

    This gives a new threshold of

    This indicates that larger networks have thresholds close to the theoretical limit of

Enhanced Robustness §

• A network displays enhanced robustness if the breakdown threshold deviates from the breakdown threshold of a random network . That is

  In other words, it has enhanced robustness if the network performs better than a randomly wired network.

• This has the following implications

  • Because for most networks where deviates from , robustness as predicted by the Molloy-Reed criterion
  • The degree distribution of a network does not need to follow a strict power law to display enhanced robustness. The only requirement is be bigger than a random network of similar size.
  • The critical exponents are dependent on
  • Enhanced robustness is not limited to node removal, but emerges from link removal as well.

Cascading Failures §

• Models have been made to capture the dynamics of cascading effects. They share three ingredients.
  • The system is characterized by some flow over the network
  • Each component has a local breakdown that determines when it contributes to a cascade
  • Each system has a mechanism to redistribute the traffic to other nodes on a cascade

Failure Propagation §

• The Failure Propagation Model is a model for cascading failures in a network.

• In this we consider a network with an arbitrary degree distribution where each node contains an agent that

  • Has some state (active or inactive). Agents are initialized as active.
  • Is characterized by a breakdown threshold

• We proceed as follows

  • At time , set one agent to “inactive”.
  • At subsequent time steps, randomly pick an agent and update its state following a threshold rule:
    • If the selected agent is active, check its neighborhood.
      • If at least of the neighbors are inactive, then this agent becomes inactive too.
      • Otherwise, it remains active.
    • If the agent was inactive, it remains inactive.

• Empirical simulations show a phase transition within the model based on

  • Subcritical Region - If , cascades terminate quickly since changes in one node are unlikely to perturb other nodes and their sizes follow an exponential distribution.
  • Critical Region - If , the size of the cascades follow a power law distribution. Some cascades are large and some are small
  • Supercritical Region - If , the cascades can continue indefinitely, so all cascades are global and the network can experience major breakdowns

Branching Model §

• This builds on the observation that cascading failures follow a tree-like process.

• It is a simpler variation of the failure propagation model that works as follows

  • Start with a single active node
  • In the next time step, each active node produces offspring.
    • If the node selects , it will die out
    • If the node selects , it will have new active sites.

• We can use the branching model to solve for the size of the cascades empirically.

• For scale-free networks, it depends on degree exponent .

  Let denote the exponent of the cascade distribution. We have

  The fact that this exponent is only dependent on the degree exponent suggests that the phenomenon of cascades is universal.

• The critical regions in the branching model largely follow that of the failure propagation model.

  • Subcritical Region - If , cascades terminate quickly since changes in one node are unlikely to perturb other nodes and their sizes follow an exponential distribution.
  • Critical Region - If , the size of the cascades follow a power law distribution. Some cascades are large and some are small
  • Supercritical Region - If , the cascades can continue indefinitely, so all cascades are global and the network can experience major breakdowns

Designing Robust Networks §

Designing for Failure §

• In order to make a network more robust, we need to maximize its breakdown threshold .

• One way to do this is to maximize the average degree, but this also requires us to increase the overall “cost” of the network.

• We can increase robustness without changing the cost of the network.

  • By the Molloy-Reed criterion, if we wish to do this for a fixed , we should maximize .
  • The degree distribution that does this, based on empirical simulations, is a bimodal distribution where the two modes are and .

• If we wish to optimize the topology against both random failures and attacks we should maximize

  By analysis and empirical simulations, this is best achieved with the bimodal distribution

  The maximum is obtained when so that there is only one node that has (i.e., there is a hub and spoke topology topology).

  The obtained network is robust even under targeted attacks since each of the nodes with degree are connected to each other.

Intervention §

• Another approach to build robustness is to make policies for cascading failures.

• One way to do this is through more links, however in practice this is infeasible since failures can happen much quicker.

• However, another way to do this is through selective link and node removal.

  Simulations indicate that removal should happen right after the initial failure but before it can propagate.
  Also, remove nodes with small loads and links with large excess loads in the vicinity of the initial failure.

Links §

• Barabasi

• Fundamental Constructs of Network Science

• Chegeer’s Inequality - another measure of robustness.