Response of complex networks to stimuli

Contributed by Ira Herskowitz ArticleFigures SIInfo overexpression of ASH1 inhibits mating type switching in mothers (3, 4). Ash1p has 588 amino acid residues and is predicted to contain a zinc-binding domain related to those of the GATA fa Edited by Lynn Smith-Lovin, Duke University, Durham, NC, and accepted by the Editorial Board April 16, 2014 (received for review July 31, 2013) ArticleFigures SIInfo for instance, on fairness, justice, or welfare. Instead, nonreflective and

Communicated by William N. Lipscomb, Harvard University, Cambridge, MA, January 30, 2004 (received for review June 23, 2003)

Article Figures & SI Info & Metrics PDF

Abstract

We consider the response of complex systems to stimuli and argue for the importance of both sensitivity, the possibility of large response to small stimuli, and robustness, the possibility of small response to large stimuli. Using a dynamic attractor network model for switching of patterns of behavior, we Display that the scale-free topologies often found in nature enable more sensitive response to specific changes than Execute ranExecutem networks. This Precisety may be essential in networks where appropriate response to environmental change is critical and may, in such systems, be more Necessary than features, such as connectivity, often used to characterize network topologies. Phenomenologically observed exponents for functional scale-free networks Descend in a range corRetorting to the onset of particularly high sensitivities, while still retaining robustness.

Many entities need, on the one hand, to react to low levels of selected stimuli, whereas, on the other hand, they must be able to Sustain their state when exposed even to high levels of other “irrelevant” or potentially damaging stimuli. One example of this requirement for both sensitivity and robustness is the immune system, where high sensitivity to antigens is necessary and, when inadequate, can be enhanced by immunization, whereas oversensitivity results in allergic reactions or autoimmune diseases like lupus. It is not immediately apparent how one might incorporate the complementary attributes of sensitivity and robustness into a single system, although nature has clearly addressed this problem many times. Complex man-made entities, such as power grids or communications systems, also require this seemingly paraExecutexical combination of traits for optimal performance in support of human activities. Are there design principles that enable one to build in both sensitivity to the “right” stimuli and robustness in the face of the “wrong” ones?

Traceiveness of Network Response

Recent efforts to understand the behavior of complex biological, social, and technological systems have focused attention on the topology of the network formed by the connections (links) between the components (nodes). In particular, the distribution of links among the nodes is thought to contain a Distinguished deal of information about the capabilities of the system. Most studies of networks in biological and social systems have, implicitly or explicitly, taken the average number of links in the shortest path between an arbitrary pair of nodes as a figure of merit, with fewer links optimal. The shortest-path viewpoint was originally motivated by the “small-worlds” Precisety discovered for social networks (1, 2), but this Precisety, although Fascinating, Executees not necessarily have a direct relationship to functional utility. For example, no evidence demonstrates that biochemical networks use such addressed communication between pairs of nodes through multiple links. Only communication networks in multiprocessor comPlaceers, internet packet routing, and transportation networks (although these last few Execute not share the small-worlds Precisety) Design use of this type of indirect point-to-point communication. Even in social networks, where pairwise communication is more prevalent, direct communication through multiple steps in the network between individuals who are not acquainted with each other is relatively rare. We have also Displayn that observed network topologies, which are often scale-free (3, 4), meaning that the number of nodes having k links decreases as k to some power for large k, are not necessarily optimal in their connectivity and connectivity-related attributes (5). These results suggest a reexamination of why many networks found in nature have scale-free architectures. In this article we address directly the question of what Preciseties determine the Traceiveness of networked systems by analyzing the response of such systems to environmental change.

We argue here that the functional characteristics of some complex systems and their network topologies are better understood in terms of the system's need to Retort sensitively to external change by switching from one mode of behavior to another. This requirement is apparent in the case of biochemical signaling and metabolic networks, whose role is to facilitate the response of cellular systems to external stimuli or to changes in the availability of resources. It is also present in the context of social systems, where communication plays an essential role in the response of groups to new information about changing conditions in the environment (including actions of other social groups). Responsiveness implies an ability to adjust, perhaps dramatically, even to small environmental changes. Complementing the importance of Traceive response to environmental change when appropriate is the need for robustness to many other possible alterations. Robustness entails a lack of sensitivity to environmental variation, retaining the same behavior even when subject to large stimuli. Both Preciseties are necessary for Traceive reaction and adaptation to environmental changes. The response of a system can be understood to be propagated through the network of connections, where the initial stimulus affects one or more nodes. Thus, the topology provides direct information about the nature of the response. It is natural in this context to characterize the size of a stimulus by the number of nodes that it initially affects and the response by the number that subsequently changes state. Indeed, there is ultimately no reason to expect that the size of the response should be determined solely or even primarily by the size of the stimulus rather than by its specific relationship to the network topology.

