Flat-head power-law, size-independent clustering, and scaling of coevolutionary scale-free networks

Abstract

Scale-free topology and high clustering coexist in some real networks, and keep invariant for growing sizes of the systems. Previous models could hardly give out size-independent clustering with self-organized mechanism when succeeded in producing power-law degree distributions. Always ignored, some empirical statistic results display flat-head power-law behaviors. We modify our recent coevolutionary model to explain such phenomena with the inert property of nodes to retain small portion of unfavorable links in self-organized rewiring process. Flat-head power-law and size-independent clustering are induced as the new characteristics by this modification. In addition, a new scaling relation is found as the result of interplay between node state growth and adaptive variation of connections.

Graphical abstract

Keywords

scale-free network / flat-head power-law / size-independent clustering / scaling relation / coevolution

1 Introduction

Recently, complex network models are often made up to describe real systems. Nodes in a network represent individuals in the system and links represent relations among them. Scale-free network (SFN) [1] as a sort of typical model is characterized by power-law degree distribution: p(k)\sim k^{-\gamma } with exponent \gamma \in (2.0,3.0), which is verified by many analytical derivations and numerical simulations [2, 3]. However, on one hand, for some empirical works [4–7], degree distribution on a double-log plot always appears like a hockey stick that has a flat head connected by a straight body, quite different from a perfect power-law line. It demands an appropriate explanation instead of long-term ignorance. On the other hand, the clustering coefficient of a network, the average probability for any two neighbors of an individual to be linked together, is usually in the magnitude of {10}^{-1} for real systems, and it does not obviously depend on the growing size of a network [8–12]. However, it cannot be obtained in some famous analytical deviations for SFN accompanied with ideal power-law distribution of degrees. Two points of deviations motivate us to look for new scheme to mend the gap between theoretical and empirical results.

In early development of complex network research, dynamics on networks and dynamics of networks are separated. People always consider how topology determines the collective behavior of nodes of a network that is undergoing gradual change for more precise investigation. For many phenomena, such as academic art creation [13], global climate fluctuations [14], financial transactions [15], and synaptic plasticity of neural networks in the brain [16–18], both the structure and functions emerge from the same process in which time-dependent individual states and local interactions of nodes feedback with each other. Therefore, various co-evolutionary models [19–29] of networks are presented lately, and it becomes a hot topic nowadays [30–37]. Unfortunately, rarely could one see self-organized mechanism that results in flat-head distribution of scale-free networks with functional features accompanied simultaneously. Our recent model [29] based on generalized principle of competitive exclusion served a plausible choice of coevolutionary mechanism that yields both topological structure and dynamic behavior from the same process. However, it shares a common drawback of some previous scale-free network models, i.e., decaying clustering coefficient: C(N)\sim N^{-\theta } with \theta \approx 1.24, in contrast to many size-independent empirical results [2, 8–12].

In this paper, we revisit degree distribution and clustering coefficient from a new angle of view. The iteration rules in Ref. [29] are modified to fit for empirical results of real systems [4–7]. More precisely, we suggest a new mechanism to produce scale-free networks with flat-head degree distribution and size-independent clustering coefficient and reveal coevolution effect by a new scaling relation combining topological controlling parameter and average level of node states.

2 The coevolutionary model

Members in diverse systems share a generic nature, i.e., to behave differently from others under the pressure of competition, which is concluded as the generalized principle of competitive exlusion [29]. We set-up the present model through following iteration rules based on this principle. (1) Network growth starts from a small complete graph with m₀ nodes. Each node i on joining the network was assigned an initial state with a random real number w(i) uniformly distributed in the range (0,1). When a new node i^{\prime } is added to the preexisting network at each time step, it gives out m edges to old nodes arbitrarily [see Fig. 1(a)]. At every step, each node i counts \overline{w(i)}, the average of state values w(j),(j\ne i), over its nearest linked neighbors j. From them, it picks up the one whose w(j) makes the maximum distance from the average \overline{w(i)}, which is called J_{\max }(i) corresponding to \max |w(j)-\overline{w(i)}|, then a randomly selected node j among the nearest neighbors of i is chosen as the offspring of J_{\max }(i), called J_{\mathrm{sed}}(i). Different from seceder model [38, 39], it is kept at its own site, and its state value is updated as w(J_{\mathrm{sed}}(i))=w(J_{\max }(i))+\delta, where random number \delta \in (0,1) is also uniformly distributed. Obviously, w(i) here can be accounted as a time-dependent nondecreasing fitness [40]. (2) For the newcomer node i^{\prime } at every step, together with its fellows that are ‘young’ enough (i.e., i^{\prime }-i⩽\mathrm{\Delta }I), where \mathrm{\Delta }I is a given integer constant implicating aging effect [41] (hereafter, we call them I altogether for convenience), search J_{\mathrm{sed}}(j) for all I^{\prime }\text{s} neighbors j. An edge linking such node I and its neighbor j is removed under the conditions and [see the crossed edge in Fig. 1(b)], where h is a given value of threshold. Then, a new edge is added between node J_{\mathrm{sed}}(j) and I simultaneously [see dotted lines in Fig. 1(b)] if w(J_{\mathrm{sed}}(j))/w(I)⩾h. Of course, double links and self-loops are forbidden. Finally, if any node i becomes isolated due to edge-cutting, directly link it to its J_{\mathrm{sed}}(i). Note here that “and” replaces “or” in our last model [29].

