TLC-Chaos12 .pdf Synchronizability of small-world networks generated from ring networks with equal-distance edge additions Longkun Tang,1,2,a) Jun-an Lu,2,b) and Guanrong Chen3,c) 1School of Mathematical Science, Huaqiao University, 362021 Fujian, China 2School of Mathematics and Statistics, Wuhan University, 430072 Hubei, China 3Department of Electronic Engineering, City University of Hong Kong, Hong Kong, China (Received 11 January 2012; accepted 18 April 2012; published online 3 May 2012) This paper investigates the impact of edge-adding number m and edge-adding distance d on both synchronizability and average path length of NW small-world networks generated from ring networks via random edge-adding. It is found that the synchronizability of the network as a function of the distance d is fluctuant and there exist some d that have almost no impact on the synchronizability and may only scarcely shorten the average path length of the network. Numerical simulations on a network of Lorenz oscillators confirm the above results. This phenomenon shows that the contributions of randomly added edges to both the synchronizability and the average path length are not uniform nor monotone in building an NW small-world network with equal-distance edge additions, implying that only if appropriately adding edges when building up the NW small-word network can help enhance the synchronizability and/or reduce the average path length of the resultant network. Finally, it is shown that this NW small-world network has worse synchronizability and longer average path length, when compared with the conventional NW small-world network, with random-distance edge additions. This may be due to the fact that with equal-distance edge additions, there is only one shortcut distance for better information exchange among nodes and for shortening the average path length, while with random-distance edge additions, there existmany different distances for doing so. VC 2012 American Institute of Physics. As a typical network model, small-world network has been widely investigated. A small-world network usually has a stronger synchronizability as the edge-adding probability increases in its generation. It has been noticed, however, that it is impractical to enhance the network synchronizability by randomly adding some edges when building up a real network. In this contribution, therefore, a new type of small-world networks is proposed to be built on ring networks by equal-distance edge additions. The influence of edge addition on both synchronizability and average path length of such networks is further studied and compared via adding the same number of new edges in different ways. The findings are new, interesting, and may have implication on better understanding of network synchronization. I. INTRODUCTION Synchronization has been a focal subject for scientific research for a long time due to its ubiquity and importance in nature and society. Since the small-world network models1,2 typically have better synchronizability than many other types of complex networks, synchronization on small-world networks has attracted considerable attention recently. There are two effective ways to generate a small-world network: by random edge-rewiring, which yields the WS model,1 and by random edge-adding, which leads to the NW model.2 Both are generated from a nearest-neighbor coupling network, among which the ring network is the simplest. Small-world networks not only have relatively high cluster coefficients but also possess relatively short average path lengths in general. The concerned issue of synchronizability of small-world networks has been extensively investigated.3–13 In particular, Refs. 3–6 discussed the synchronizability of a small-world network generated by randomly adding a fraction of longrange shortcuts into a ring network. The results show that the synchronizability of the network becomes stronger as the edge-adding probability p increases, namely as the number of long-range shortcuts increases. On the other hand, Refs. 9–11 studies the correlation between the synchronizability and the average path length of a small-world network. The results show that as p increases, the synchronizability of the network is enhanced and correspondingly the average path length is reduced. That the synchronizability of the network becomes stronger probably results from the decreasing of the average path length, which motivates the present study. This paper tries to answer the following question: how does the distance between two connected nodes affect the synchronizability and the average path length of an NW small-world network? Specifically, this paper considers an NW small-world network of size N, generated by adding m edges on m pairs of randomly chosen nodes from among all possible node pairs in a given ring network of size N. The a)Electronic mail: tomlk@hqu.edu.cn . b)Electronic mail: jalu@whu.edu.cn . c)Electronic mail: eegchen@cityu.edu.hk . 1054-1500/2012/22(2)/023121/7/$30.00 22, 023121-1 VC 2012 American Institute of Physics CHAOS 22, 023121 (2012) distance between node i and node j is denoted dij. Only the case of equal distance dij ¼ d is considered in this paper. It is to explore the impact of both the distance d and the edgeadding number m on the synchronizability and the average path length of the NW small-world network. II. PRELIMINARY Consider an undirected and unweighted ring network with N nodes, labeled as 1; 2; ;N, according to a counterclockwise or clockwise arrangement. The distance between node i and node j, denoted as dij, is defined by dij ¼ min j i; modi N j;N; j i: (1) Here, modx; y is the modulo function, which returns the remainder after the number x is divided by the divisor y, and the result has the same sign as the divisor. Since the network topology is undirected, the connectivity is symmetric with dij ¼ dji. For illustration, a ring network with 12 nodes has distances between node 1 and node 4, node 3 and node 8, and node 10 and node 2, given by d14 ¼ 3; d38 ¼ 5; and d10;2 ¼ 4, respectively. When new edges are added to these three pairs of nodes, the new edges are said to have distance 3, 5, and 4, respectively, as shown in Figure 1. In this paper, the effect of random adding-edges with an equal distance is examined; that is, adding m new edges to m randomly chosen pairs of nodes from the following node set: fi; j ¼ 1; 2; ;Njdij ¼ d; 1 d ½N=2g: (2) Here, is the rounding function retaining the integer part of a real number. Note that there are N pairs of nodes for every such distance d, except when N is even, there are only N=2 pairs with distance d ¼ N=2. As an example, consider again the ring network with 12 nodes, and select 4 pairs of nodes with distance d ¼ 4 (for instance, choose pairs of node 1 and node 5, node 4 and node 8, node 10 and node 2, and node 11 and node 3), and then add new edges to link these pairs of nodes, respectively, as shown in Figure 2. The corresponding Laplacian matrix L is as follows: L ¼ zfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl{ d¼4 zfflfflfflfflfflfflfflfflfflfflfflfflfflfflffl}|fflfflfflfflfflfflfflfflfflfflfflfflfflfflffl{ d¼4 3 1 1 0 1 1 3 1 0 1 1 3 1 . . . 1 1 3 1 1 0 1 1 3 1 0 0 1 2 1 . . . . . . 1 2 1 . . . 1 1 3 1 . . . 0 0 1 2 1 1 . . . 1 3 1 1 . . . 1 3 1 1 0 . . . 1 2 0BBBBBBBBBBB BBBBBBBBBBBB@ 1CCCCCCCCCCCCCCCCCCCCCCCA (3) III. NETWORK SYNCHRONIZATION PRELIMINARIES Consider a network of N identical dynamics nodes, described by _ xi ¼ Fxi cXN j¼1 aijHxj: (4) Here, xi 2 Rn is the state vector of the ith node, F : Rn ! Rn is a well-defined nonlinear function, c is a positive constant coupling strength, H : Rn ! Rn is the inner coupling matrix, A ¼ aijNN is the outer coupling matrix satisfying dissipative condition Pj aij ¼ 0, i; j ¼ 1; 2; ; N. Set nit ¼ xit s, i ¼ 1; 2; ; N, and linearize the state Eq. (4) at a desired state s. Then, one obtains the following linear system of variational equations: _n i ¼ DFsni cXN j¼1 aijDHsnj; i ¼ 1; 2; ;N: (5) Here, DFs and DHs are the Jacobian matrix of Fs and Hs evaluated at s, respectively. Let n ¼ ½n1; n2; ; nN. Then, Eq. (5) can be rewritten as _n ¼ DFsn cDHsnAT: (6) Denote K ¼ diagk1; k2; ; kN, with kii ¼ 1; 2; ; N being the eigenvalues of the symmetrical matrix A, which can be decomposed into the Jordan form AT ¼ SKS1, and let g ¼ ½g1; g2; ; gN ¼ nS. Then, one has _gi ¼ ½DFs ckiDHsgi; i ¼ 1; 2; ;N: (7) Since A is symmetrical, the master stability equation can be defined as follows: 023121-2 Tang, Lu, and Chen Chaos 22, 023121 (2012) y_ ¼ ½DFs aDHsy: (8) Here, a is a real constant determined by the coupling strength and the eigenvalues of matrix A. One can calculate the largest Lyapunov exponent Lmaxa of the linear system (8), as a function of a, to obtain the so-called master stability function.14 It is known that Lmaxa 0 is a necessary condition for ni ! 0 namely xit ! 0 as t!1, i ¼ 1; 2; ;N, achieving completely synchronization in network (4). Note that since the network is undirected and unweighted, its coupling matrix A is a symmetrical and irreducible Laplacian matrix, which has only one zero eigenvalue along with N 1 positive real eigenvalues, denoted as 0 ¼ k1 k2 kN. If the synchronized region of the network is bounded, where Lmaxa 0 within a finite interval a1 a a2, then to achieve network synchronization, it is necessary that a1 ck2 ck2 ckN a2 (9) Or, more conveniently, it is required that the eigenratio R satisfies R ¼ kN=k2 a2=a1: (10) The smaller the ratio R, the easier the condition (10) is satisfied, so the better the network synchronizability. If the synchronized region is unbounded, where Lmaxa 0 within an infinite interval a1 cki 1, i ¼ 1; 2; ;N, then the larger the k2, the better the network synchronizability, because the coupling strength c can be smaller. To some extent, the impact of k2 on the network synchronizability is higher than that of kN.15,16 FIG. 1. Adding edges with several different d in a ring network with 12 nodes. FIG. 2. Adding 4 edges with d ¼ 4 in a ring network with 12 nodes. FIG. 3. k2 as a function of d for N ¼ 1000. From bottom up: m is, respectively, (a) 10, 20, 30, 40, 50, 60, 80, and100 and (b) 100, 150, 200, 250, and 300. FIG. 4. k2=kN as a function of d for N ¼ 1000. From bottom up: m is, respectively, (a) 10, 20, 30, 40, 50, 60, 80, and 100 and (b) 100, 150, 200, 250, and 300. 023121-3 Tang, Lu, and Chen Chaos 22, 023121 (2012) IV. INFLUENCE OF DISTANCE ON NETWORK SYNCHRONIZABILITY This section is devoted to an extensive numerical investigation to the influence of equal-distance edges additions on the network synchronizability. Specifically, consider two ring networks with N ¼ 1000 and N ¼ 2000, respectively, in which all nodes have identical dynamics, so that the synchronizability of the two networks can be characterized by both k2 and k2=kN. For each m, randomly pick up m pairs of nodes from all possible pairs with an equal distance d, and then connect each pair of nodes by a new edge, thereby adding totally m new edges to the ring. Then, for each resulting network, calculate the eigenvalues of its corresponding Laplacian matrix. Since the new edges were added at random, the Laplacian matrix would be different on each trial, so in the simulation, 50 different realizations were performed and the results were averaged. For the network with N ¼ 1000 nodes, let d ¼ 2; 3; ; N=2, while for the network of N ¼ 2000 nodes, d ¼ 10; 20; ;N=2 were used. Their corresponding Laplacian eigenvalues k2 and k2=kN as functions of d and m were found, respectively, as shown in Figures 3 and 4 for the network with N ¼ 1000 and Figures 5 and 6 for N ¼ 2000. From Figures 3–6, one can see that for both criteria characterizing the synchronizability of the networks, namely with k2 or k2=kN, the synchronizability of the simulated small-world networks is always correlated with the distance d, and the network synchronizability as a function of d is non-monotonous, but fluctuant. Moreover, one can see that the fluctuations become fiercer as the edge-adding number m increases. The most striking phenomenon is that as m becomes bigger than a certain threshold value, there exist FIG. 5. k2 as a function of d for N ¼ 2000. From bottom up: m is, respectively, (a) 20, 40, 60, 80, 100, and 120 and (b) 160, 200, 300, 400, 500, and 600. FIG. 6. k2=kN as a function of d for N ¼ 2000. From bottom up: m is, respectively, (a) 20, 40, 60, 80, 100, and 120 and (b) 160, 200, 300, 400, 500, and 600. FIG. 7. k2 or k2=kN as a function of m for several different distances for N ¼ 1000. 023121-4 Tang, Lu, and Chen Chaos 22, 023121 (2012) some distances d such that the value of k2 will be saturated, namely will not be further increased by adding even more edges of such distances (for example, d ¼ 200; 250; 333; 400; and 500 for the network with N ¼ 1000, and d ¼ 400; 500; 670; 800; and 1000 for N ¼ 2000). Actually, the value of k2=kN becomes even slightly smaller. This can be seen more clearly from Figure 7. In other words, the synchronizability of a forming small-world network is not continuously and monotonically enhanced by the operation of “equal-distance edge addition” to an initial ring network. In fact, it turns out to be closely related with the distance of the added edges: for some values of d, the synchronizability either remains unchanged or is slightly decreased. It shows that one should avoid adding new edges with such distances in order to enhance the synchronizability of the growing small-world network with this method, or on the contrary should add new edges with such distances when synchronization is undesirable. Moreover, one can see from the figures that the number of the distance d corresponding to the minimum values of k2 (or k2=kN) increases as m increases, and the set of those minimum distances with bigger values of m contains that with smaller m. There were perception and tendency to add some longrange connections into a nearest-neighbor network, so as to shorten the average path length of the overall network thus improving the synchronizability of a small-world network.9–11 Moreover, it was believed that by increasing the number m of edge additions, one could shorten the average path length thereby improving the synchronizability of the small-world network. However, our investigation reveals that these are not always true. Figure 8 shows the impact of the equal-distance d on the average path length of the resulting small-world network. One can see that the average path length is not always significantly reduced as m increases. When m is bigger than a certain threshold value, there exists some values of distance d such that the average path length is saturated. For example, for the ring network with N ¼ 1000, the average path length deceases from 65.7685 to 63.5979 (the difference is very small) as m increases from 40 to 300 (the difference is very large) with d ¼ 250. Such values of distance d are exactly those corresponding to the minima of k2 (or k2=kN), but the curves of the average path, Ps, are opposite to that of k2 (or k2=kN). To verify the above theoretical results, a linearly coupled small-world network consisting of N ¼ 100 identical Lorenz oscillators is simulated x_i1 ¼ axi2 xi1 x_i2 ¼ cxi1 xi1xi3 xi2 x_i3 ¼ xi1xi2 bxi3 i ¼ 1; 2; ; N: 8: (11) Here, a ¼ 10; b ¼ 8=3; c ¼ 28, and H ¼ ½100; 000; 000; namely, the coupling is through the “x” component. The error of synchronization among the N nodes is defined as follows: Et ¼ 1 NXN i¼1 k xit xt k (12) FIG. 8. Ps as a function of d. From bottom up: m is, respectively, (a) 10, 20, 30, 40, 50, 60, 80, 100, 150, 200, 250, and 300 (N ¼ 1000) and (b) 10, 20, 40, 60, 80, 100, 120, 160, 200, 300, 400, 500, and 600(N ¼ 2000). FIG. 9. The errors of synchronization among 100 different Lorenz dynamics oscillators over time for d ¼ 22 and 25 and m ¼ 40 and 50. The inset is an amplified figure on some time interval. FIG. 10. k2 (a) and k2=kN (b) as a function of d for N ¼ 100. From bottom up: m is 20, 25, 30, 35, 40, 45, 50, 55, 60, and 65. 023121-5 Tang, Lu, and Chen Chaos 22, 023121 (2012) Let the coupling strengthen c ¼ 120, d ¼ 22 and 25, and m ¼ 40 and 50. The synchronization error is shown in Figure 9, which implies that when m is larger than a threshold, the synchronization error and the synchronization time of the network with d ¼ 22 are both significantly less than that of the network with d ¼ 25. The value of k2 or k2=kN at d ¼ 22 is much larger than that at d ¼ 25, as can be seen in Figure 10. In addition, it is shown that the synchronization error and synchronization time for d ¼ 25 are about the same for both cases of m ¼ 40 and m ¼ 50, but this is not the case for d ¼ 22. These findings are fully consistent with the above theoretical results. Finally, the synchronizability and average shortest path length of the conventional NW small-world networks are given as comparison with those of the fixed-shortcut-distance NW small-world networks. For the networks with N ¼ 1000 nodes, the eigenvalue k2 (or eigen ratio k2=kN) and average shortest path length Ps with m edges additions are shown in Figure 11, while Figure 12 shows those of the networks with N ¼ 2000 nodes. From both figures, it is clear that for the same number m of edges additions, k2 and k2=kN (or the average shortest path length Ps) are much larger (or shorter) than that of the fixed-shortcut-distance NW small-world network, implying that the conventional NW small-world network has better synchronizability and shorter average shortest path length. It also indicates that, without considering shortcut distance limitation, one should not fix but randomize shortcut distance for enhancing the synchronizability via adding some edges into a ring network. V. CONCLUSIONS AND DISCUSSIONS In summary, this paper has explored the relationships between the edge-adding number m or the edge-adding distance d with the synchronizability and the average path length of the NW small-world networks generated from ring networks via random edge-adding. The impacts of m and d on both synchronizability and average path length have been investigated. Extensive numerical simulations have shown that the resulting average path length of the network is not FIG. 11. NW small-world network with conventional algorithm and N ¼ 1000, m ¼ 10, 20, 30, 40, 60, 80, 100, 150, 200, 250, and 300. (a) k2 and k2=kN vs m and (b) Ps vs m. FIG. 12. NW small-world network with conventional algorithm and N ¼ 2000, m ¼ 20, 40, 60, 80, 120, 160, 200, 300, 400, 500, and 600. (a) k2 and k2=kN vs m and (b) Ps vs m. 023121-6 Tang, Lu, and Chen Chaos 22, 023121 (2012) always shortened and so the synchronizability is not always enhanced in forming a fixed-shortcut-distance NW smallworld network. Nevertheless, when m is bigger than a certain threshold value, some values of distance d have almost no influence on the synchronizablity, but may scarcely shorten the average path length as m increases. This phenomenon indicates that the contributions of randomly added edges to both the synchronizability and the average path length are not uniform nor monotone. The present study also reveals that there are significant differences in the synchronizability and average path length for the NW small-world networks between the fixed-shortcutdistance strategy and the non-fixed-shortcut-distance strategy. Conventional NW small-world network has better synchronizability and shorter average shortest path length, which is perhaps because there exist many different distances for better information exchange among nodes and for shortening the average path length, while with the fixed-shortcut-distance strategy, there exists only one shortcut distance to be used. However, if it is necessary to fix the shortcut distance for some practical considerations. Since the distances of the adding-edges are important to the building of an NW smallworld network and, therefore, one should avoid adding new edges with inadequate distances in order to enhance the synchronizability of a growing small-world network. However, what are the exact values for such distances? And, what are their correlations with the size of the underlying network? These questions call for more investigations, from which a new mathematical theory may be further developed. ACKNOWLEDGMENTS This work was supported by the National Natural Science Foundation of China under Grants 60974081 and 11172215, the Hong Kong RGC under the GRF Grant CityU1114/11E, and the Fundamental Research Funds for the Central Universities. 1D. J. Watts and S. H. Strogatz, Nature (London) 393,440 (1998). 2M. E. J. Newman and D. J. Watts, Phys. Lett. A 263, 341 (1999). 3X. F. Wang and G. Chen, Int. J. Bifurcation Chaos 12,187(2002). 4F. Qi, Z. Hou, and H. Xin, Phys. Rev. Lett. 91, 064102 (2003). 5I. V. Belykh, V. N. Belykh, and M. Hasler, Physica D 195, 159 (2004). 6I. V. Belykh, V. N. Belykh, and M. Hasler, Physica D 195, 188 (2004). 7H. Hong, M. Y. Choi, and B. J. Kim, Phys. Rev. E 65, 026139 (2002). 8K. Park, L. Huang, and Y.C. Lai, Phys. Rev. E 75, 026211 (2007). 9T. Nishikawa, A. E. Motter, Y. C. Lai, and F. C. Hoppensteadt, Phys. Rev. Lett. 91, 014101 (2003). 10M. Zhao et al., Physica A 371, 773 (2006). 11X. F. Wang, X. Li, and G. R. Chen, Complex Network and Application (Tsinghua University Press, Beijing, 2006). 12X. P. Han and J. A. Lu, Sci. China, Ser. E 50, 615 (2007). 13C. Y. Yin, B. H. Wang, W. X. Wang, and G. R. Chen, Phys. Rev. E 77, 027102 (2008). 14L. M. Pecora and T. L. Carroll, Phys. Rev. Lett. 80, 2109 (1998). 15F. M. Atay, T. Biyikoglu, and J. Jost, Physica D 224, 35 (2006). 16L. Huang, Q. F. Chen, Y.-C. Lai, and L. M. Pecora, Phys. Rev. E 80, 036204 (2009). 023121-7 Tang, Lu, and Chen Chaos 22, 023121 (2012)
The small world yields the most effective information spreading Linyuan Lu, Duan-Bing Chen and Tao Zhou NJP 13 (2011)123005 The small world yields the most effective information spreading.pdf 在以往的文献中，人们在研究网络的传播过程时通常采用统一的模型如 SIR ，或基于此模型的变种。网络中有一条谣言，所有知道这个谣言的人都是已感染人群（ I ），所有不知道该谣言的人群都是易感人群（ S ）。那些知道了但是没有兴趣再传播的人被视为免疫的人（ R ）。开始的时候随机选择一个节点释放谣言，而且只有他的邻居有可能知道这个谣言。当网络中没有易感染人群（谣言活跃用户）的时候传播结束。 Sudbury 最早在完全随机网络中进行研究，发现可以感染 80% 的人。 Zanette 在小世界网络中进行研究发现可以感染的人数小于 80% 。以上的两个研究都是基于同质网络的，即度相同。 Liu 研究了传播比例和网络结构的关系。他考察的是异质度网络。 Zhou 进一步考察了不同的网络结构的影响，发现随机网络（度不相同）的传播比无标度好，而同质的随机网络传播最好可达到 80% ，这与 Ssudbury 的结论一致。 总的来说已有的工作结论很明显，使用 SIR 模型后发现规则网络传播能力最差， SW 好一些，最好的是随机网络，而同质的随机网络（ HMER ）效果最好。即 RESWERHMER 那么使用 SIR 模型来研究信息（或者行为）的传播是否合适呢？ Centola 在 Science 上发表的实验结果给了我们一定的启发。 显然，信息的传播和疾病的传播有着明显的本质上的区别，体现在如下几点： 1） 信息传播具有记忆性，疾病传播没有。（ Memory effects ） 在疾病传播中，这次接触有没有感染疾病与下次接触的结果是相互独立的，因此没有记忆效应。而信息传播具有记忆性，这次传播可能不成功，但是这个结果会累积，并影响下一次的结果。 2） 信息传播具有社会加强作用，疾病传播没有。（ Social reinforcement ） 一条信息如果我只听到一次可能有所怀疑，但是听多了就可能相信了。 3） 对一条信息来说，传播的每条链接一般只用一次，疾病传播可用多次。（ Non-redundancy of contact ） 人们可以进行多次的身体接触，但是一般不会将一条信息告诉同一个人多次。最恰当的比喻就是“一个妓女可能会孜孜不倦试图把艾滋病传染给你，如果她自己不知道而且你持续付钱的话；但是，一个八卦消息同一个人不会向你说十遍，祥林嫂除外！——周涛” 特别注意的是，对于那些可信性不容易被验证的信息而言，如谣言等， 1 ）和 2 ）的效应更加明显。而对于那些可信性强的信息，如权威网站发布的官方信息， 1 ）和 2 ）的效应较弱，使得传播过程更倾向于传统的 SIR 模型。 基于以上三点考虑，我们提出一个简单的模型。每一时间步，每一个体处于四种状态之一： 1 ）不知道（ Unknown ）——个体还不知道该信息，类似于 SIR 模型中的易感人群。 2 ）知道（ Known ）——个体听到了这个信息，但是由于不确定信息的准确性因此不愿意传播（在此假设人们只愿意传播可信的消息）。 3 ）确认（ Approved ）——个体确认了该消息并进一步传播给他的邻居。 4 ）疲惫（ Exhausted ）——个体传播了信息后对该信息失去兴趣，相当于 SIR 模型中的免疫态。 模型假设节点在时间 t 确认该信息的概率为 P(m)=(lambda-T)exp +T ， 其中 m 为截止到 t 时刻，个体接收到的信息次数， m 在此体现了信息传播的记忆性特征。 T 为最大确认概率。参数 b 体现了社会加强作用的强度， b 越大，社会加强作用越大。 Lambda=P （ 1 ）表示只听到一次信息就确认的概率。 在规则网，小世界和随机网络上做实验。结果发现，在 lambda 较小的时候规则网络的传播比随机网络更快更广。随着 lambda 的增加，随机网络的优势逐渐体现，达到某一临界值的时候随机网络表现得更好。而当 lambda 很大的时候，也就是说只听到一次就确信的时候（权威发布的信息）网络结构对最终确认人数的影响并不大，但是随机网络的传播速度更快。进一步的，实验结果显示临界值随网络规模呈现一个非单调递增的趋势：先迅速减小，当规模足够大的时候基本稳定在一个很小的值。这个结果使得我们有些质疑 Centola 的实验是否能够在更大规模的网络上成功。 在规则网络上引入一个很小的随机重连的概率后，网络具有了小世界特性。实验发现，在我们新提出的模型框架下小世界网络的传播效果更好。最优的断边重连概率随参数 b 的增加呈现单调递减的趋势，并且这种趋势不受网络规模的影响。 除本文考虑的三点区别外，信息和疾病的传播还存在以下不同： 1） 信息传播随时间衰减迅速，人们的兴趣本身就会随时间衰减。在当今的社会，信息的时效性是信息价值的重要组成部分。试想，当你兴致勃勃的告诉大家一个消息的时候，却换来这样的回应“你不是吧，这个我们早知道了！”是多么尴尬的事啊。而疾病可以存在上千年，不管是昨天，今天还是明天他都在那里，阴魂不散！ 2） 信息传播中不同类型的边的传播能力和方式不同，而疾病传播则没有太多区分，疾病传播中接触强度只会造成传播概率差异。 3） 信息传播的效果受到信息内容的影响。人们更容易关注，接受和传播感兴趣的内容。而疾病，不管你爱或不爱，他就在那里等着你。 4） 信息传播中每个节点的影响力不同，人们更倾向于相信权威的话。而在疾病传播中人们不会因为经常与权威人士接触而更容易得病。 可见在信息传播中，人们的主观能动性起到很重要的作用，而在疾病传播中人们完全是被动的。 虽然本文模型很简单，但是实验结果在很大程度上纠正和完善了人们对信息传播的传统认识。当然，文章还有很多不足之处，谨以此小文抛砖引玉，期待更多的相关研究。 参考文献： 1. A. Sudbury, J. Appl. Prob. 22 (1985) 443. 2. D. H. Zanette, Phys. Rev. E 64 (2001) 050901 (R). 3. D. H. Zanette, Phys. Rev. E 65 (2002) 041908. 4. Z. Liu, Y.-C. Lai, N. Ye, Phys. Rev. E 67 (2003) 031911. 5. Y. Moreno, M. Nekovee, A. F. Pacheco, Phys. Rev. E 69 (2004) 066130. 6. J. Zhou, Z. Liu, B. Li, Physics Letters A 368 (2007) 458. 7. Damon Centola, The Spread of Behavior in an Online Social Network Experiment, Science 329 (2010) 3.
今天看了科学网这个帖子 ，小世界原理、世界小现象实证研究 http://www.sciencenet.cn/blog/user_content.aspx?id=230314 ， 好歹咱也是研究复杂网络了，外加今年在social networks正好有两篇有关50年来小世界现象研究的综述，链接放到下面送给感兴趣的人吧。 作者均为：Sebastian Schnettler Center for Research on Inequalities and the Life Course, Department of Sociology, Yale University, New Haven, CT, United States 1. A structured overview of 50 years of small-world research http://dx.doi.org/10.1016/j.socnet.2008.12.004 Abstract This paper offers a structured overview of 50 years of small-world research. Initially formulated by Pool and Kochen in the mid-1950s, the small-world concept can be divided into six research foci, based on three dimensions (structural, process-related, psychological), and two process-related themes (diffusion, search). Building on this analytical distinction, the article provides a historical summary of the different phases of research on the small-world problem, and summarizes the empirical and theoretical progress on different facets of the small-world phenomenon. The paper concludes with a brief assessment of accomplishments and open questions, suggesting some possible future research areas. Keywords: Small-world phenomenon; Social networks; Six degrees of separation; Small-world experiment; Social process; Social structure; Complex networks; New science of networks; Milgram; Social capital; Network dynamics 2. A small world on feet of clay? A comparison of empirical small-world studies against best-practice criteria http://dx.doi.org/10.1016/j.socnet.2008.12.005 Abstract Small-world studies were introduced by Milgram and others in the 1960s and 1970s. These studies, and a majority of variants conducted by others, display a number of methodological weaknesses that bias their results. While no explicit methodological standard exists for these studies, here I derive a number of best-practice criteria for small-world studies by pointing out mistakes of previous studies, and by applying methodological standards from other empirical research areas. Improving the methodology of letter referral studies is important, because such studies could still be useful in a number of contexts today, especially for the exploration of factors affecting targeted search processes. Keywords: Small-world phenomenon; Six degrees of separation; Milgram; Social process; Social structure; Small-world experiment; Experiment; Search; Best practice 想了解小世界现象前世今生的可以看看第一篇文献，想进一步做实证研究的可以读读第二篇文献。
标签: 小世界