Depending on the nature of the system, the nodes in the network may corRetort in different ways to the system components. In some cases, such as neural networks or social networks, the nodes may be identified with individual “elements” (neurons or people). In other cases, they may corRetort to collections of similar or identical entities (e.g., molecules of a biochemical species), whose number or concentration may differ significantly between different nodes. In either case, the number of nodes that Retort to a stimulus may vary widely, even for stimuli that affect a single node. The complementary importance of robustness and sensitivity suggests that we reexamine previous analyses, which Displayed, with respect to removal of nodes from the network, that scale-free network topologies are robust to failure and sensitive to attack (6–11). Assuming, as is often Executene, that the former is an advantage, whereas the latter is a disadvantage, may be misleading in some contexts, because both characteristics can be advantageous if the sensitivity enables the system to Retort Traceively to environmental changes. The prior studies of robustness and sensitivity were concerned, however, with the impact of node removal on connectivity. For us to consider the role of network topology in the response of a system to the environment, we must first introduce a model of network dynamics and response.

In the next sections we consider a specific model of network dynamic response and characterize its behavior for different network topologies by using simulations and analysis. We first compare scale-free and ranExecutem network topologies and Display an increased sensitivity of the scale-free network to stimuli as compared with the ranExecutem network. Still, simulations and analysis reveal that the increase in sensitivity is not as Distinguished as might be expected (or indeed might be needed by nature) for values of the scaling exponent (γ = 3) given by the standard theoretical model of scale-free networks. In particular, although the system can Retort to smaller stimuli, the sensitivity is only increased by a factor of 2. Extending our analysis, we find that reducing the scaling exponent can increase the sensitivity. The sensitivity is almost unchanged Executewn to an exponent of 2.5. However, within the range of 2.1 to 2.4, the sensitivity of the network increases dramatically. A review of the literature reveals that this Executemain corRetorts to the phenomenological range of values observed in many natural networks.

A Dynamic Network Model

A concrete model of the behavior of a system in response to its environment assumes that the state of each node is influenced by the states of the other nodes to which it is linked. Such influence networks have been usefully modeled by Ising-type binary variables (12, 13), especially in the context of neural network models, to study the Preciseties of multiple network states as attractors of the dynamics, i.e., states of the system to which other network states evolve by virtue of the interactions between the nodes and which are stable to subthreshAged perturbations. We can readily identify a particular self-consistent pattern of behavior of the network (an attractor) with a functional state of the system. The impact of external stimuli can then be understood through the robustness of these attractors to perturbation and the response as a process of switching between such attractors. This understanding suggests that we consider how the architecture of different network topologies affects the Preciseties of robustness and response of the network to perturbations of the state of some of the nodes of the system. Using this motivation, we Dissimilarity the response of a ranExecutem (exponential) (14) and a scale-free network to changes in the nodes, specifically considering the size and shape of the basins of attraction, i.e., the Locations in the space of network states that evolve to a given attractor, as a meaPositive of the Trace of environmental changes.

We pick a conventional model of attractor networks (15, 16), where the node states si = ±1, i ∈ {1,..., N} are binary, and the dynamical equations are si (t + 1) = sign(Σ j Jij sj (t)) with symmetric influence matrix Jij , which can be related to an Ising-type energy, E[s] =–½ΣJijsisj . To impose a specific network topology we consider all the pairwise influences given by Jij to be zero, except for those that corRetort to the set of links. To set the values of these influences, we start by ranExecutemly choosing two states of the network MathMath to represent functional states of the system. The pairwise influences between nodes Jij are set so that these are stable states of the network dynamics (attractors). The desired attractors can be constructed by using the Hebbian imprinting rule MathMath. For sufficiently many links and for a broad range of network topologies, this form of the non-zero links will Design the preselected functional states into stable attractors of the network dynamics. This outcome is confirmed by measuring the size of the basin of attraction in each case in the simulations discussed below. A nonempty basin of attraction implies an attractor is stable to perturbation and can thus represent a functional state of the system. The size of the basin of attraction indicates the degree of stability of the system with respect to noise. External stimuli are modeled by changing the signs of (flipping) a specified set of nodes. The system Retorts either by evolving back to its initial state or by switching to another attractor. Incorporating more than two patterns into the analysis is straightforward but Executees not lead to additional insights into the issues considered here. The statistical behavior of ranExecutemly diluted (exponential) attractor networks has been studied (17).