Different from the last model, we take a stronger constraint on removing an old link between nodes i\to j hence rewiring link from node I to its neighbor j with smaller probability than in the old mechanism with rule “or”. That is, we demand a new condition for removal: both ratios less than h for one over the other are needed, which means that the difference between node j and I is relatively not large enough; while in our last model, removal happens when either one ratio or the other is less than h, which facilitates more rewiring activities in the coevolution. Obviously, nodes I has a little inert property to retain old correlations in the present mechanism. We will see this as modification from primitive rule that contributes dramatic change of coevolving results.

The coevolutionary mechanism is abstracted from observation of practical systems. In art creation, people have a generic tendency to create new works so that they distinguish themselves from others. In scientific research, sparks from a collision of opinions with large difference often result in creation. Scholars are often under the pressure to publish new papers. However, papers with the same or very similar viewpoints, methods, and results to existing ones have less chance to be published. Obviously, the competition exclusion promotes speciation and prosperity of scientific research.

Suppose a graduate student just starts his academic career from a certain topic, usually, he has to focus on some papers after extensive searching with limited time, and often, he extends his reading to references of them. Generally speaking, he needs to pay more attention to ones with sharp contrasts against his knowledge background [w(i)], and understand recently published literature [w(J_{\mathrm{sed}}(j))] to inspire new ideas for his own paper. However, he may be restrained within the ability of his understanding in the reading. Therefore, we assume a suitable range of threshold ratios (h) within which papers with state values w(J_{\mathrm{sed}}(j))⩾hw(i) would be read by the learner I. Moreover, papers in selective reading based on one’s local sight are likely to be cited, forming an increase in the in-degree of a citation network. On the opposite side, papers [on the node state w(j)] that have small difference from w(I) [too low ratio of w(j)/w(I)], and vice versa, are less cited [the link between node I and j is cut in Fig. 1(b)]. Finally, a recently updated node state [w(J_{\mathrm{sed}}(i))] would be more attractive to a failure (an isolated) node. It is not strange that this mechanism can fit well to empirical results of citation networks [42, 43] and numerical simulations [44] with exponent \gamma \sim 2.0 for in-degree distribution, as seen in Ref. [29].

3 Simulation results

Numerical simulations with constrained growing iteration rules demonstrate essential power-law degree distribution of the network. Figure 2 shows typical flat-head behavior with scale-free degree distribution in the main body, which implies that a relaxation of deterministic rules for rewiring unsuitable links to form a better one contributes the flat-head distribution. Empirical results from some real systems may imply more randomness of interactions among individuals compared with other ones with perfect power-law distributions. That is, individuals in such a system tend to keep minor portion of old relations due to their inert property despite of the tendency of breaking down. In Fig. 2, one can see that slopes γ of power-law for main bodies of degree distributions increase essentially with thresholds h and get saturated near \gamma \sim 2.89 with h\sim 7.0 or 8.0. Correspondingly, in our last model, it is difficult to find good scale-free behavior for too small (h⩽2.0) or too large (h>8.0) thresholds. Both old and new mechanisms show that γ increases with h within the valid range of suggested coevolution rules. However, very large thresholds do not yield suitable scale-free topology since it demands connection between node states with unreasonable difference, say, for example, in the problem of citation, a beginner could not understand a very profound literature. Therefore, slope-growing of descent degree distribution and its termination are qualitatively understandable.

