New Research In
Physical Sciences
Social Sciences
Featured Portals
Articles by Topic
Biological Sciences
Featured Portals
Articles by Topic
 Agricultural Sciences
 Anthropology
 Applied Biological Sciences
 Biochemistry
 Biophysics and Computational Biology
 Cell Biology
 Developmental Biology
 Ecology
 Environmental Sciences
 Evolution
 Genetics
 Immunology and Inflammation
 Medical Sciences
 Microbiology
 Neuroscience
 Pharmacology
 Physiology
 Plant Biology
 Population Biology
 Psychological and Cognitive Sciences
 Sustainability Science
 Systems Biology
Dynamic pattern evolution on scalefree networks

Edited by Michael E. Fisher, University of Maryland, College Park, MD, and approved May 25, 2005 (received for review December 14, 2004)
Abstract
A general class of dynamic models on scalefree networks is studied by analytical methods and computer simulations. Each network consists of N vertices and is characterized by its degree distribution, P(k), which represents the probability that a randomly chosen vertex is connected to k nearest neighbors. Each vertex can attain two internal states described by binary variables or Isinglike spins that evolve in time according to local majority rules. Scalefree networks, for which the degree distribution has a power law tail P(k) ∼ k ^{γ}, are shown to exhibit qualitatively different dynamic behavior for γ < 5/2 and γ > 5/2, shedding light on the empirical observation that many realworld networks are scalefree with 2 < γ < 5/2. For 2 < γ < 5/2, strongly disordered patterns decay within a finite decay time even in the limit of infinite networks. For γ > 5/2, on the other hand, this decay time diverges as ln(N) with the network size N. An analogous distinction is found for a variety of more complex models including Hopfield models for associative memory networks. In the latter case, the storage capacity is found, within mean field theory, to be independent of N in the limit of large N for γ > 5/2 but to grow as N ^{α} with α = (5  2γ)/(γ  1) for 2 < γ < 5/2.
The biosphere contains many complex networks built up from rather different elements such as molecules, cells, organisms, or machines. Despite their diversity, these networks exhibit some universal features and generic properties, a topic of much recent interest (16). One important result of this recent activity is a classification scheme for the structure of networks in terms of their topology and connectivity (5, 6). The basic elements of each network can be represented by nodes or vertices and their interrelations by edges between these vertices. By definition, the degree, k, of a given vertex is equal to the number of edges connected to it. In this way, each network is characterized by its graph, a well defined mathematical object (7). Four large subsets of network graphs have been characterized in terms of their connectivity properties: regular ordered and random networks, which have been studied for a long time, as well as smallworld (1) and scalefree (4) networks. The latter types of networks are characterized by a degree distribution, P(k), that decays as P(k) ∼ 1/k ^{γ} with decay exponent γ.
Many biological, social, and technological networks are found to be scalefree (5, 6). To explain this abundance, several mechanisms have been proposed, some of which are related to the growth of networks with preferential attachment rules (5, 8). The impact of network architecture on network integrity or resilience has also been investigated (6, 911). Upon random removal of a finite fraction of vertices, a scalefree network with decay exponent 2 < γ < 3 will always keep a giant component. In contrast, if a tiny fraction of the most highly connected vertices is selectively removed, such a network will also break up into many small components. Applying this insight to the case of disease spreading on networks, one realizes that infective diseases have a high probability to affect the whole network (12) unless one immunizes the most highly connected vertices (13).
Random removal of vertices is equivalent to the process of site percolation on the initial network (9, 10). Likewise, disease spreading is intimately related, in the long time limit, to bond percolation (6, 10). In general, the elements of real networks are dynamic and exhibit various properties that change with time. A more detailed description of the network dynamics is then obtained in terms of dynamical variables associated with each vertex of the network. We will consider processes on networks that evolve fast compared with any changes in the network topology, which is therefore taken to be timeindependent. Two examples for such dynamical processes are provided by the regulation of genetic networks that exhibit a changing pattern of active and inactive genes (see, e.g., ref. 14) or by neural networks that can be characterized by firing and nonfiring neurons (see, e.g., ref. 15).
To identity universal features and generic properties, it is often convenient to use discrete dynamical variables and to allow each vertex to attain several distinct states. The network is then characterized, at each moment in time, by a certain pattern of these internal vertex states, and the time evolution of these patterns represents the global dynamics of the whole network.
The study of discrete dynamical processes on ordered and random networks has a long history. Ordered networks have been studied in the context of neural computation (16, 17), cellular automata or Boolean dynamics (18, 19), and dynamic Ising models (20). Random networks with random Boolean dynamics were introduced in the context of gene expression and studied as prototypes of random cellular automata (2123). Discrete dynamic processes on smallworld networks were discussed in ref. 2, whereas analogous processes on scalefree networks have only been addressed rather recently (2426).
Random networks as originally studied in mathematics (57) are characterized by a Poissonian degree distribution as given by P(k) =〈k〉 ^{k}e ^{〈k〉}/k!, where 〈k〉≡∑kP(k) denotes the mean value of the vertex degree k. In contrast, scalefree networks are characterized by P(k) ∼ k ^{γ} with decay exponent γ for an intermediate range of kvalues that can be defined as follows. To avoid disconnected subgraphs, it is useful to introduce a certain minimal degree k _{0} > 0. Furthermore, a large but finite network containing N vertices is also characterized by a certain maximal degree k_{N} . These two “cutoffs” can be incorporated in a particularly simple way via the explicit form (9)
with the normalization factor and k_{N} = k _{0} N ^{1/(γ  1)} (see Degree Distribution and Maximal Vertex Degree in Supporting Text, which is published as supporting information on the PNAS web site).
Many scalefree networks are characterized by decay exponents γ that fall into the narrow range 2 < γ ≤ 5/2 as observed in ref. 24. Indeed, table 2 of ref. 5 contains a list of ten scalefree networks with 2 < γ < 5/2, one with γ = 2.5, and only three with 2.5 < γ < 3. The lower boundary value γ = 2 is easy to understand since it ensures that the mean vertex degree 〈k〉 = ∑kP(k) remains finite in the limit of large N. The upper boundary value γ = 5/2 is less obvious. To gain some insight into this latter value, Aldana and Cluzel (24) studied the Kauffman model, i.e., random Boolean dynamics for binary variables or Isinglike spins (21, 22) on scalefree networks. They suggested the criterion that scalefree networks with decay exponent 2 < γ < 5/2 are located on the boundary between order and chaos (24). However, for random Boolean dynamics, the phase boundary between order and chaos turns out to be independent of the network architecture but depends only on the mean vertex degree 〈k〉. Indeed, this phase boundary is determined by the simple relation 2〈k〉ρ(1  ρ) = 1 between 〈k〉 and the model parameter ρ, which represents the probability that the output of a Boolean function with random input will be equal to 1 (22). As long as 〈k〉 > 2, this equation has two solutions in the physical range 0 < ρ < 1 that determine the boundaries between the ordered and the chaotic phases. Since scalefree networks with γ > 5/2 as well as random Poissonian networks can have 〈k〉 > 2, all of these networks can exhibit transitions between ordered and chaotic phases if the binary patterns evolve according to random Boolean dynamics (21, 22).
In this article, we consider dynamic network models for binary variables or Isinglike spins which evolve in time according to local majority rules on scalefree networks. The latter rules are equivalent to the socalled Glauber dynamics (20) for Isingmodels at zero temperature. In addition, we extend our study to finite temperature in the context of Hopfield models (17, 27) for associative memory networks and to networks with directed edges. The main results of our study are as follows.
First, using mean field theory and computer simulations, we show that scalefree networks with γ = 5/2 represent a sharp boundary for the local majority dynamics. This boundary is defined with respect to the decay of strongly disordered patterns and the associated growth of order within these patterns. For γ < 5/2, the disordered patterns decay within a finite time even in the limit of infinite networks. For γ > 5/2, on the other hand, this decay time diverges as ln(N) with the vertex number N. The latter behavior is consistent with recent results for opinion spreading on social networks (28). The different dynamic behavior of scalefree networks with γ < 5/2 and γ > 5/2 provides a new light on the empirical observation that most realworld networks are scalefree with 2 < γ < 5/2.
Second, our simulations give strong evidence that, for scalefree networks, disordered patterns typically evolve toward the two completely ordered patterns (or ground states) provided the networks are connected, the minimal vertex degree k _{0} > 1, and the mean vertex degree 〈k〉 is sufficiently large. This is rather different from the behavior found previously for treelike networks (29) and for ddimensional hypercubic networks with d ≥ 3 (30), where the evolving patterns are typically trapped in metastable states with many domain boundaries and “blinkers,” but is consistent with the behavior observed in random Poissonian networks (31).
Third, we determine the minimal fraction of spins which one has to flip to transform the allspindown pattern into another pattern that evolves toward the allspinup pattern under the local majority dynamics. We derive an analytical expression for this minimal fraction and show that it vanishes very rapidly as ∼ exp(const/(γ  2)) as the decay exponent γ approaches the value γ = 2. This sensitivity of ordered spin patterns to selective spin flips has been independently observed in ref. 25. In contrast to the behavior of the decay time for strongly disordered patterns, the minimal fraction varies smoothly with the decay exponent γ in the vicinity of γ = 5/2.
Fourth, when extended to Hopfield models on scalefree networks, our mean field theory predicts that γ = 5/2 represents a sharp boundary for these models as well. For γ > 5/2, the maximal storage capacity of the network does not grow with the network size N in the limit of large N. In contrast, for 2 < γ < 5/2, the maximal storage capacity grows as N ^{α} with α = (5  2γ)/(γ  1) for large N. Very recently, it has been argued that functional networks in the human brain resemble scalefree networks with γ ≃ 2.1 (32). For the latter networks, our mean field theory predicts the storage capacity to grow as N ^{α} with α ≃ 0.73. This growth of the storage capacity with network size N is almost as fast as in the original Hopfield model (17) on complete graphs with vertex degree k = N  1 for which α = 1.
Models and Methods
To proceed, consider random scalefree networks with N vertices and M edges with degree distribution P(k) as obtained from the socalled configuration model (6) (see Numerical Generation of ScaleFree Networks in Supporting Text and Fig. 5, which is published as supporting information on the PNAS web site). Each vertex i of such a network has two internal states described by the Ising spin σ _{i} = ±1. The network architecture is embodied in the network's adjacency matrix I with matrix elements I_{ij} = 1 if the two vertices i and j are nearest neighbors, i.e., if they are connected by an edge, and I_{ij} = 0 otherwise. At each vertex i, we define the field h_{i} ≡∑ _{j} I_{ij} σ _{j} . The sign of the field h_{i} is positive and negative if the majority of the nearest neighbor spins is positive or negative, respectively. The time evolution of the spin pattern is now defined by the local majority rule as given by
In the special case h_{i} (t) = 0, we choose σ _{i} (t + 1) = +1 or 1 with equal probability. These local majority rules are equivalent to Glauber dynamics (20) at zero temperature as studied, e.g., on ddimensional hypercubic networks (30) and on random Poissonian networks (31). Recently, similar dynamic models were also used in the context of opinion spreading (28), network robustness and sensitivity (25), and the yeast cellcycle regulation system (26).
In general, the graph of a random scalefree network may be disconnected and consist of several components. In such a situation, the pattern evolution in one network component is completely independent of the evolution in all of the other components. To avoid this division of the evolving patterns into several subpatterns, we will focus on degree distributions characterized by minimal vertex degree k _{0} ≥ 2 and mean vertex degree 〈k〉 ≥ 10 for which graphs with several components are rather unlikely. In general, random graphs with 〈k〉> 1 have one giant component and several small ones; for Poissonian graphs, the giant component contains φ(〈k〉)N vertices, where φ(〈k〉) approaches φ(∞) = 1 exponentially fast with increasing 〈k〉 (5). For such disconnected networks, our analysis applies to the pattern evolution on the giant components as long as k _{0} > 1. Random scalefree networks with k _{0} = 1 are special since they tend to be treelike with many surface sites.
To study the time evolution of the spin patterns in more detail, we consider the probabilities q_{k} (t) that a vertex with degree k is in the spinup state, and the probability Q(t) that, for any vertex in the network, a randomly chosen nearest neighbor vertex is in the spinup state. As will become clear below, the probability Q is directly related to the order parameter of the system and will, thus, be called the ordering probability. Since a vertex associated with a randomly chosen edge has degree k with probability kP(k)/〈k〉 in a random network with no vertex degree correlations, the probabilities q_{k} and the ordering probability Q satisfy the simple relation with 0 ≤ Q(t) ≤ 1. Note that the ordering probability Q differs, in general, from the overall probability to find any vertex in the spinup state. The latter probability is given by 〈q〉 ≡ ∑ _{k} P(k)q_{k} . Special patterns for which 〈q〉 = Q are provided by kindependent probabilities q_{k} = q. In particular, for the allspindown pattern with q_{k} = 0 for all k and for the allspinup pattern with q_{k} = 1 for all k, one has Q = 〈q〉 = 0 and Q = 〈q〉 = 1, respectively.
If we know the ordering probability Q at a certain time t, we can calculate the probabilities q_{k} at the next time step. Indeed, it follows from the majority rule dynamics as defined by Eq. 2 that
where the prime at the summation symbol indicates that this sum runs over all integer m with k/2 ≤ m ≤ k, δ is the Kronecker symbol, and B_{k} _{,} _{m} ≡ k!/[m!(k  m)!] are the binomial coefficients. Finally, summation of the lefthand side of Eq. 4 leads to the evolution equation
for the ordering probability Q with the evolution function
for random graphs with no vertex degree correlations as considered here.
The evolution equation (5) has two stable fixed points at Q = 0 and Q = 1, and an unstable one at Q = 1/2. The fixed points with Q = 0 and Q = 1 correspond to the allspindown and allspinup patterns, respectively. The unstable fixed point with Q = 1/2 represents the phase boundary between these two ordered patterns; the corresponding boundary patterns are characterized by probabilities q̂_{k} , which satisfy
where M is the total number of edges. A subset of these boundary patterns is provided by those patterns for which the probabilities q̂_{k} = 1/2 for all vertex degrees k. Therefore, the order parameter of these systems is taken to be
which vanishes for all boundary patterns.
In the next section, we will compare the mean field trajectories obtained from the evolution equation (5) with the pattern evolution obtained from computer simulations. In the latter case, one starts from a certain initial pattern and applies the majority rule dynamics as given by Eq. 2 to each vertex of the network. Since we want to be able to use the same initial pattern for both mean field theory and computer simulations, we will define the enlarged set of strongly disordered patterns that consists (i) of the boundary patterns characterized by Eq. 7 and (ii) of additional patterns characterized by probabilities q̃_{k} that lead to Q = Q̃ = 1/2 ± 1/2M and, thus, to the order parameter
which vanishes in the limit of large network size N. A pattern with probabilities q̃_{k} can be obtained from a boundary pattern by simultaneously flipping two spins with opposite orientations on a k and (k + 1) vertex.
The evolution equation for the order parameter y = Q  1/2 can be directly obtained from the corresponding equation (7) for Q and is given by y(t + 1) =Ψ(1/2 + y(t))  1/2. In the vicinity of the unstable fixed point with Q = 1/2 and Ψ(1/2) = 1/2, the latter equation can be linearized and becomes
for small y(t). Iterating this equation n times from an initial time t _{0} up to a final time t _{1}, one obtains the time difference
in the limit of small y(t _{0}).
It follows from the explicit expression (Eq. 6) for the evolution function Ψ(Q) that the derivative Ψ′(1/2) at the unstable fixed point with Q = 1/2 diverges for a scalefree network with decay exponent γ ≤ 5/2 in the limit of large network size N. More precisely, one obtains the asymptotic behavior
in the limit of large N with α = (5  2γ)/(γ  1), where c _{γ} is a dimensionless γdependent coefficient (see Derivation of Eq. 12 in Supporting Text).
Results and Discussion
Decay of Strongly Disordered Patterns. Now, consider an initial state of the network at time t = t _{0} that corresponds to a strongly disordered pattern with order parameter y(t _{0}) = ỹ = ±1/2M ∼ 1/N as in Eq. 9. For t > t _{0}, such an initial pattern evolves according to the majority rule dynamics that leads to an increase in the absolute value of the order parameter y and, thus, to the growth of order. We will characterize this decay of the strongly disordered patterns by the decay time t_{d} , which is the time it takes to reach a pattern with an order parameter y _{*} that satisfies y _{*} ≥ 1/4. In addition, we have also estimated the probability to reach the completely ordered patterns when one initially starts from strongly disordered ones.
Within mean field theory, the decay time t_{d} follows from Eq. 11 and is given by t_{d} ≈ ln(〈k〉N)/ln(Ψ′(1/2)) for large 〈k〉 or large N. This expression behaves as
in the limit of large network size N. Thus, for scalefree networks with decay exponent 2 < γ < 5/2, strongly disordered patterns always decay after a finite number of iteration steps even in the limit of large N. In contrast, for networks with γ > 5/2, the decay time diverges as ln(N). The latter behavior for γ > 5/2 also applies to Poissonian networks and is, thus, consistent with recent results for opinion spreading on social networks (28).
We have confirmed these mean field predictions by computer simulations. To avoid both disconnected and treelike network graphs, the simulations were performed for networks with a relatively large mean vertex degree 〈k〉 and minimal vertex degree k _{0} > 1. In Fig. 1, we display the time evolution of the absolute value of the order parameter, y = Q  1/2, as obtained for three different networks that have the same size n = 2^{18} and the same mean vertex degree 〈k〉 = 20 but are distinguished by their degree distributions: These networks are scalefree with γ = 2.25 and k _{0} = 5, scalefree with γ = 3 and k _{0} = 10, and Poissonian, respectively. For each network, 2,000 initial spin patterns are generated, which are all strongly disordered and characterized by the initial order parameter y(t _{0}) = ỹ = 1/〈k〉N as in Eq. 9. For each of these initial patterns, the local majority dynamics leads to an increase of y with time t. Finally, the time evolution as shown in Fig. 1 is obtained, for each network, via an average over all 2,000 trajectories.
The distributions of the decay times t_{d} corresponding to the individual trajectories of the three networks are displayed in Fig. 2. Inspection of this figure shows that the decay time distribution for the scalefree network with γ = 2.25 has a narrow peak around t_{d} ≃ 4, whereas the decay time distributions for the scalefree network with γ = 3 and for the Poissonian network are much broader and shifted toward larger values. The three histograms shown in Fig. 2 correspond to all trajectories with a decay time t_{d} up to 30 iteration steps. For the scalefree network with γ = 2.25, 9 of 2,000 trajectories have a decay time between 30 and 100 iteration steps, and 2 of 2,000 trajectories have a decay time that exceeds 100 steps. Likewise, for the scalefree network with γ = 3 and for the Poissonian network, only one and no trajectory, respectively, had a decay time above 100 steps.
The maximum of the decay time distribution defines the most probable decay time. This time scale was determined for three ensembles of scalefree networks with (i) γ = 2.25 and k _{0} = 5, (ii) γ = 2.5 and k _{0} = 7, and (iii) γ = 3 and k _{0} = 10. All three ensembles are characterized by the same mean vertex degree 〈k〉 = 20. Each ensemble consists of 100 different random networks. For each of these networks, 1,000 different pattern trajectories were determined starting from 1,000 strongly disordered spin patterns as in Eq. 9. The most probable decay times obtained in this way are displayed in Fig. 3 as a function of the network size N. In this figure, we compare the results obtained by numerical iterations of the majority rule dynamics as in Eq. 2 with the mean field results corresponding to the evolution equation (5). Inspection of Fig. 3 shows that the most probable decay time is indeed very insensitive to the vertex number N for γ = 2.25 but grows with N as ∼ ln(N) for γ = 3.0. For the borderline case with γ = 5/2, the decay time grows more slowly than ln(N).
We have also studied the approach of the evolving patterns toward the completely ordered patterns (or ground states) with Q = 0 or Q = 1. For the three networks just discussed, which are characterized by vertex number n = 2^{18} and mean vertex degree 〈k〉 = 20, the probability to reach these ordered patterns is very close to 1: In all three cases, we find that the probability of not reaching the completely ordered patterns within 100 steps is smaller than 10^{2} (see Fig. 6, which is published as supporting information on the PNAS web site). For the scalefree networks with γ = 2.25 and 〈k〉 = 20, we have also determined this latter probability as a function of the network size N and found that it is smaller than 0.6 × 10^{2} for 2^{10} ≤ n ≤ 2^{18} (see Fig. 7, which is published as supporting information on the PNAS web site).
To see how the time evolution of the order parameter depends on the mean vertex degree 〈k〉, the same set of simulations was also performed for three networks with 〈k〉= 10 and k _{0} ≥ 2. The corresponding decay time distributions are found to be rather similar to those displayed in Fig. 2 (see Fig. 8, which is published as supporting information on the PNAS web site). The main difference is that the approach to the completely ordered patterns is slowed down (see Figs. 9 and 10, which are published as supporting information on the PNAS web site). Additional simulations for mean vertex degree 〈k〉= 7 and 〈k〉= 5 show that the time to reach the completely ordered patterns further increases with decreasing 〈k〉. These simulation results are consistent with those obtained for random Poissonian networks (31) but are rather different from the behavior found for treelike networks (29) and for ddimensional hypercubic lattices with d ≥ 3 (30).
As emphasized in refs. 30 and 31, spin patterns, which evolve according to local majority dynamics, can be trapped in metastable states corresponding to several spinup and spindown domains. In addition, the domain boundaries may not be completely frozen but may contain “blinkers,” i.e., single spins that continue to flip after each time step. It is not difficult to see that domain boundaries and blinkers are likely to occur for spin patterns on treelike graphs (33), leading to the glassy dynamics found for Cayley trees (29). Somewhat surprisingly, multidomain patterns with blinkers are also typical for ddimensional hypercubic lattices with d ≥ 3 as shown in ref. 30. In contrast, our simulations give strong evidence that, for scalefree networks with k _{0} > 1, disordered patterns typically evolve toward the two completely ordered patterns provided the networks are connected and the mean vertex degree 〈k〉 is sufficiently large. The case k _{0} = 1 is special since the graphs tend to be treelike, and their dynamics is presumably characterized by blinkers as well.
Selective Spin Flips. Now, let us look at a different aspect of the response behavior. We start from the allspindown pattern and ask how many spins we have to flip to reach another pattern that evolves toward the allspinup pattern under the local majority dynamics.
If we flipped the spins on a randomly chosen set of vertices, we would have to flip, in general, of the order of N/2 spins. However, we can induce such a global transition in a much more efficient way if we flip primarily those spins that are located on the highly connected vertices. This is illustrated in Fig. 4, which displays the minimal fraction of spins, Ω_{min}, which one has to flip to transform the allspindown pattern into the allspinup pattern. An analytical estimate for this minimal fraction can be obtained from the explicit relation for the boundary patterns as given by Eq. 7 if one considers such patterns with q̂_{k} = 0 for k _{0} < k < k_{*} and q̂_{k} = 1 for k_{*} < k < k_{N} , where the intermediate kvalue k _{*} is determined by the requirement that the spin pattern represents a boundary pattern with ordering probability Q = Q̂ = 1/2 (see Derivation of Eq. 14 in Supporting Text). For large vertex number N, this leads to the asymptotic estimate
This minimal fraction does not depend on the mean vertex degree 〈k〉 and vanishes very rapidly as ∼ exp(const/(γ  2)), i.e., as an essential singularity in γ  2. Both properties are fully confirmed by the numerical results (see Fig. 4). For γ = 3, for example, the asymptotic estimate (Eq. 14) leads to Ω_{min} ≈ 1/4 in perfect agreement with the numerical results shown in Fig. 4. This sensitivity of ordered spin patterns to selective spin flips has been independently observed in ref. 25.
Thus, a scalefree network with a decay exponent γ that is close to γ = 2 has the additional property that one needs to selectively flip only a very small fraction of the spins to induce a transition from one ordered pattern to the other. This property provides a very efficient way for the system to adapt its state in response to varying external conditions. Note, however, that in contrast to the behavior of the response time, the dependence of the minimal fraction Ω_{min} on the decay exponent γ does not exhibit a sharp borderline at γ = 5/2.
Dynamic Behavior of More Complex Models. The main features of the pattern evolution described above are quite generic and remain valid for various extensions and generalizations of the majority rule dynamics. One particularly interesting generalization is obtained if we extend our mean field theory to Hopfield models (17, 27) that address the maximal storage capacity S _{max} of associative memory networks. This capacity, which represents the largest possible number of patterns that can be stored in the network, is found to behave as
with α = (5  2γ)/(γ  1) in the limit of large network size N (see Hopfield Models on ScaleFree Networks in Supporting Text). In contrast, for γ > 5/2, the maximal storage capacity S _{max} does not grow with the network size N for large N. It has been recently argued that some functional networks in the human brain are indeed scalefree with γ ≃ 2.1 (32, 34). Thus, for these latter networks, our mean field theory predicts that the storage capacity grows as N ^{α} with α ≃ 0.73, which is almost as fast as in the original Hopfield model on complete graphs that have the constant vertex degree k = N  1 and are characterized by α = 1.
We have also extended our analysis of the majority rule dynamics to a variety of other models including Potts models on nondirected networks as well as to Ising models on directed networks (see Extension to Directed ScaleFree Networks in Supporting Text). For all of these generalizations, we find that γ = 5/2 represents a borderline case for the dynamic pattern evolution.
Summary. In summary, we have studied the response behavior of a large class of dynamic network models. We found that scalefree networks are characterized by very rapid response provided γ < 5/2. As far as the decay time of strongly disordered patterns is concerned, γ = 5/2 represents a sharp borderline. For γ < 5/2, all of these patterns decay within a finite decay time even in the limit of infinite vertex number. For γ > 5/2, on the other hand, this time diverges as ln(N) for large vertex number N. We also determined the minimal fraction of spin flips to induce a transition from one ordered pattern to another ordered pattern. This fraction becomes very small as one reduces the value of γ and vanishes as an essential singularity in γ  2. These results are generic and can be generalized to more complex models that involve more than two vertex states and/or directed edges.
One particularly interesting extension is to Hopfield models for associative memory on scalefree networks. In this latter case, we find that the storage capacity is independent of network size N for γ > 5/2 but grows as N ^{α} with α = (5  2γ)/(γ  1) for 2 < γ < 5/2. For the functional networks of the human brain with γ ≃ 2.1 (32), this implies that the storage capacity grows as N ^{α} with α ≃ 0.73. These mean field predictions should be accessible to simulation studies that have been restricted, so far, to the special case γ = 3 > 5/2 (35).
Our results shed light on the empirical observation that many realworld networks are scalefree with decay exponent 2 < γ < 5/2. Further extensions of our study should address possible effects of vertexvertex correlations, which are present in realworld networks and lead to clustering (1) and modularity (3, 36). We expect that correlations between vertices of high degree will make the response of scalefree networks with γ < 5/2 even more rapid, but this remains to be studied in more detail. Likewise, it will be interesting to investigate how the response behavior is influenced by weighted edges (see, e.g., ref. 37) corresponding to variable nearest neighbor couplings.
Note Added in Proof. For the special case of scalefree networks with minimal vertex degree k _{0} = 1, additional simulations have confirmed that the decay of strongly disordered patterns is characterized by persistent oscillations of the order parameter y around y = 0.
Acknowledgments
We thank Max Aldana for interesting correspondence about his previous work on scalefree networks.
Footnotes

