Chapter1 Introduction to Damage Spreading

Chapter1. Introduction to Damage Spreading

1.1 What Is Damage Spreading

1.1.1The Concept of Damage Spreading

To some physicists, the shape of a snowflake, the roughness of a crack surface, corroding process in iron, virus spreading and some economic and social phenomena are just some random growth processes. In order to describe these processes, many mathematical models, such as percolation, have been put forward. Damage spreading (DS) is no more than a powerful growth model, which simulates the time evolution of perturbation spreading throughout a cooperative system by adopting some evolution rules (Glauber dynamics, heat bath dynamics, Kawasaki dynamics, etc.).

It is well known that , how a perturbation spreads throughout a cooperative system composed of interacting subunits is a question that arises in many fields of research. To obtain the answers to this question, we need a useful technique to descript the evolution of a small perturbation (termed the damage) spreading through a cooperative system. Damage spreading (DS) is one of such techniques , which has been shown very successful.

Now we show how damage spreading works. Firstly, we simulate a system until it is in equilibrium. Then, at time t=0, we make a replica of this equilibrium configuration, and create a single spin flip (“initial damage”) in the center of the replica. Thenceforth, both the original system (“control”) and its damaged replica evolve by use of identical dynamics-e.g.,the same random numbers are used for both systems.

As t evolves, our initial single-site damage generally results in a region of the cooperative system in which the spins s i(t) differ in control system. We call this region the “damage”, and measure this damage quantitatively by counting the number of spins in the perturbed system that differ from their counterparts in the control system. We find that sometimes the damage remains localized to a relatively small region of the lattice, and sometimes it spreads through the entire cooperative system (since each spin is interacting with its neighbors). In our comparison of the control and its replica, overall averages-like the net number of up spins or magnetization-will generally remain unaffected by small initial damage; thus our study concerns microscopic details of a spin configuration rather than macroscopic averages.

The concept of DS was first introduced in the context of biologically motivated systems by Stuart Kuffman in 1969,now it has been extensively applied in the study of dynamical properties of statistical models ,especially in magnetic models, like Ising,Clock,Potts,spin glass,etc.

This technique has also been applied in the study of Coulomb glass. The combined influence of disorder and long-range interactions on the properties of many-particle systems has been a subject of great interest for some time. The behavior of strong localized correlated electrons in disordered insulators is especially complicated, both experimentally and theoretically. Thus progress has been slow since the first investigations. DS provides an important method for this study.

In terms of application, the significance of DS can be found in its relevance in the research in many economic and social phenomena. For instance, many social systems can be modeled by letting spin up/down denote different opinions or preferences. In such models, a ferromagnetic interaction is interpreted as two people who prefer to agree, while an antiferromagnetic interaction means that they want to disagree. A magnetic field adds a bias that can be interpre ted as ……prejudice?? or……stubbornness,?? while the randomness induced by a finite temperature can be seen as ……free will.?? On the other hand, it may be useful in business applications when one wants to estimate and thereby control the damage incurred by a sudden change of alliance of a particular site on the supermarket network, or shopping mall, from company Red to company Blue. The study of damage spreading on point patterns using different dynamics may help us to get a better theoretical understanding of the competitions between companies in a planar network of shops or centers.

1.1.2 Measurement of the Damage Spreading: Hamming Distance

For a given Ising system , the Hamiltonian considering of only the nearest-neighbor interactions is given as

∑-=>

(1-1a)

where J ij >0 is the ferromagnetic exchange interaction coefficient between the nearest-neighbor sites i and j , i.e., the interaction between the nearest-neighbor agents (polygons or nodes). In most cases, we can we ignore the dependence of J ij on the two sites (i,j) ,thus we take J ij =J as a constant. In this case, (1-1a) changes into

∑><-=j i j i s s J H ,.

(1-1b)

