Nov 22, 2006 - which is the main characteristic of a scale-free network. A very small .... monitor the probability Fann(kmax), i.e. the fraction of ev...

0 downloads 2 Views 209KB Size

arXiv:cond-mat/0611591v1 [cond-mat.dis-nn] 22 Nov 2006

Department of Physics, University of Thessaloniki, 54124 Thessaloniki, Greece (Dated: April 30, 2018) In this work we examine some characteristic properties of reaction-diffusion processes of the A + A → 0 type on scale-free networks. Due to the inhomogeneity of the structure of the substrate, as compared to usual lattices, we focus on the characteristics of the nodes where the annihilations occur. We show that at early times the majority of these events take place on low-connectivity nodes, while as time advances the process moves towards the high-connectivity nodes, the so-called hubs. This pattern remarkably accelerates the annihilation of the particles, and it is in agreement with earlier predictions that the rates of reaction-diffusion processes on scale-free networks are much faster than the equivalent ones on lattice systems. PACS numbers: 82.20.-w, 05.40.-a, 89.75.Da, 89.75.Hc

I.

INTRODUCTION

The A + A → 0 reaction is one of the most fundamental annihilation processes, with many applications [1]. In a number of papers [2, 3, 4] this reaction was studied on scale-free networks, both computationally and analytically. In a recent Letter [2] we reported some unusual properties of reaction-diffusion processes taking place on scale-free networks. These networks represent a special class of random networks, where the probability that a node is connected to k other nodes of the network follows a power-law form: P (k) ∼ k −γ ,

(1)

where the value of the exponent γ usually lies in the range 2 < γ < 4. A large number of systems from markedly different disciplines have been found to fall in this class, and new systems are added continuously in the list [5, 6]. This ubiquity explains the intense interest devoted to the study of the complex networks field. The unusual structure of the scale-free networks has been shown to strongly modify the properties of dynamic processes, where particles move from node to node along the existing links, as compared to the same heavily-studied processes on lattice systems or continuous space. Reaction-diffusion mechanisms are a frequently encountered mechanism for kinetics, where particles diffuse in a space and react in a predefined way upon encountering other particles. For example, during the A + A → 0 process, particles of the A type diffuse and annihilate when they collide with other particles of the same type. In Euclidean lattices, the simplest mean-field approach predicts a linear increase of the inverse particle concentration ρ(t) with time t. A large number of studies [7, 8, 9], though, demonstrated that the density actually scales as 1 1 ∼ tf , − ρ(t) ρ0

(2)

where f < 1, and ρ0 is the initial particle concentration at time t = 0. In a space with dimensionality d this

exponent equals f = d/dc , for d ≤ dc and f = 1 for d > dc . The critical dimension for the A + A reaction is dc = 2. This ‘anomalous’ behavior has also been observed when the substrate of diffusion has different geometry, such as a fractal structure [10], where f = ds /dc , and ds is the spectral dimension. The maximum value of f in all the above cases has been f = 1. In scale-free networks, though, we recently found numerically that the process follows a different mechanism. For networks with γ ≤ 3.5, the concentration decay still follows a power law, which for a short interval is described initially by f < 1, but soon after that exhibits a crossover to a power law with an exponent f > 1. This is a clear indication for the rapid acceleration of the process, which we attributed mainly to the existence of the hubs. Following this, Catanzaro et al. [3] developed a theoretical framework for ‘uncorrelated’ networks (i.e. networks with no degree-degree correlations, see [11]). They predict a behavior t1/(γ−2) , 2 < γ < 3 1 ∼ . (3) ln(t), γ=3 ρ(t) t, γ>3

A detailed comparison between the two models was recently presented in [4], where it also became evident that the exact behavior of the particle concentration depends on details of the structure, such as, for example, the minimum number of links on a node. In the present work we study the reaction-diffusion A + A → 0 model on scale-free networks, with emphasis on the nodes where the annihilation events take place on, and we try to better understand the mechanism that leads to this new type of behavior. II.

THE MODEL

The networks that we use in our simulations are prepared with the standard configuration model [12]. Initially, an integer k value representing the number of links is assigned from a random distribution obeying Eq. 1 to every one of the N nodes in the network. Random pairs

2 0

10

-1

10

-2

10

Fann(k)

