|Home | About | Journals | Submit | Contact Us | Français|
We present a model of adaptive regulatory networks consisting of a simple biologically motivated rewiring procedure coupled to an elementary stability criterion. The resulting networks exhibit a characteristic stationary heavy-tailed degree distribution, show complex structural microdynamics, and self-organize to a dynamically critical state. We show analytically that the observed criticality results from the formation and breaking of transient feedback loops during the adaptive process.
Much recent research attention has focused on understanding the structure of naturally occurring empirical networks and associated random graph models . An overarching aim of many of these studies is to determine the relationships between network structure and dynamics. For instance, modularity and sparsity have long been known to contribute to global stability, while feedback is a well-studied prerequisite for the support of complex dynamics such as oscillations, multistability, and chaos . However, although much work has, so far, focused on networks which are static in their topology, many real-world complex systems evolve both structurally and dynamically over time . For instance, neural networks change in structure depending on synaptic activity while genetic regulatory networks change structurally on the evolutionary time scale in a fitness-dependent manner. Consequently, adaptive networks—in which changes in network topology and dynamics continually feedback on each other—are now attracting increasing research interest . Since many biological regulatory systems, such as neural and genetic regulatory networks, are also thought to optimally balance stability and adaptability by operating at, or near to, criticality , a number of prior studies have sought to elucidate mechanisms of self-organized criticality (SOC) in adaptive networks . For example, important early results were obtained by Christensen et al. and Bornholdt and Rohlf, who showed that adaptive networks may self-organize to a critical state by a simple mechanism in which “quiet nodes grow links [and] active nodes lose links” . However, despite the apparent ubiquity of critical adaptive networks in nature, the mechanisms of adaptive SOC remain to be fully determined.
In this Letter we outline a simple new adaptive network model which reproduces characteristic features of biological systems, including a heavy-tailed degree distribution and self-organization to a dynamically critical state. To fix ideas our model may be thought of as describing adaptive changes in a genetic regulatory network, although it may also be applied to other systems which undergo adaptive rewiring. In genetic regulatory networks, genetic mutations cause changes in protein structure which, in turn, not only alter local network connectivity but also global system stability. Consequently, our model is a simple scheme intended to describe, albeit in an idealized way, mutation-driven local rewiring in the face of a global stability (fitness) constraint: mutations are allowed to accumulate during times of stability, but harmful mutations are suppressed during times of instability.
Mathematically, a network is a graph consisting of a set of vertices (of size n) and a set of edges E. A directed graph (digraph) is a graph in which each edge υi ~ υj E has a unique orientation (υi → υj). Although digraphs describe well structural relationships in complex systems, in many cases relationships also have an intrinsic sign. To cope with such systems, a natural framework is that of signed digraphs. A signed digraph is a digraph in which each edge υi ~ υj E additionally has a unique sign σij [−1, +1] depending on whether it is “activating” (σij = +1) or “inhibiting” (σij = −1). The adjacency matrix A = aij of a signed digraph has the form aij = σij if υi ~ υj E and aij = 0 otherwise. When considering structural features of without regard for signs we shall also use the absolute adjacency matrix Ã = |aij|. The in-degree (out-degree) of a vertex is the number of incoming (outgoing) edges it has, without regard for sign. The net degree dnet(υi) = |din(υi) − dout(υi)| of a vertex υi is the absolute difference of its incoming and outgoing degree. Intuitively, net degree measures how “sourcelike” or “sinklike” a vertex is. By extension, we define the imbalance of a vertex pair as the absolute difference of their net degrees, I(υi, υυ) = |dnet(υi) − dnet(υj)|. It has recently been observed that many empirical networks contain significantly more source and sink vertices than expected by chance, and that this degree imbalance naturally leads to depletion of feedback loops which, in turn, confers enhanced stability properties . Thus, degree imbalance and dynamic stability are intrinsically related, a fact that our model exploits.
We begin at t = 0 with a random signed digraph (t = 0) with Erdős-Rényi connectivity, in which edge orientations and signs have been assigned independently in an equiprobable random manner . We then rewire (t) at successive time steps according to the following rules. (1) Randomly and uniformly choose an edge eold = υa ~ υb connecting two vertices in (t) such that (t) − eold is not disconnected and an ordered pair of nonadjacent vertices υc, υd ≠ υc. (2) Calculate the pair-wise imbalances I(υa, υb) and I(υc, υd). (3) Delete eold and create a new edge enew = υc → υd, choosing its sign randomly and uniformly, and recalculate the imbalances. (4) If the sum of the two imbalances after the switch is greater than that before then accept the switch unconditionally, otherwise accept with probability ρ(t).
In order to couple structural rearrangement to dynamics we allow ρ(t) to vary in a manner which takes into account the changing stability of the system. To do so we assume that, in addition to regulatory links defined by (t), each species (vertex υi) also decays at a constant characteristic rate εi which we fix at t = 0 independently, randomly, and uniformly on the unit interval. Thus, at each evolutionary time point we obtain a modified adjacency matrix B(t) = A(t) − diag(εi). Global stability is then given by the magnitude of μmax(t) = max Re μi(t), where μi(t) for i = 1,…, n are the eigenvalues of B(t). In particular, the system is stable when μmax(t) < 0 and unstable when μmax(t) > 0 . Therefore, we set ρ(t) = 1 − h[μmax(t)], where h[x] is the Heaviside step function, allowing defective switches when the system is stable and suppressing defective switches when the system is unstable. The key property of this coupling is that it makes global information available to the local structural reorganizing process, providing continual feedback between structure and dynamics.
The networks produced by this simple model are characterized by a stationary heavy-tailed degree distribution (see Fig. 1, left) indicating the presence of hub source and sink vertices, a well-known feature of real-world networks [8,11]. However, since our model allows for periods of random structural rearrangement, this macroscopic stationarity masks complex structural microdynamics in which individual vertices continually accumulate and lose edges (see Fig. 1, right). This kind of “mixing” microdynamics is not produced by classical rich-get-richer models of hub formation , but has recently been highlighted as an important characteristic of real-world evolving networks .
Figure 2 gives a plot of μmax(t) at equilibrium  for a representative system showing that dynamics on the evolutionary time scale are characterized by periods of stability [μmax(t) < 0] and instability [μmax(t) > 0] punctuating back and forth. To help interpret these dynamics, also shown is λmax(t) = max Re λi(t), where λi(t) are the eigenvalues of the graph adjacency matrix A(t) and three measures of network structure. The first structural measure shown is total net degree Dnet(t) = Σidnet[υi(t)], a measure of overall degree imbalance in (t). It is apparent that changes in total net degree correlate poorly with changes in stability, suggesting that although fluctuations in net degree are observed during the evolutionary process, it is not degree imbalance per se that drives the characteristic dynamics of μmax(t). In order to identify more precisely the structural origin of the observed bursting dynamics, and based upon the observation that degree imbalance naturally leads to feedback loop depletion , also shown are two measures of network cyclic structure . The first, Φ(t) = ncyc(t)/n where ncyc(t) is the number of vertices which participate in a cycle in (t), measures overall cyclic structure without regard for details such as cycle numbers or distribution of cycle lengths. The second,
where i are the eigenvalues of the absolute adjacency matrix Ã(t), is an indirect measure of “returnability,” which takes into account details of closed walks in (t). In particular, Ψ(t) is a sum of all closed walks in (t) weighted in decreasing order by length [note that Ψ(t) + n may be thought of as the partition function of (t)] .
Examining the time series of Ψ(t) and Φ(t) it is apparent that, unlike total net degree, both Ψ(t) and Φ(t) exhibit similar bursting behavior to that of μmax(t). In particular, periods of stability [μmax(t) < 0] generally correspond to periods when both Ψ(t) = 0 and Φ(t) = 0 (in Fig. 2 this occurs >90% of the time). Since Ψ(t) = 0 and Φ(t) = 0 if and only if (t) is acyclic, this indicates that periods of stability occur primarily when (t) is acyclic. Furthermore, changes in stability predominantly occur concordantly with changes in Ψ(t) and Φ(t) (for instance, in Figs. 2 and and33 this occurs >99% of the time). Considering the time series as binary variables (“stable or unstable” and “cyclic or acyclic”) and calculating entropies gives H[Φ(t)] = H[Ψ(t)] = 0.093 and H[μmax(t)] = 0.100. The mutual information between these series is M[μmax(t), Φ(t)] = M[μmax(t), Ψ(t)] = 0.088, indicating that changes in stability are strongly related to changes in cyclic structure .
In order to better understand this relationship, we now derive some analytical results relating cycles and spectra of signed digraphs which will help interpret these numerics. To obtain exact results we shall focus on deriving analytic formulas for Ψ and λmax in the particular case that all cycles in are disjoint (that is, each vertex υ V; belongs to at most one cycle). Although this is a strong condition to impose, and most real-world networks are not expected to be cycle-disjoint, this case is analytically tractable and, since our evolutionary scheme favors the minimization of cycles, yields results which shed light on the observed dynamics. Full proofs of all analytic results are provided in the supplementary materials .
First we observe that if a signed digraph is cycle-disjoint, then its spectrum has a particularly simple form. Specifically, if contains positive cycles and negative cycles of length k (for k = 3,…, n)  and all cycles are disjoint, then its spectrum is the zero eigenvalue with multiplicity (n − ncyc), along with the eigenvalues of each of the cycles considered separately as induced subgraphs (that is, the union of copies of the kth roots of +1, and copies of the kth roots of −1, for k = 3,…, n). An immediate consequence of this result is that if is cycle-disjoint and possesses at least one positive cycle then λmax = 1, while if all cycles are negative then λmax = Reeπi/l = cos(π/l), where l is the length of the longest cycle in . Examination of the time-series data shows that λmax(t) = 0, 1 and cos(π/l) for some 3 ≤ l ≤ n + do indeed occur commonly during evolution (for instance, in Fig. 2 this occurs ≈ 53% of the time), indicating the continual formation and breaking of isolated cycles by the evolutionary scheme.
This result is also useful since it allows us to calculate Ψ analytically in the case that is cycle-disjoint. In particular, if contains disjoint cycles of length k for k = 3,…, n then, using Eq. (1),
where Hk,0(z) is the generalized hyperbolic function of order k and kind 0 . Figure 3 shows that values of Ψ(t) calculated using Eq. (2) often occur during evolution, again indicating that isolated cycles are continually formed and broken by the evolutionary scheme.
These analytical results may be used to interpret numerics by making use of two further results which relate λmax to μmax in the cycle-disjoint case. First, note that in the special case that (t) is acyclic, λmax(t) = 0 and μmax(t) = − minεi < 0, and the system is stable. Second, if (t) is cycle-disjoint then μmax(t) < λmax(t) and this bound is tight [μmax(t) → λmax(t) as εi → 0 for all i]. Consequently, if vertex decay rates are all small then the completion of a single cycle in an otherwise acyclic network is sufficient to trigger a burst of instability, as seen in Fig. 2. When this occurs the evolutionary process responds by suppressing any further defective switches and rearranging local network structure to remove the cause of the instability. Typically, this is quickly achieved and the burst of instability is relatively short. However, occasionally cycles may accumulate more rapidly than they are removed, giving rise to extended bursts of instability and heavy-tailed statistics characteristic of a critical state (see Fig. 4).
For completeness it should be noted that if (t) is not cycle-disjoint then the relationship between cycles and stability can be complex: it is not necessarily true that μmax(t) < λmax(t) and, in rare cases, changes in cyclic structure and stability may occur discordantly. Further details are included in the supplementary materials .
Many biological regulatory systems are thought to balance stability and adaptability by self-organizing to a dynamically critical state . In this Letter we have presented a simple adaptive network model which reproduces characteristic features of biological systems, including a heavy-tailed connectivity distribution, microdynamics, and robust self-organization to criticality. Previous models have shown that adaptive networks may self-organize to a critical state due to rewiring based upon local activity [6,7]. Here, the mechanism of self-organization is somewhat different and relies on the fact that feedback and stability are generally inversely related: by employing a flexible rewiring scheme which allows feedback loops to be formed during periods of stability and eliminated during periods of instability, criticality naturally arises in our model. It seems plausible that these (and other, as yet unknown) adaptive processes may be responsible for the criticality observed in nature.
PACS numbers: 89.75.Fb, 02.10.Ox, 05.65.+b, 89.75.Hc