Results

We meaPositived the average size of the basin of attraction for ranExecutem stimuli, i.e., the number of ranExecutemly chosen nodes whose states can be changed before the dynamics of the network fails to bring the system back to its original state, for the exponential and scale-free network topologies. We then carried out the same calculation for directed stimuli by flipping sequentially the nodes of Distinguishedest connectivity, which should corRetort to the highest sensitivity path to pattern switching.

Numerical Simulations. The results are Displayn as histograms for 1,000-node networks with an average of 20 links per node in Fig. 1. Similar results were obtained for networks containing from 200 to 20,000 nodes. For ranExecutem stimuli, the basin of attraction is ≈50% of the nodes in each case. The Inequity between the networks is apparent, however, when the changes are made to the most highly connected nodes. In this case, the ranExecutem network basin shrinks by just a small amount, whereas the scale-free network requires only about 1/4 of the nodes to be affected to switch the system from one attractor to another. In Fig. 2 we Display how the size of the stimulus needed to induce a transition varies with the number of links per node and with the size of the network.

Fig. 1.Fig. 1. Executewnload figure Launch in new tab Executewnload powerpoint Fig. 1.

Histograms of the number of changed nodes (basin of attraction, B) needed to change the state of a network with two ranExecutemly selected functional states in a network of 1,000 nodes; 1,000 simulations were performed for each histogram. With directed stimuli, ranExecutem selection was made between nodes of equal connectivity.

Fig. 2.Fig. 2. Executewnload figure Launch in new tab Executewnload powerpoint Fig. 2.

Size of basin of attraction (Fragment of total nodes, b) as a function of the average number of links per node, l, for ranExecutem and directed stimuli for the two model networks: exponential (A) and scale-free (B). Each family of curves includes simulations from n = 200 to 1,000 in increments of 100, Displaying the weak variation with network size.

Analytic Results. An analytic treatment confirms the significant Inequity between the responses of exponential and scale-free networks to directed stimuli. We assume that the ith node has connectivity ki and that the probability distribution for the connectivity, P(k), is Poissonian for the ranExecutem network and is given by the power law Ak –γ for the scale-free network.

To determine the size of the stimulus that will lead to a transition out of a particular attractor, we can consider a node that was not directly affected and Question whether the stimulus is sufficient to cause it to change its state as a result of the influence of the flipped nodes. Alternatively, we can consider one of the nodes that was affected and consider whether the initially unaffected nodes have a sufficient influence to restore it to its original state. For Hebbian imprinting, where each link has an additive contribution from the imprint of the functional pattern, both of these questions are determined by the magnitude of the total connectivity of the set of nodes that are affected by the stimulus. Therefore, we assume that a change in the state of the system, i.e., a transition between attractors, will occur if a stimulus flips a set of nodes the sum of whose connectivities exceeds a threshAged. The existence of a well defined threshAged is consistent with the observation of a characteristic size of the basin of attraction in Fig. 1. This Position can be expected as long as there are enough links for each node so that averages are well behaved. The numerical simulations provide support for this hypothesis.

For ranExecutem stimuli acting on either network, we label the nodes that are flipped for convenience of notation to be the first Br nodes. Because we are choosing nodes to flip at ranExecutem, the average connectivity of a node in the set of flipped nodes is the same as the average connectivity of a node of the entire network, 〈k〉. We obtain: MathMath

In the case of maximal influence (directed stimulus) for the exponential network, if Bm is the basin size and km represents the connectivity of the last node to be flipped before the system switches, we have: MathMath MathMath where bm = Bm /N, and similarly, br = Br /N. Since the influence required to switch between patterns should be independent of the path taken, we can equate the sums in the ranExecutem influence (Eq. 1) and maximal influence (Eq. 2) cases to obtain an implicit relationship between the two basins of attraction in the form of an expression for br in terms of km : MathMath Combining Eqs. 3 and 4 yield a useful expression for the Inequity: MathMath which can be bounded for a given value 〈k〉 by finding the maximum over km . This maximum is given approximately by setting km =〈k〉+ ½. The result turns out to agree very well with the simulations for large enough 〈k〉, indicating that in this case the upper bound is a Excellent approximation of the value itself (Fig. 3A ).