of links are chosen and connect two nodes, but double links and self-connections are not allowed. This network creation method may create a certain number of separated clusters (depending on the value of γ). We isolate and use only the largest cluster of the network, where the particles are allowed to diffuse. During the reaction-diffusion process the number of particles M (t) in the system is reduced with time, and we denote with ρ(t) the particle concentration at time t. The initial particle concentration is ρ0 . A number of N0 = ρ0 N particles are placed on randomly selected nodes (in simulations of this work we use ρ0 = 0.5). Then, we randomly choose one particle and pick one of the neighboring nodes where this particle is located at. If this new node is empty, the particle moves and occupies its new position. If this node is already occupied, then the two particles annihilate and are immediately removed from the system. Time is advanced inversely proportionally to the current number of particles, by 1/M (t). We repeat this procedure by continuously selecting, moving and (possibly) annihilating particles. We perform 100 different realizations of the walk on different networks of size 106 nodes each. The largest cluster on these networks is, of course, smaller and spans 35% to 100% of the system nodes, depending on the value of γ.

-3

10

2.0

-4

10

2.5

-5

10

3.0

3.5

-6

10

0

10

1

10

2

10

3

k

10

4

10

5

10

FIG. 1: Probability, Fann (k), for an annihilation event to take place on a node with k links as a function of k, during a process of t = 100 steps. Open symbols are averages over 100 scale-free networks with γ=2.0, 2.5, 3.0 and 3.5 (top to bottom, shown in the plot), of N = 106 nodes each. The data have been logarithmically binned for k > 10. Lines represent Eq. 4, with the corresponding exponent 1 − γ for each case. We also present unbinned data (dots) for the case of γ = 2.0.

ing to a k-node, i.e. III.

RESULTS

In order to gain insight into the reaction process, and given that the substrate of the diffusion is very inhomogeneous, we try to understand the nature of the nodes where the annihilations take place. The connectivity of the nodes in the network varies largely from node to node, but the great majority has a small number of connections, which is the main characteristic of a scale-free network. A very small number of nodes are well-connected (the hubs), and the existence of the hubs has been shown to be the main reason behind most of the unusual properties reported for the scale-free networks. In this context, we have performed simulations of the A + A reaction-diffusion problem on scale-free networks of various γ exponents. After t = 100 steps, when the particle concentration has diminished to small values, we calculate the percentage of annihilation events Fann (k) that took place on a node with k links. Figure 1 shows Fann (k) as a function of k. The raw data for Fann exhibit a kink at values of k around 100 to 1000, above which the curve increases monotonically with increasing k. We present one such curve in Fig. 1 for the case of γ = 2.0. This feature (which is also size-dependent) is a numerical artifact, due to the rarity of nodes with very large degree k, and is removed when the data are binned. The four curves in the figure are the result of logarithmic binning at degrees k > 10. In a mean-field treatment of a network with no degreedegree correlation we expect that the number of events would be proportional to the total number of links lead-

Fann (k) ∼ kP (k) ∼ k 1−γ .

(4)

The exponent 1 − γ is verified in all four cases, as can be seen in Fig. 1, for the intermediate to large k regime. The result of Eq. 4 and the presented curves show that even though most of the events take place on low-k nodes, which comprise most of the network, the probability for annihilation at the hubs is significantly larger than their relative appearance in a network. The behavior seems also not to be influenced by any degree-degree correlation in the network. The probability that nodes with low connectivity are connected to a hub can in fact be larger than the one predicted for a completely uniform distribution [11], due to the avoidance of double links and self-connectivity. The importance of the hubs can be made explicit if we ask what is the average number of events R(k) on a single node with k links, i.e. R(k) =

Fann (k) . P (k)

(5)

According to Eq. 4 we expect a linear increase with the number of links k, since R(k) ∼ k 1−γ /k −γ ∼ k. This behavior is verified in Fig. 2, at least for large k values. The slope of γ = 2 seems to be slightly different than the other curves, but this can be attributed to the increasing number of hubs at this γ value, where the network has a very small diameter. The curves in Fig. 2 span many decades on the y-axis manifesting a very different role of nodes with different degrees. The case of γ = 2 is

3 5

10

slope=1

4

10

γ=3.0

3

(a)

γ=2.5 10

γ=2.0

10

-1

γ=3.5

2

R(k) 101

Fann(k=1)

10

γ=3.5

0

10

10

γ=3.0

-2

γ=2.5

-1

10

γ=2.0

-2

10

10

-3

10

0

10

1

10

2

10

3

k

10

4

10

5

-3

10

(b)