↵ † To whom correspondence should be addressed. Email: lipowsky{at}mpikg.mpg.de.

Author contributions: H.Z. and R.L. designed research; H.Z. and R.L. performed research; and R.L. wrote the paper.

This paper was submitted directly (Track II) to the PNAS office.

Freely available online through the PNAS open access option.
 Copyright © 2005, The National Academy of Sciences
References
 ↵

↵
Watts, D. J. (1999) Small Worlds (Princeton Univ. Press, Princeton).
 ↵

↵
Barabási, A.L. & Albert, R. (1999) Science 286 , 509512. pmid:10521342
 ↵
 ↵

↵
Bollobas, B. (1998) Modern Graph Theory (Springer, New York).
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵

↵
Tong, A. H. Y., Lesage, G., Bader, G. D., Ding, H., Xu, H., Xin, X., Young, J., Berriz, G. F., Brost, R. L., Chang, M., et al. (2004) Science 303 , 808813. pmid:14764870

↵
Dayan, P. & Abbott, L. (2001) Theoretical Neuroscience (MIT Press, Cambridge, MA).
 ↵

↵
Hopfield, J. J. (1982) Proc. Natl. Acad. Sci. USA 79 , 25542558. pmid:6953413

↵
von Neumann, J. (1963) in John von Neumann, Collected Works, ed. Taub, A. H. (Pergamon, Oxford), Vol. 5.
 ↵
 ↵
 ↵