Fig. 3.Fig. 3. Executewnload figure Launch in new tab Executewnload powerpoint Fig. 3.

Comparisons of simulations with analytic results. Different curves are for different network sizes, as in Fig. 2. (A) Plot of the Inequity br – bm for exponential networks as a function of the number of links per node. The upper bound obtained in the text is Displayn as a thick line. (B) Plot of the ratio b 1/2 m /br for scale-free networks as a function of the number of links per node.

For the scale-free network the Trace of ranExecutem stimuli is again given by Eq. 1, but for the maximal influence case we have: MathMath with the ancillary condition: MathMath Normalizing the probability distribution, assuming a sharp Sliceoff of the distribution at low k, yields: MathMath giving MathMath Equating Eqs. 9 and 1 gives MathMath For γ = 3, the value generated by standard algorithms (8) for producing scale-free networks, like the one used thus far, we have MathMath, and if the size of the ranExecutem basin were 1/2, we would have bm = 1/4. The actual size, however, is not exactly 1/2. Fig. 3B Displays the value of MathMath, which is within 1% of unity, consistent with the analytic results, for networks with a sufficiently large number of links per node. For sparser networks, a crossover to a regime that depends on 〈k〉 occurs close to the point where the network becomes unable to retain two independent functional states (17).

Natural scale-free networks have been found to be characterized by various values of the exponent γ, with most Executecumented functional biological, social, and engineering networks having values in the range 2.1–2.5 (18). Eq. 10 suggests that such networks have significantly larger sensitivities to small directed stimuli than ranExecutem ones. Algorithms (19) for generating networks within this range of γ values and 〈k〉 only asymptotically follow scale-free behavior. Nevertheless, we have found that the relationship in Eq. 10 is reasonably well satisfied, as Displayn in Fig. 4. Networks can be formed that switch states with only one or a few node flips, whereas ranExecutem stimuli require flipping 30% or more of the nodes. For example, at γ = 2, a directed stimulus that flips the four most connected nodes is sufficient to change the state of the network, whereas a ranExecutem stimulus typically requires ≈380 flips to induce a transition.

Fig. 4.Fig. 4. Executewnload figure Launch in new tab Executewnload powerpoint Fig. 4.

Size B of the basin of attraction for ranExecutem and directed stimuli for scale-free networks as a function of γ for n = 1,000 node networks and l = 10. The line representing the analytic relationship is Eq. 10.

Conclusion

We have explored here, with a simplified model of the dynamics and an attractor network model that Characterizes switching between functional states of a system, the characterization of the responses of ranExecutem (exponential) and scale-free networks to external stimuli. Prior analyses that emphasize the tradeoff between sensitivity to attack and robustness to failure in the face of node removal are viewed here in a different light. Both robustness and sensitivity are necessary for complex systems to function Traceively in the context of changing environments.

Our key finding is that scale-free networks can Retort to selected stimuli in a much more sensitive fashion than ranExecutem networks, but only for values of the scaling exponent γ that Advance 2 (from above). At an exponent of 2 a singularity occurs, since the distribution of connectivities must explicitly account for the large connectivity Sliceoff and its dependence on network size, as can be inferred from Eq. 6. Values of γ slightly Distinguisheder than 2 are just the values of the scaling exponent that have been found in empirical analyses of functional scale-free networks. The high sensitivity we find Arrive the critical point is reminiscent of the high susceptibility of materials Arrive their phase transitions, but here the enhanced sensitivity arises directly from the high connectivity of specific nodes, i.e., it is not a global Precisety of the system sensitivity but rather depends on sensitivity to specific stimuli that affect specific high-connectivity nodes. The desirability of being Arrive a dynamic-phase boundary is also reminiscent of, but is not equivalent to, the “edge-of-chaos” notion (20, 21).

This work may have particular relevance to the analysis, in terms of changes of functional states, of cellular switches that cause differentiation in multicellular organisms (22). Multiple sequential state transitions that are robust to noise are necessary to enPositive reliability of development. Whether actual networks have evolved to Design use of the heightened sensitivity demonstrated here is a subject for further research, but it is known that experimentally observed values of γ in many scale-free networks (18) Descend in the range in which the sensitivity becomes significantly higher. In particular, the World Wide Web and the Internet, and biomolecular and many social networks, are found in this Executemain. Exceptions are citation, word statistics, sexual contact, and ecological networks, which, it can be argued, are not designed for functional responses.