also the borderline value that separates networks with finite degree distribution moments from networks with infinite moments. The diameter of networks with γ < 2 is extremely small and the hubs connect practically the entire network within a few steps. In such networks with γ < 2, which are difficult to simulate numerically, we expect that the annihilation process will be exponentially fast and that almost all the reaction activity will take place on the hubs or on their immediate neighbors. In a typical walk of t = 100 steps about 2 × 105 events are observed. If we focus on a particular node with a small degree we see that there is much less than one annihilation event occuring on this node during the process. On the contrary, more than 104 events occur at the hubs having k ≃ 105 links. We, thus, conclude from Figures 1 and 2 that a hub is a much more active element in a network than any other node, although the majority of events still occurs over the large number of low-k nodes. The results until now concerned the entire process after averaging over the first t = 100 steps. We now turn to the time evolution of the diffusion-reaction mechanism. In Fig. 3a we can see how Fann (k = 1) varies with time. For all γ values the probability starts initially with a certain value and decreases monotonically with time before stabilizing to a much lower value. For γ = 3 and γ = 3.5, where hubs are not very strongly connected, the probability goes down to a value of 0.02 even for the longer times displayed. For γ = 2 and γ = 2.5, though, the probability that an annihilation occurs on a node with k = 1 practically vanishes. This picture is reversed when we monitor the probability Fann (kmax ), i.e. the fraction of events taking place on the single most connected node of the network during the time interval [t, t+1] over the total number of events that occured during the same interval. Figure 3b suggests that now Fann (kmax ) starts with low values but continuously increases as time evolves. Note

10

Fann(k=kmax)

FIG. 2: Average number of annihilation events per node, R(k), with k links as a function of k, during a process of t = 100 steps. Curves are averages over 100 scale-free networks with γ=2.0, 2.5, 3.0 and 3.5, of N = 106 nodes each.

-1

γ=2.0

γ=2.5 10

-2

γ=3.0 γ=3.5

10

-3

1

10

100

time FIG. 3: Time evolution of the average probability (a) Fann (k = 1) and (b) Fann (k = kmax ), for networks with varying γ exponents.

that for networks with γ < 3 more than 10% of the events at long times take place on this node alone. In Fig. 4 we present the time evolution of the entire Fann (k) distribution for different γ values. The distribution at t = 1 has a form similar to that of Fig. 1. When γ = 2, and as time evolves, the low-k part decreases and the large-k part increases. Asymptotically, the distribution tends to uniform and for t ≃ 40 there is no event taking place at nodes of small connectivity. For γ = 2.5 the picture is similar, but at t = 100 the distribution has not yet spread uniformly over the entire k range. For γ ≥ 3 the right wing increases with a slower rate than when γ < 3, and always remains significantly lower than the small-k part, at least for the early time scale that we observe in our current work. Notice also that at time t = 100 the process on networks with different γ lies in different stages of the ρ(t) evolution, as can be seen in Fig. 1 of Ref. [2]. For γ = 2 the concentration has almost diminished to zero, while for γ = 2.5 we are well inside the power law regime with f > 1. When γ = 3.0 we are located close to the crossover point between the two power law regimes, and for γ = 3.5

4 0

8

10

(a) γ=2.0

(b) γ=2.5

-1

(b) γ=2.5

20

g(L)

-2

10

4

10

-3

10

t=1 t=5 t=10 t=40

-4

10

2

t=1 t=5 t=20 t=100

0

0

10

0

1

2

3

4

0

5

0

2

4

(c) γ=3.0

(d) γ=3.5

10

t=1 t=10 t=20 t=100

t=1 t=10 t=50 t=100

8

10

-3

10

(c) γ=3.0

6

g(L)

-2

g(L)

-1

4

-4

10

2 0

10

1

10

2

10

k

3

10

4

0

10 10

1

10

2

10

3

10

4

10

k

FIG. 4: Time evolution of the probability distribution Fann (k) for four different γ values (shown on the plot). Data have been logarithmically binned for k > 10. Each curve corresponds to different times displayed in the legends.