The topological evolution of the growing network with the same h is stable, showing the same exponent γ of power-law for different sizes N (N=4000, 5000, 6000, 7000, 8000, and 9000,h=3.0, with \gamma =2.33 for the main bodies of these degree distributions), which is shown in Fig. 3. Note that it is plotted based on one run of simulation, without any ensemble average. Moreover, the stability is also verified for all thresholds that appeared in Fig. 2.

Meanwhile, a beneficial by-product emerges together with such a distribution. Averaged clustering coefficient C of the network is at least one order higher than that from unconstrained mechanism although it is not yet as large as that found in real networks, and it almost does not decrease on the growing size of the network as seen in previous models including our last one (see square blocks in Fig. 4). Note that sized-independent C is a long anticipated result that is absent in many analytical models. Some models provide coexistence of the scale-free topology and high clustering coefficient [9, 45–47] but with global message demanded instead of self-organized mechanism, as in the present model.

Apart from novel topological properties, the present mechanism also produces a functional feature through self-organized coevolution. It is expected that the average level of node states relies on threshold h which governs the topology of the network when it grows with the size N (number of nodes). To check our expectation, we define the average value T as follows:

\begin{array}{}\text{(1)}& T={\displaystyle \sum _{i=1}^N}{w}_i^2/N\end{array}

Moreover, we plot T^{\alpha }h against α in Fig. 5. It is found that T^{\alpha }h is independent on h near \alpha =1/2. Therefore, relation T^{1/2}h(N) shows approximate parallel lines with the slope \beta =1.18\pm 0.12 in Fig. 6, which implies an approximate scaling relation from our primitive simulation for the average level of node states:

\begin{array}{}\text{(2)}& T\sim h^{-1/\alpha }{N}^{\beta /\alpha }f(h_0)\end{array}

where \alpha =1/2, \beta =1.18\pm 0.12, h₀ is a constant, and f(x) is a universal function. In the specific case of citation networks, T may act as a collective measure combining average number affiliated to each impact factor of cited papers in a network characterized by a suitable parameter h. It implies assortative property between linked papers through citations, which is anticipated to be tested by careful rectifying of empirical data.

4 Summary

In conclusion, scale-free property of networks may come from the coevolution mechanism of interactions between individuals in a system. Time-dependent node states and varying links corresponding with them feed back each other, which results in both dynamic topology and function of a network. In particular, the flat-head power-law distributions of some empirical networks can be understood with constrained rewiring rule in the present mechanism. In addition, size-independent clustering coefficient is simultaneously realized. Increasing average level of node states is found to scale with topological threshold of correlations. They are all induced from the modification to the mechanism of coevolution in our recent model by taking inert property of nodes for rewiring links into account. Interestingly, high and size-independent clustering coefficient in many real networks is attributed to hierarchical and modular structure in networks [8–10]. However, we have not introduced such type of structures explicitly in the present model. Therefore, it would deserve further investigation to see whether the mechanism could lead to an indirect approach to these structures. Moreover, we expect more application to the analysis of practical complex systems.

References

[1] A.-L. Barabasi and R. Albert, Science, 1999, 286: 509

[2] R. Albert and A.-L. Barabasi, Rev. Mod. Phys., 2002, 74: 47

[3] S. N. Dorogovtsev and J. F. F. Mendes, Adv. Phys., 2002, 51: 1079

[4] A. Clauset, C. R. Shalizi, and M. E. J. Newman, SIAM Review, 2009, 3: 661

[5] A.-L. Barabasi, R. Albert, and H. Jeong, Physica A, 2000, 281: 69

[6] H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A.-L. Barabasi, Nature, 2000, 407: 651

[7] A.-L. Barabasi, H. Jeong, Z. Neda, E. Ravasz, A. Schubert, and T. Vicsek, Physica A, 2002, 311: 590

[8] E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and A.-L. Barabasi, Science, 2002, 297: 1551

[9] E. Ravasz and A.-L. Barabasi, Phys. Rev. E, 2003, 67: 026112

[10] A.-L. Barabasi, E. Ravasz, and Z. Oltvai, Lecture Notes in Physics, 2003, 625: 46

[11] E. Pieroni, S. de La Fuente, and van Bentem, Proteomics, 2008, 8: 799