We consider two identical systems A and B. First, we evolve system A for a long time to reach equilibrium, then system B, which is a replica of system A, is made. At t =0, the spin in the center cell of the lattice B is flipped (damaged) and fixed for all t>0. The Hamming distance (or damage) in phase space for the trivalent structures is calculated by

)(M )t (D M i )t (s ),t (s B i A i ∑-==1

11δ, (1-2) where )}({t s A i and )}({t s B i are the two spin configurations of the system which subject to the same thermal noise and the same set of random number. Here M is the number of the total spins on the lattice studied.

1.1.3 Monte Carlo Rules: Dynamics

System evolutes under some dynamics . Most commonly used dynamics in the damage spreading study are as follows:

(1).Glauber dynamics

Glauber dynamics makes the evolution of the spin configuration s={s i (t)}, with the

transition probability of flipping spin i given by

()m i n 1,e x p i i B E w s k T ?????=-?? ?????. (1-3)

Here ΔE i is the change in energy when spin i is flipped. Glauber dynamics corresponds to a situation where the system is in thermal equilibrium with a heat reservoir.

(2).Kawasaki dynamics

Kawasaki algorithm is the simplest order parameter conserving dynamics consisting of exchanging spins on nearest-neighbor sites (spins) i and j with the probability

0,0()1,0ij ij ij for E s for E ω?≤?=??>?

, (1-4) To fulfill the Kawasaki process, we can have many updating rules, for example, the heat bath probabilities

()ij B ij

ij

B B E k T ij E E k T k T e s e e

ω?-??-=

+ , (1-5) the Glauber probabilities )]exp(,1min[T k E B ij

ij ?-=ω,and the usual Kawasaki

dynamics Eq.(1-4).Eq.(1-4) is also called T =0 K-dynamics, implying that it is the zero-temperature limit of Eq.(1-5). Obviously, when T =0, (1-5) reduces to (1-4). If the change in energy ij E ?after exchanging the neighboring spins i and j is positive, the new configuration is automatically accepted. If it is negative, then the new configuration is not accepted. K-dynamics simulates a system subjected to a continuous flux of energy.

(3).Competing Glauber-Kawasaki dynamics

Combinating Glauber and Kawasaki (G-K) dynamics presents a weighted transition probability per unit time from state s to 's as

(,')(,')(1)(,')G K s s p s s p s s ωωω=+-.

(1-6)

We go through the M sites with a probability )()',(''2'21'11s s s i s s s s M i s s s s G M M i i ωδδδδω -=∑= (1-7)

or

''''11,(,')()i j j i M M M K ij s s s s s s s s i j s s s ωδδδδω<>=

∑ (1-8)

with ()i s ωis the probability of flipping spin i ., ()ij s ω is the probability of exchange between the nearest-neighbor spins i and j (given above) .

Combinating G- K dynamics is also called mixed G-K dynamics or competing G-K dynamics.

1.2 Damage Spreading: What Have We Learnt?

Many interesting results of DS have been reported since it was applied in statistical physics. Many elements which characterize the DS process have been considered in literatures, including the interactions (ferromagnetic, antiferromagnetic , spin glass ,etc.), the Monte Carlo rules (heat bath , Glauber , Metropolis, etc.). As for the lattice geometry, many work has been done on square , triangle ,hexagon, and other lattices. Recent years, much attention has been paid to the DS study on complex networks .

(1) Damage spreading phase transition

In the case of pure Ising ferromagnets, a sharp dynamical phase transition is observed and the dynamical phase transition temperature separates two phases: the frozen(order) and chaotic (disorder) states. In the frozen phase the spin distance is independent of the initial distance and vanishes rapidly while in the chaotic phase the distance remains finite for a long time. In the more complicated systems like fully frustrated, spin glass and XY model, a third phase between these two phases was found. It is called the intermediate phase where the distance does not vanish but becomes independent of the initial distance .

Many authors had discussed the relation between the DS transition temperature T d and the Curie temperature T c. This relation is of great importance. Till now, many methods have been suggested for the accurate determination of the DS transition temperature. A direct measure of the temperature dependence function of the averaged damage can be used, but not with high accuracy . On the other hand, one may

of damage to define T d . More reliable use the peak location of the fluctuation )

(T

D

estimate for the transition temperature can be obtained by using the finite-size scaling procedure. All these methods will become obsolete if we can find the relation between T d and T c. For the two-dimensional Ising model, it is shown that the heat-bath dynamics T d coincides with T c whereas for Glauber and Metropolis dynamics T d is near but smaller than T c . Unfortunately, satisfactory explanation for this relation between these two temperatures is still lacking.

(2) DS technique is less sensitive to statistical fluctuations but depends to a great extent on the dynamics chosen

Compared to conventional Monte Carlo methods, the DS technique is less sensitive to statistical fluctuations. But it is found that DS depends to a great extent on the dynamics chosen and, particularly for the “heat bath” dynamics, on the typ e of initial configurations. These properties are very important because they are contrary to the case of usual statistical Monte Carlo modeling, where all the dynamics give the same values for the magnetization, susceptibility and special heat, differing only in the convergence rate.

(3)DS is sensitive to the ways of updating

Nobre et al. investigated the damage spreading in the Ising model on a triangular lattice, for ferro- and antiferromagnetic interactions ,using Glauber dynamics. They employed two procedures for updating spins: the sequential and parallel ones. They found that :(a)The sequential algorithm leads to a dynamic transition at a temperature very close to the usual static critical temperature Tc in the ferromagnetic case, whereas in the antiferromagnetic problem, no transition is found, suggesting that the equilibrium phase transition and the frozen-chaotic one are strongly correlated.(b)The parallel recipe is not able to distinguish the two interactions, giving a similar dynamics transition for both, at a temperature which is considerably different from Tc. This implies that the use of parallel algorithms for updating spins is very questionable.

1.3 Moreabout Damage Spreading: Problems Unsolved

The first problem, as mentioned above, is the relation between T d and T c and how to present an reasonable explanation. In addition, how to determine T d is another

problem . It is well known that T c can be determined using Binder?s cumulant s, but

for T d ,we lack of such a tool. The third problem is about the definition and measure of the damageIt appears that DS is uniquely defined only if one specifies the Hamiltonian and the dynamic rule; there are also new and interesting phenomena that cannot be measured by Hamming distance. Hamming distance is too much averaged. Hamming distance is extensively accepted as a good measure because it can show a phase transition of the damage. Are there other measurements in the damage spreading process? To solve these problems ,we need further study to the damage spreading process.

1.4 Generalization of the Damage Spreading Method

The damage-spreading technique is a modification of the usual Monte Carlo method. The core idea of damage spreading is to look not at the time evolution of a single system but to compare the time evolutions of two systems which are subjected to the same thermal noise ,i.e., the same random numbers are used within the Metropolis algorithm. Usually, at the beginning of the simulation the occupation numbers of both systems differ only at a single site or at a few sites, e.g., a single column in a 2D lattice system.

Since both systems are thermodynamically identical, averages of equilibrium quantities will be the same for both systems. Microscopically, however, the two systems may evolve differently from each other. The central observable in

damage-spreading simulations is the Hamming distance D(t), which is the portion of sites for which the occupation numbers differ between the two systems. D(t), which measures the ……damage,?? is given by (1-2) for the Ising systems. We can generalize

the method to study the coulomb glass ,at that case the damage is defined as

(1-9)

where )(0t n i and )(t n c i are the occupation numbers of site i of the original system and the copy at Monte Carlo time t .

Recently, a scaling ansatz was suggested for damage spreading in the surface growth model and the essential dynamical scaling properties of kinetic surface roughening were obtained from the scaling ansatz.

The suggested scaling ansatz is briefly summarized as follows. Consider two systems A and B of growth. In system A growth begins with a flat surface, i.e., 0)0,(=r h A for any r on the substrate, whereas growth in system B begins with 0)0,(=r h B except at one point r 0, where 1)0,(0=r h B . The surfaces in A and B are allowed to grow under the same growth rule and under the same sequence of random numbers. Here h A ,h B means the surface height of system A and B at t .A damaged column at t is defined by the r at which ),(),(t r h t r h B A ≠. If a column at r d is damaged, the lateral damage-spreading distance //d and the vertical damage-spreading distance ⊥d of the column are defined by

(1-10)

where means the average surface height in system B. If the periodic boundary condition is imposed, then //d must satisfy //d

To study the dynamical scaling property of surfaces by damage spreading the main relation to focus on is the relation between ⊥d and //d or the function of ),(//t d d ⊥. Here ),(//t d d ⊥ means the average of ⊥d over the surviving damages which exist only at the lateral distance //d (or at //0d r r d ±=). The function ),(//t d d ⊥ should have all the detailed information on damage spreading in the

surface growth.

Since we are interested in the propagation of the initial perturbation, we define the damage spreading distance or propagation distance D as the maximum value among the distances between the damage sites and the original point r0, in other words ,the measure of the damage spreading in the above process can also be as follows

.(1-11)

The damage spreading technique can also be used to discuss the stability of the magnetic structure of nanoscopic arrays of monodomain ferromagnetic posts. Simulations are performed with the Pardavi-Horvath algorithm. The stability is considered on a plane (r,Ha), where r is the dispersion of the coercive field of the posts, and Ha is the amplitude of an applied, slowly varying sinusoidal magnetic field. The stability is understood as follows. Let us consider two identical arrays, A and B, under action of a slowly oscillating magnetic field. In one array, we flip the magnetic moment of one post. Then we start to observe the difference between the magnetic states of A and B. This difference can be conveniently written as the so-called Hamming distance in the configuration space. In theory of codes, the Hamming distance between two strings of bits is the number of different bits. Here it is the number of posts, which are magnetized oppositely in A and B. If this distance increases with time, we conclude that the system is not stable: one flip can destroy the magnetic state of the array.

To conclude, the core idea or key point of the damage spreading technique lies in the definition of “damage”. This “damage” is not realistic damage but a mathematic one instead. How to choose the measures to describe the process is of great importance, and different processes should have different measures. We will show this in chapter 12 once more, where we extent the damage spreading method to polymer morphogenetic.

References

Z.Z.Guo , Xiao-Wei Wu and Chun-An Wang, Pramana-journal of physics 66,

1067(2006).

Application of damage spreading on coulomb glass, see T.Wappler and T. V ojta,prb55,6272,1997.

Application of damage spreading on the surface growth model ,see Jin Min Kim，Youngki Lee and In-mook Kim，PRE54,4603,1996;Yup Kim and C. K. Lee，PRE62,3376,2000;Y up Kim，PRE64,027101,2001.

Application of damage spreading discuss the stability of the magnetic structure of nanoscopic arrays of monodomain ferromagnetic posts, see A. Kaczanowski, K.

Ku?akowski / Microelectronic Engineering 81 (2005) 317–322; A. Kaczanowski, K. Ku?akowski,Damage spreading in a periodic nanoarray of magnetic posts, Physica B 351 (2004) 1–4.