# Evolving Networks with Enhanced Stability Properties

Authors: David Newth; Jeff Ash
Journal: Research Letters in Physics
 (2008)

---

## Abstract

We use a search algorithm to identify networks with enhanced linear
stability properties in this account. We then analyze these networks for
topological regularities that explain the source of their stability/instability.
Analysis of the structure of networks with enhanced stability properties
reveals that these networks are characterized by a highly skewed degree
distribution, very short path-length between nodes, little or no clustering,
and dissasortativity. By contrast, networks with enhanced instability
properties have a peaked degree distribution with a small variance, long
path-lengths between nodes, a high degree of clustering, and high assortativity.
We then test the topological stability of these networks and discover
that networks with enhanced stability properties are highly robust to the
random removal of nodes, but highly fragile to targeted attacks, while networks
with enhanced instability properties are robust to targeted attacks.
These network features have implications for the physical and biological
networks that surround us.


---

## Body

## 1. Introduction

Our  modern
society has come to depend on large-scale infrastructure networks to deliver
resources to our homes and businesses in an efficient manner. Critical
infrastructure is continually confronted with small perturbations, most of
which have no effect on the network's performance. However, a small fraction of
these disturbances propagates through the network, crippling its performance.
Over the past decade, there have been numerous examples where a local
disturbance has lead to the global failure of critical infrastructure. For
instance, on August 14, 2003, a string of events starting in Ohio triggered the
largest blackout in North American history [1]. Where a network is carrying a flow of some types
(electricity, gas, data packets, information, etc.), a “node” carries a load,
and under normal circumstances this load does not exceed the capacity of that
node. Nodes also have the ability to mediate the behavior of the network in
response to a perturbation (such as the failure of a neighboring node or a
sudden local increase in flow). The resilience of a system to the propagation
of disturbances is directly related to the structure of the underlying network.
In previous work [2]
we have examined the topological properties of networks that make them
resilient to cascading failures. In this account, we use a search algorithm to
help us identify network properties that lead to enhanced linear stability
properties. We also show that networks that display enhanced linear stability
properties are highly resilient to the random loss of nodes. By contrast
networks with enhanced instability properties tend to be more resilient to the
loss of key nodes.


## 2. Stability Analysis of Complex Networks