[12] B. D. Camillo, G. Toffolo, and C. Cabelli, Ann. New York Acad. Sci., 2009, 1158: 125

[13] M. E. J. Newman, Proc. Natl. Acad. Sci. USA, 2001, 98: 404.

[14] J. Masoliver, M. Montero, and G. H. Weiss, Phys. Rev. E, 2003, 67: 021112

[15] A. A. Tsonis and P. J. Roebber, Physica A, 2004, 333: 497

[16] V. M. Eguiluz, D. R. Chialvo, G. A. Cacchi, M. Baliki, and A. V. Apkarian, Phys. Rev. Lett., 2005, 94: 018102

[17] S. Song, K. D. Miller, and L. F. Abbott, Nat. Neurosci., 2000, 3: 919

[18] J. M. Montgomery and D. V. Madison, Trends Neurosci. 2004, 27: 744

[19] A. Barrat, M. Barthelemy, and A. Vespignani, Phys. Rev. Lett., 2004, 92: 228701

[20] S. Bornholdt and T. Rohlf, Phys. Rev. Lett., 2000, 84: 6114

[21] Y. B. Xie, W. X. Wang, and B. H. Wang, Phys. Rev. E, 2007, 75: 026111

[22] M. G. Zimmermann, V. M. Eguluz, and M. S. Miguel, Phys. Rev. E, 2004, 69: 065102(R)

[23] P. Holm and M. E. J. Newman, Phys. Rev. E, 2006, 74: 056108

[24] M. Liu and K. E. Bassler, Phys. Rev. E, 2006, 74: 041910

[25] C. S. Zhou and J. Kurths, Phys. Rev. Lett., 2006, 96: 164102

[26] J. M. Pacheco, A. T. Traulsen, and M. A. Nowak, Phys. Rev. Lett., 2006, 97: 258103

[27] P. Fronczak, A. Fronczak, and J. Holyst, Phys. Rev. E, 2006, 73: 046117

[28] C. P. Zhu, S. J. Xiong, Y. J. Tian, N. Li, and K. S. Jiang, Phys. Rev. Lett., 2004, 92: 218702

[29] C. P. Zhu, T. Zhou, H. J. Yang, Z. M. Gu, D. R. He, and B. H. Wang, New J. Phys., 2008, 10: 023006

[30] T. Gross and B. Blasius, J. R. Soc. Interface, 2008, 5: 258

[31] O. Graeser, C. Xu, and P. M. Hui, Europhys. Lett., 2009, 87: 38003

[32] C. Meisel and T. Gross, Phys. Rev. E, 2009, 80: 061917

[33] A. L. Do, L. Rudolf, and T. Gross, New J. Phys., 2010, 12: 063023

[34] L. X. Zhong, F. Ren, T. Qiu, J. R. Xu, B. H. Chen, and C. F. Liu, Physica A, 2010, 389: 2557

[35] H. H. Jo, H. K. Lee, and H. Park, Phys. Rev. E, 2010, 81: 066108

[36] M. Li, S. G. Guan, and C. H. Lai, New J. Phys., 2010, 12: 103032

[37] B. Wu, D. Zhou, Q. Luo, L. Wang, and A. Trausen, PLOS One, 2010, 5: e11187

[38] P. Dittrich, F. Liljeros, A. Soulier, and W. Banzhaf, Phys. Rev. Lett., 2000, 84: 3205

[39] A. Soulier and T. Halpin-Healy, Phys. Rev. Lett., 2003, 90: 258103

[40] S. N. Dorogovtsev and J. F. F. Mendes, Phys. Rev. E, 2001, 63: 056125

[41] S. N. Dorogovtsev and J. F. F. Mendes, Phys. Rev. E, 2000, 62: 1842

[42] D. Braha and Y. Bar-Yam, Phys. Rev. E, 2004, 69: 016113

[43] C. R. Myers, Phys. Rev. E, 2003, 68: 046116

[44] A. Vazquez, Phys. Rev. E, 2003, 67: 056104

[45] P. Holme and B. J. Kim, Phys. Rev. E, 2002, 65: 026107

[46] T. Zhou, G. Yan, and B. H. Wang, Phys. Rev. E, 2005, 71: 046141

[47] S. L. Bu, B. H. Wang, and T. Zhou, Physica A, 2007, 374: 864

Rights & permissions

©Higher Education Press and Springer-Verlag Berlin Heidelberg 2011