the concentration has not reached the transition point and still decays slower than linear. In Ref. [2] we had shown that during an A + A → 0 reaction particles tend to segregate. This is a very unusual type of behavior, since in regular Euclidean space the opposite effect (formation of depletion zone) is observed. We, thus, consider in more detail the cluster structure of the particles in the network. We have already seen (Fig. 3a of [2]) that the fraction QAA , defined as the number of the close contacts in the system over the total possible number of contacts, increases as a function of time (except for γ > 3), a clear indication towards particle segregation. In order to fully characterize the motion and the spatial distribution of the particles we now use the two-particle correlation function g(L), which we define as the number of particles at distance L over the number of particles at distance L when we assume an equal but uniform particle distribution. On random networks, this random distribution cannot be accurately estimated theoretically, as e.g. for simple lattices, due to the widely different local environment. In order to overcome this problem, for every network that we used and for every concentration encountered we placed a corresponding number of particles uniformly on this network and averaged over 20 different realizations. By calculating the average number of particles at distances L we were able to determine the value of the denominator. Thus, if the particles are randomly distributed in the network this quantity will be 1. If the particles tend to occupy nodes far from each other this fraction will be

0

0

10

5

6

8

10

L

L

10

Fann(k)

(a) γ=2.0

6

g(L)

Fann(k)

10

15

2.0 1.8 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.2 0.0

(d) γ=3.5

0

5

L

10

15

20

25

L

FIG. 5: Two-particle correlation function g(L) as a function of the distance L for different γ values (shown in the plot). The dashed line represents the uniform distribution limit g(L) = 1. Thicker curves correspond to earlier times. Times used in each plot: (a) t =3, 8, 20, 30. (b) t =6, 25, 100, 150, (c) t =12, 72, 500, 850, and (d) t =15, 140, 1800, 3400.

g(L) < 1, while g(L) > 1 shows that particles are clustered in close contact to each other. The first three plots in Fig. 5 (corresponding to γ ≤ 3) describe a picture where particles break their initial uniform distribution and cluster with an increasing rate. The average number of neighbors within a few steps is significantly high and increases with time, while the number of particles at longer distances are close to the meanfield assumption g(L) = 1. When γ = 3.5 the correlation function is more similar to a typical A + A reaction on a normal lattice. Initially, a depletion zone is created around the A particles. This depletion zone is retained for the duration of the process, with the difference that at longer times we observe an increase of particles concentration at moderate distances. This increase is, though, much smaller than for the case of γ ≤ 3.

IV.

SUMMARY

Summarizing, in the present study we focused on the details of the diffusion, such as the spatial organization of the particles and the time evolution leading to an annihilation reaction, with a scale-free network as the substrate. The majority of the particles annihilate on the low connectivity nodes. This happens mainly at early times, where the static distribution of particles on the network is the dominant factor. The particles annihilate in the

5 vicinity of their initial neighborhood, which on average includes mostly low-degree nodes (since the number of such nodes in the system is large). At later times, when a small number of particles remain in the system, diffusion starts to play an increas-

ingly important role. Particles encounter each other mainly on nodes where diffusion directs them to, i.e. on the hubs[13]. Thus, although the percentage of the hubs in the network is very small most reactions take place on them and they dominate the process at longer times.

[1] D. ben-Avraham and S. Havlin, Diffusion and reactions in fractals and disordered systems (Cambridge University Press, Cambridge, 2000). [2] L.K. Gallos and P. Argyrakis, Phys. Rev. Lett. 92, 138301 (2004). [3] M. Catanzaro, M. Bogu˜ n´ a, and R. Pastor-Satorras, Phys. Rev. E 71, 056104 (2005). [4] L.K. Gallos and P. Argyrakis, Phys. Rev. E, 72, 017101 (2005). [5] R. Albert and A.-L. Barabasi, Rev. Mod. Phys. 74, 47 (2002). [6] S.N. Dorogovtsev and J.F.F. Mendes, Adv. Phys. 51, 1079 (2002). [7] A.A. Ovchinnikov and Ya.B. Zeldovich, Chem. Phys. 28,

215 (1978). [8] D.C. Torney and H.E. McConnell, J. Phys. Chem. 87, 1441 (1983); Proc. R. Soc. Lond. A 387, 147 (1983). [9] D. Toussaint and F. Wilczek, J. Chem. Phys. 78, 2642 (1983). [10] S. Havlin and D. ben-Avraham, Adv. in Phys. 36, 695 (1987). [11] M. Catanzaro, M. Bogu˜ n´ a, and R. Pastor-Satorras, Phys. Rev. E 71, 027103 (2005). [12] M. Molloy and B. Reed, Random Struct. Algor. 6, 161 (1995); Comb. Probab. Comput. 7, 295 (1998). [13] L.K. Gallos, Phys. Rev. E 70, 046116 (2004).