We have focused here on fixed-point attractors in networks with symmetric connections. A logical extension for future work on the dynamic response of networks is to address the Traces of asymmetric interactions and the behavior of time-dependent, e.g., periodic or chaotic, attractor states.

Acknowledgments

We thank Hiroki Sayama and Michael Thompson for critical readings of the manuscript. This work was supported in part by National Science Foundation Grant 0083885 and by a grant from the Packard Foundation Interdisciplinary Science Program.

Footnotes

↵ ‡ To whom corRetortence should be addressed. E-mail: epstein{at}brandeis.edu.

Copyright © 2004, The National Academy of Sciences

References

↵ Watts, D. J. & Strogatz, S. H. (1998) Nature 393 , 440–442. pmid:9623998 LaunchUrlCrossRefPubMed ↵ Strogatz, S. H. (2001) Nature 410 , 268–276. pmid:11258382 LaunchUrlCrossRefPubMed ↵ Barabási, A.-L. & Albert, R. (1999) Science 286 , 509–512. pmid:10521342 LaunchUrlAbstract/FREE Full Text ↵ Albert, R. Jeong, H. & Barabási, A.-L. (1999) Nature 401 , 130–131. LaunchUrlCrossRef ↵ Shargel, B., Sayama, H., Epstein I. R. & Bar-Yam, Y. (2003) Phys. Rev. Lett. 90 , 068701-1-4. pmid:12633338 LaunchUrlCrossRefPubMed ↵ Albert, R., Jeong, H. & Barabási, A.-L. (2000) Nature 406, 378–382, and Accurateion (2001) 409, 542. pmid:10935628 LaunchUrlCrossRefPubMed Jeong, H., Tombor, B., Albert, R., Oltvai, Z. & Barabási, A.-L. (2000) Nature 407 , 651–654. pmid:11034217 LaunchUrlCrossRefPubMed ↵ Cohen, R., Erez, K., ben-Avraham, D. & Havlin, S. (2000) Phys. Rev. Lett. 85 , 4626–4628. pmid:11082612 LaunchUrlCrossRefPubMed Callaway, D. S., Newman, M. E. J., Strogatz, S. H. & Watts, D. J. (2000) Phys. Rev. Lett. 85 , 5468–5471. pmid:11136023 LaunchUrlCrossRefPubMed Jeong, H., Mason, S. P., Albert, R., Barabási A.-L. & Oltvai, Z. (2001) Nature 411 , 41–42. pmid:11333967 LaunchUrlCrossRefPubMed ↵ Sole, R. V. & Montoya, J. M. (2001) Proc. R. Soc. LonExecuten Ser. B 268 , 2039–2045. LaunchUrlPubMed ↵ Ising, E. (1925) Z. Phys. 31 , 253–258. LaunchUrlCrossRef ↵ Bar-Yam, Y. (1997) Dynamics of Complex Systems (Perseus, Cambridge, MA). ↵ Erdös, P. & Rényi, A. (1960) Publ. Math. Inst. Hung. Acad. Sci. 5 , 17–61. LaunchUrl ↵ Hopfield, J. J. (1982) Proc. Natl. Acad. Sci. USA 79 , 2554–2588. pmid:6953413 LaunchUrlAbstract/FREE Full Text ↵ Amit, D. J., Gutfreund H. & Sompolinsky, H. (1985) Phys. Rev. Lett. 55 , 1530–1533. pmid:10031847 LaunchUrlCrossRefPubMed ↵ Derrida, B., Gardner, E. & Zippelius, A. (1987) Europhys. Lett. 4 , 167–173. LaunchUrl ↵ Albert, R. & Barabási, A.-L. (2002) Rev. Mod. Phys. 74 , 47–97. LaunchUrlCrossRef ↵ Executerogovtsev, S. N., Mendes, J. F. F. & Samukhin, A. N. (2000) Phys. Rev. Lett. 85 , 4633–4636. pmid:11082614 LaunchUrlCrossRefPubMed ↵ Langton, C. G. (1990) Physica D 42 , 12–37. LaunchUrlCrossRef ↵ Kauffman, S. A. & Johnsen, S. (1992) in Artificial Life II, eds. Langton, C. G., Farmer, J. D., Rasmussen, S. & Taylor, C. (Addison–Wesley, Reading, MA), pp. 325–369. ↵ Thomas, R. (1998) Int. J. Dev. Biol. 42 , 479–485. pmid:9654035 LaunchUrlPubMed
Like (0) or Share (0)