Many of the complex systems that surround us—from
food webs to critical infrastructure—are large, complex, and grossly
nonlinear in their dynamics. Typically, models of these systems are inspired by
equations similar to(1)dXidt=Fi(X1(t),X2(t),…,Xn(t)),where Fi is an empirically inspired, nonlinear function
of the effect of the ith system element on the dynamics of the other n elements. When modeling ecological systems,
for instance, the function Fi takes on the form of the Lotka-Volterra
equations [3]. Of
particular interest is the steady state of the system, in which all growth
rates are zero, giving the fixed point or steady-state values for each of the
state variables Xi*.
This occurs when(2)0=Fi(X1*(t),X2*(t),…,Xn*(t)). The local
dynamics and stability in the neighborhood of the fixed point can be determined
by expanding (1) in a Taylor series about the steady state:(3)dXi(t)dt=Fi|*+∑j=1n[∂Fi∂Xj|*xj(t)+12∑k=1n[∂2Fi∂Xj∂Xk|*xj(t)xk(t)+⋯, where xi(t)=Xi(t)−Xi* and * denotes the steady state. Since Fi|*=0,
and close to the steady state, the xi values are small, all terms that are second
order and higher need not be considered in determining the stability of the
system. This gives a linearized approximation that can be expressed in matrix
form as(4)dx(t)dt=Ax(t),where x(t) is an n×1 column vector of the deviations from the
steady state. As May [4] demonstrates, determining the eigenvalues for A reveals the stability properties of the
system. Specifically the real parts of the eigenvalues can be ordered |λ1|<|λ2|<⋯<|λn−1|<|λmax|,
and we will refer to λmax as the dominant eigenvalue. If λmax<0,
then the system is said to be stable to perturbations in the region of the
fixed point. In this account, we use a rewiring scheme to create networks with
enhanced stability properties (i.e., min[λmax]), and networks that have enhanced instability
properties (i.e., max[λmax]).


## 3. Evolving Networks

We make use of a stochastic rewiring scheme to create
networks with the desired stability properties. This rewiring scheme is similar
to those used in previous studies [2, 5], and the effectiveness of this algorithm at finding networks
with enhanced stability properties is given in [5]. The rewiring scheme
consists of three steps: (1) an edge is selected and one end of the edge is
reassigned to another node; (2) the dominant eigenvalue (λmax′) is calculated for the modified network; and
(3) if λmax′ is superior to λmax,
then the edge rewiring is accepted, else it is rejected. These three steps are
repeated for 105 time steps. The rewiring scheme is initially
seeded with an Erdös-Rényi random graph [6] consisting of 100 nodes and 150 edges. The edges are
set to a value of 1, but this can be easily modified to take on real values,
and the on-diagonal or self-regulating terms are set to −1.  At every step, the
network is checked to ensure it consists of a single-connected component.
Figure 1 provides two example networks resulting from the maximization and
minimization of λmax.
The structure of the network is then examined for common statistical properties
including scale-free degree distribution [7], short path-length and high clustering [8], and assortativeness [9].Comparison of networks with enhanced stability
properties (a), and enhanced instability properties (b).
(a)(b)


## 4. Structural Properties of Stable and Unstable Networks

For each experiment, 200 runs were made and the final
networks collated and analyzed. To determine how “unique” these evolved
networks are, we compare their structural characteristics to those of two
random null models. The first is an Erdös-Rényi random graph, and is used to
determine which characteristics can be accounted for by random structures. The
second null model is the degree randomization model as described in [10]. This model randomizes node
connection (i.e., which node is connected to which other node), but preserves
the individual node degree characteristics. Comparison between the evolved
networks and the two null models shows those properties that are unique to the
evolved networks and can be accounted for by random occurrences, and those that
are a consequence of the degree distribution.Figure2 shows the comparison between the evolved
networks with enhanced stability properties and the two null models. In all
cases, the comparisons are drawn from statistics taken from 1000 null models.
Figures 2(a) and 2(b) show the variation in the average shortest path-length
and diameter. In both cases these characteristics are not significantly
different from the degree randomized model. This indicates that these
characteristics are directly related to degree distribution. Figure 2(c)
compares the clustering between the three models. The evolved networks
essentially have no clustering, unlike the two null models, suggesting that the
lack of clustering is a unique characteristic of the evolved networks. Finally
Figure 2(d) shows the evolved networks to be highly disassortative. The degree
of disassortativity displayed by the evolved networks is similar to the level
of disassortativity found in the degree randomized model, indicating that the
disassortativity is a consequence of the degree distribution. In short, the
degree distribution accounts for the path-length characteristics and
assortativity in the evolved networks, while the degree of clustering is a
unique property of the evolved networks.Comparison between the evolved networks with enhanced
stability properties and the two random null models: (a) average shortest path
length; (b) diameter; (c) clustering coefficient; and (d) assortativeness.
(a)(b)(c)(d)Figure3 shows a comparison between networks with
enhanced instability properties and the two null models. Figures 3(a), 3(b),
and 3(c) show that the average shortest path-length, diameter, and clustering
are significantly larger than those found in the two null models, suggesting
that these characteristics are unique to the evolved class of networks.
Combined, these characteristics indicate that these networks have the so-called
“long-world” properties. Finally, these networks are assortative (Figure
3(d)), but it should be noted that the spread of these distributions is wide.
The analysis suggests that the evolved networks are somewhat “unique” in
their wiring which gives them topological properties which are not solely
accounted for by the degree distribution.Comparison between the evolved networks with enhanced
instability properties and the two random null models. (a) Average shortest
path-length; (b) diameter; (c) clustering coefficient; and (d)
assortativeness.
(a)(b)(c)(d)Studies of many real-world networks have identified
skewed degree distributions—particularly those whose distributions decay as
a power-law—as a key characteristic [7]. Figure 4 shows the degree distribution for the
networks with enhanced stability and instability properties compared to an
Erdös-Rényi random graph. The degree distribution for networks with enhanced
stability is heavily skewed. Despite the short tail (due to finite size
effects), there is a significant fraction of nodes with large degrees. By
contrast, the degree distribution for networks with enhanced instability is
quite peaked, with a narrower variance than an Erdös-Rényi random graph.
This suggests that networks with enhanced
instability have a degree of regularity about the way links
are distributed throughout the network.Degree distributions. (a) Degree distribution for
networks with enhanced stability properties; (b) Degree distribution for
networks with enhanced instability properties.
(a)(b)


## 5. Resilience to Topological Attack

Now, we
examine the topological stability [11] of the evolved networks. By topological stability, we
mean how these networks break apart when nodes are removed from the network.
Here, we consider two node removal schemes: (1) random node removal; and (2)
degree centrality node removal. Under the random node removal scheme, nodes are
removed from the network without bias. Under the degree centrality node removal
scheme, nodes are removed based on their degree. After a node is removed from
the network, the centrality of each node is recalculated. If two nodes have the
same centrality score, the node selected to be removed from the network is
chosen at random. To test topological stability of the evolved networks, we
took 200 optimized networks from both optimization schemes and subjected each
network to the aforementioned attack regimes. This was repeated 100 times for
each network, to allow for adequate selection between tied centrality measures.
As nodes were removed, we kept track of size of the largest connected component 〈s〉.From Figure5, we can see how the network's largest
connected component 〈s〉 breaks-up as nodes are removed in accordance
with the attack schemes. The most striking observation here is that networks
with enhanced stability properties are highly fragile to targeted node removal,
yet are highly resilient to random node removal. By optimizing for dynamic
stability, topological stability to random attack is gained at no cost. By
contrast, networks with enhanced instability properties are less resilient to
random node removal than networks with enhanced stability properties, but these
networks are more resilient to targeted node removal.  The networks described here appear to have the same degree sequence as those studied in [12–15]. However, it is not clear if those networks posses the stability properties of the networks described here. Our networks have a very specific set of topological properties that are not accounted for by the degree distribution alone (see Section   4).Decay of networks as nodes are randomly and targetedly
removed from the network. Solid lines are networks with enhanced stability
properties, and dashed lines are networks with enhanced instability properties.
(a)(b)


## 6. Discussion

In this paper,  we have employed the use of a search
algorithm to identify network characteristics that seem to be associated with
enhanced linear stability and instability properties. Figure1 shows that the
optimized networks display a degree of structural regularity in their
arrangement. Networks with enhanced stability properties take on a star-like
structure. While finite size effects make it difficult to determine the exact
role and configuration of hubs that make these networks more stable, we
postulate that the hubs allow perturbations to be distributed and reabsorbed
quickly. We also make the following general observations about the networks
with enhanced stability properties. Networks with enhanced stability properties
(i) have very low clustering and almost no cycles, (ii) have a highly skewed
degree distribution and the degree distribution accounts for many of the
observed network characteristics, (iii) have short paths between any two nodes,
a small diameter, and are highly disassortative, and (iv) are highly resilient
to random attack, but highly sensitive to targeted attack. It is tempting to
suggest that when a network is optimizing for stability, topological stability
to random failure is obtained as a no-cost bonus.By contrast we make quite different observations about
the networks with enhanced instability properties. They (i) have an interlocked
loop structure, (ii) have a peaked degree distribution, and the degree
distribution is not the sole source of the structural properties observed
within these networks, (iii) tend to have longer average shortest path-lengths,
larger diameter, higher clustering, and tend to be more assortative than random
null models, and (iv) are resilient to both random and targeted attacks.In this paper, we have shown that the ability of small
initial shocks to cascade to the extent that large systems are affected or
disrupted is directly linked to the way the underlying system elements are
connected [4].
Understanding the way a network is structured provides great insights into the
dynamical properties demonstrated by that network [16, 17]. Many biological, social,
and large-scale infrastructure networks display a surprising degree of
similarity in their overall organization. For example, the frequency with which
we observe scale-free networks in the real world may be explained by their
demonstrated topological and dynamical stability. However, while these systems
may look structurally similar, the origins of their similarity may be quite
different. Biological networks, for example, exploit homeostasis provided by
certain network properties, while technological networks arrive at the same
properties as the result of a trade-off between communication efficiency and
link cost [18]. From
the simple system dynamics studied here, we suggest that large complex networks
can be designed to be robust to perturbations, if simple structural design
rules are followed.



---

*Source: 195873-2008-11-30.xml*