↵
Derrida, B. & Pomeau, Y. (1986) Europhys. Lett. 1 , 4549.

↵
Aldana, M., Coppersmith, S. & Kadanoff, L. P. (2003) Perspectives and Problems in Nonlinear Science, eds. Marsden, J. E., Kaplan, E. & Sreenivasan, K. R. (Springer, New York).

↵
Aldana, M. & Cluzel, P. (2003) Proc. Natl. Acad. Sci. USA 100 , 87108714. pmid:12853565

↵
BarYam, Y. & Epstein, I. R. (2004) Proc. Natl. Acad. Sci. USA 101 , 43414345. pmid:15070719

↵
Li, F., Long, T., Lu, Y., Ouyang, Q. & Tang, C. (2004) Proc. Natl. Acad. Sci. USA 101 , 47814786. pmid:15037758

↵
Derrida, B., Gardner, E. & Zippelius, A. (1987) Europhys. Lett. 4 , 167173.
 ↵

↵
Mélin, R., Anglès d'Auriac, J. C., Chandra, P. & Douçot, B. (1996) J. Phys. A 29 , 57735804.
 ↵
 ↵
 ↵
 ↵
 ↵

↵
Stauffer, D., Aharony, A., da Fontoura Costa, L. & Adler, J. (2003) Eur. Phys. J. B 32 , 395399.

↵
Maslov, S. & Sneppen, K. (2002) Science 296 , 910913. pmid:11988575

↵
Zhou, H. & Lipowsky, R. (2004) Lecture Notes Comput. Sci. 3038 , 10621069.
Citation Manager Formats
More Articles of This Classification
Physical Sciences
Related Content
 No related articles found.
Cited by...
 No citing articles found.