38 6 Vol. 38 No. 6 2008 11 25 ADVANCES IN MECHANICS Nov. 25, 2008 *, 200444 4 : ; ; ;..,.,.,,,, 1, 3.,. 20 60, Travers Milgram [1] (six degrees of separation).. 1998 Watts Strogatz [2] (small world) (random shortcuts),. 2000 Kleinberg [3] (navigable) ; 2006 Nevanlinna. 1999 Barabási Albert [4] (scale-free) ; 2006 John Von Neumann (Medal).,. 20 [5].., (Euclid)., 1736 (Euler). 2 20 Solomonoff Rapoport [6] Erdös Rényi [7] ( ). ( )., ( )., ( ), ( ).,,.,,.., ( ) : 2008-06-30, : 2008-07-16 (60874083, 10872119) E-mail: shidh2001@263.net
680 2008 38,.,,. 2005 Barabási [8] (human dynamics). 2006 Vázquez [9],..,.,,,.,,.. 2., 1/4. 6,. : 1, 6, (average path length)( ) ; 2,,.,,,,,. 3 (fraction of transitive triples),. (clustering coefficient). 20 60, : (regular) (random),.,.,,, 4,, 1(a).,, ( ), (degree distribution) ( δ- ).,,.,,. SR [6] : N, p,, G(N, p),. X, ( 0 N(N 1)/2, ) n N(N 1)/2, n P (G n ) = p n (1 p) [N(N 1)/2] n., 2 N(N 1)/2,, pn(n 1)/2. ER [7] : N n, N(N 1)/2,, G(N, n),. ( ) N(N 1)/2,, n,. 2n p = N(N 1).. [7] : ;, ;.,, [10]. Watts Strogatz :, ;, ;..
6 : 681 WS, [2] : (1) : N, K = 2k, N >> K >> 1; (2) : p,,., (2) p., NK/2.,, pnk/2.,,., p= 0, ; p= 1,. k, Nk. p,, 1(a). 1(b), p,,. 1,. Kleinberg WS 1 [2],. WS,.,, 2(a). K(Kleinberg), [3] : (1) : N N, u (i, j), w (k, l), u w d(u, w) = k i + l j ; (2) : p(p 1) ; (3) : u d(u, w) r w q(q 0),. Kleinberg, s t,,, (decentralized search algorithms). [11] : (i) r = 0, α 0, p, q, N, l α 0 N 2/3. r = 0,,. (ii) r = 2, α 2 ( N ), p, q, l α 2 (log N) 2,. r 2 l α 0 N β,, r = 2 K, 2(b).
682 2008 38 2 [3]. 1999, Barabási Albert [4],, 3. BA., 1 [13]. BA [4] : (1) : m 0 ; (2) : ; (3) m(m / m 0 ) : Π (k i ) = k i k j i, j k i i.. 3 3 [12],,,,,. 3,,. (complex),.,, ( ) ; ;.
6 : 683 3,.,.,. :, ; :, ; :, ; :,.,,, 1. N, k, L, C, γ, ν.,. - : k nn k µ µ Pearson ν [14]. (assortative mixing), ν 1 ; (disassortative mixing), ν 1. Newman [15] - :,. 1, Barabási Albert 1 ( ), BA 3( ), 1 4..,, Dorogovtsev Mendes [16] (power law growth), [17] (logarithmic growth), [18]., [19], Dorogovtsev [20]., Albert Barabasi [21], [22] 1 4. ; [22] : (1) : m 0 (2) c (c < m 0 (m 0 1)/2) :, Π (k i ) = ak 1 i i, a 1 = i k 1 i ;, i O i K 1 i Π (k j ), K i = j O i Π (k j ), j., i j, c ; ; (3) : (4) / m : Π (k i ) = (k i + 1) (k j + 1) i j, m(m m 0 ) m ( m c),
684 2008 38.,, [23]. [24]., BA. BA Klemm Eguiluz [25] ; Takemoto Oosawa [26] [27]., BA,, (motif) [28]. BA,.. [29], Fortunato (rank) [30]. [31].,, [32 34]. Kleinberg [3], Watts [35]., [36]., [37] ;, [38]. [12 14,39] [40].,, [41].,. Karapivsky Redner [18]. 110,,.. 3. : (1) : ; (2) : ; (3) :, ; (4) :, ( ) ; (5) :. : (1) (growing network) : ; (2) (evolving network) : ; (3) (weighted network) :, ; (4) (hierarchical network) : ; (5) (bipartite network) : ; (6) (spatial network) :. : (1-1) (specifying network): N, WS K ; (1-2) (evolving network):, ;, BA,. (2-1) (uncorrelated network): P (k k) P (k ), ; (2-2) (correlated network): P (k k) P (k ),. (3-1) (static network):,
6 : 685 (3-2) (dynamic network): 4,,.. 4.1,. 4.1.1 (mean-field approach) Barabasi, Albert Jeong [42]. :, k. BA, k i (t) t i, k i (t), (dynamic equation). k i t = mπ (k i) = m k i j k j = k i 2t, k i(i) = m (1) (1) k i (t) = m (t/i) β, β = 1/2., k i (t) i.,, { } P {k i (t) < k} = P i > m2 t m 2 t k 2 = 1 k 2 (n 0 + t) P (k, t) = P {k i(t) < k} k = 2m 2 k 3 t n 0 + t t, ( ) P (k) = lim t P (k,t) 2m 2 k γ (2) γ = 1 + 1/β = 3 ( ). : m 2m2 k 3 dk = 1, (2),.,, k i (t). [43],,. k i (t) [44] ( [44] ),. i 1 mπ (k i ). 4.1.2 (rate-equation approach) Krapivsky [45]. k ( ) N k (t), k i (t) N k (t), mπ (k i ) (rate equation) dn k (t) dt = m (k 1)N k 1(t) kn k (t) k kn k(t) + δ km (3), k k., P (k) = k 1 P (k 1) k 2 2 P (k) + δ km (4),, BA [46].,,. 4.1.3 (master-equation approach) Dorogovtsev, Mendes Samukhin [20]., A, BA m,. k = q + A, q. m BA, A = m., q i (t). P (q, i, t) i i t q, P (q,, t) (master equation), P (q, t) = 1 t i=1 P (q, i, t) t. BA t [P (q, t + 1) P (q, t)] + P (q, t + 1) δ qm = q 1 2 P (q 1, t) q P (q, t) (5) 2 lim P (q, t) = P (q), lim t [P (q, t) t t P (q, t)] = 0, (4). (4) P (q) = 2m(m + 1) (q + m)(q + m + 1)(q + m + 2) (6)
686 2008 38 (6),,, k = q + m.,., [47],. 4.1.4 (Markov chins approach) [17]. K i (t), BA, K i (t), T = {i, i + 1, i + 2, }, Ω = {m, m + 1, m + 2, }. k = m, m + 1,, m + t i, mπ (k i ), 1 k/2t, l = k P {K i (t+1) = l K i (t) = k} = k/2t, l = k + 1 0, l k, l k + 1 [17] (rectangle iterative algorithm) [48], O(t 2 ). 3, [22]. BA, m=5, t=150 000 ( ), 150 000 ( ) ( ), 4.,.,. 4.2,.,. 4.2.1 G, A(G) : i j, a ij = 1, 0, a ii = 0. Laplacian L(G) A D, D, A G., Laplacian,. A L.,, N, λ j, j = 1,, N., ρ(λ) k M k ρ(λ) = 1 N n δ(λ λ j ), M k = j=1, λ k ρ(λ)dλ (7) M k = 1 N 1 N N (λ j ) k = 1 N tr(ak ) = j=1 i 1,i 2,,i k a i1i 2 a i2i 3 a ik i 1 (8) 4 [41] [49] f(k, i, t) = P {k i (t) = k, k i (l) k, l = 1, 2,, i, i + 1,, t = 1}, P (k, t), lim t P (k, t) = P (k).,,,,. (8) : a i1i 2 a i2i 3 a i3i 1 = 1, 3,..,.,,, [50]. Laplacian 0, N, 0
6 : 687 1. 0 = r 1 > r 2 r N, r 2 [29]. 4.2.2 MacArthur [51],.,. G, Aut(G),. N N!,. G a G, r G = (a G /N!) 1/N. Aut(G) = H 1 H n,.,.,.,. ϕ = G/Aut(G) G.,, d ij, i j., [52].. : 5(a),,. Aut(G) = S 3 S 3, { 2.13, 1, 1, 0.77, 0, 0, 1.77, 3.13}. : 5(b), 4 : 1 = {1, 2, 3}, 2 = {4}, 3 ={5}, 4 = {6,7,8}, 1 d ij. { 2.13, 0.77, 1.77, 3.13}, 1 0. r G 0.415 8,.,.,. 5 [51] 5,.,.,,, [9].,,.,. (Praxeology) Victor, Hunter Anthroponomy, Anthropo, Nomy. Mises, :,. 2005 Barabási [8]. Barabási [8]. : L, ρ(x) x. t > 0 p, 1 p.,..
688 2008 38 : p 1 ( ), ( ) p(τ), α = 1 ( ).,. p 0 ( ), ( ). Barabási [8]. [53], 6, α = 3/2. Vázquez [9],. - (SI)..,. p(τ),,,. g(τ) = 1 p(x)dx. n(t) t τ τ, [54], n(t) = D d=1 z dg d (t), z d d, D d, *.,. 6 [53],.. 7,,,...,., Cobham [55], α = 3/2 ( )... [56].
6 : 689 7 [9] Blanchard Hongler [57]. ; G(x), (EDF),. EDF,. Barabási ;, G(x)..,..,,. Vázquez,.,,,., ;,. [58],.,,,. [59],., :,, [60].. 4 : ; ; ;.. 6. (1) :. :,. :. :. :,. (2) : :,. :,. :,. (3) : :,. :,.,,. :,,..,. (4) :.,..
690 2008 38,.. 1 Travers J, Milgram S. An experiment study of the small world problem. Sociometry, 1969, 32: 425 443 2 Watts D J, Strogatz S H. Collective dynamics of smallworld networks, Nature, 1998, 393: 440 442 3 Kleinberg J M. Navigation in a small world. Nature, 2000, 406: 845 4 Barabási A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286, 509 512 5... :, 1993 6 Solomonoff R, Rapoport A. Connectivity of random nets. Bulletin of Math Biophys, 1951, 13: 107 117 7 Erdös P, Rényi A. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 1960, 5: 17 61 8 Barabási A L. The origin of bursts and heavy tails in human dynamics. Nature, 2005, 435: 207 211 9 Vázquez A, Rácz B, Lukács A, Barabási A L. Impact of non-poissonian activity patterns on spreading processes, Phys Rev Lett, 2007, 98: 158702 10 Molloy M, Reed B. A critical point for random graphs with a given degree sequence. Random Structures and Algorithms, 1995, 6: 161 179 11 Kleinberg J M. Complex networks and decentralized search algorithms. ICM06, 2006 12 Albert R, Barabási A L. Statistical mechanics of complex networks. Rev Mod Phys, 2002, 74: 47 97 13 Newman M E J. The structure and function of complex networks. SIAM Rev, 2003, 45: 167 256 14 Boccaletti S, Latora V, Moreno Y, et al. Complex networks: structure and dynamics. Physics Reports, 2006, 424(4, 5): 175 308 15 Newman M E J. Assortative mixing in networks. Phys Rev Lett, 2002, 89: 208701 16 Dorogovtsev S N, Mendes J F F. Effect of the accelerating growth of communication networks on their structure. Phys Rev E, 2001, 63: 025101 17 Shi D H, Chen Q H, Liu L M. Markov chain-based numerical method for degree distributions of growing networks, Phys Rev E, 2005, 71: 036140 18 Krapivsky P L, Redner S. Network growth by coping. Phys Rev E, 2005, 71: 036118 19 Liu Z H, Lai Y C, Ye N, et al. Connective distribution and attack tolerance of general networks with both preferential and random attachments. Physics Letters A, 2002, 303: 337 344 20 Dorogovtsev S N, Mendes J F F, Samukhin A N. Structure of growth networks with preferential linking. Phys Rev Lett, 2000, 85: 4633 4636 21 Albert R, Barabási A L. Topology of evolving networks: local events and universality. Phys Rev Lett, 2000, 85: 5234 5237 22 Shi D H, Liu L M, Zhu S X, Zhou H. Degree distributions of evolving networks. Europhys Lett, 2006, 76: 731 737 23 Chung F, Lu L, Dewey G, et al. Duplication models for biological networks. Journal of Computational Biology, 2003, 10: 677 687 24 Amaral L A N, Scala A, Barthélémy M, et al. Classes of small-world networks. Proc Natl Acad Sci USA, 2000, 97: 11149 25 Klemm K, Eguiluz V M. Growing scale-free networks with small-world behavior. Phys Rev E, 2002, 65: 057102 26 Takemoto K, Oosawa C. Evolving networks by merging cliques. Phys Rev E, 2005, 72: 046116 27 Zhang Z Z, Rong L L, Zhou S G. Evolving Apollonian networks with small-world scale-free topologies. Phys Rev E, 2006, 74: 046105 28,. (I)., 2007, 4(4): 6 12 29,,.. :, 2006 30 Fortunato S, Flammini A, Menczer F. Scale-free network growth by ranking. Phys Rev Lett, 2006, 96: 218701 31 Fang J Q, Bi Q, Li Y. Advances in theoretical models of network science. Front Phys China, 2007, 1: 109 124 32 Barrat A, Barthélemy M, Vespignani A. Weighted evolving networks: coupling topology and weight dynamics. Phys Rev Lett, 2004, 92: 228701 33 Li M H, Fan Y, Chen J W, et al. Weighted networks of scientific commnication: the measurement and topological role of weight. Physica A, 2005, 350: 643 650 34 Wang W X, Wang B H, et al. General dynamics of topology and traffic on weighted technological networks. Phys Rev Lett, 2005, 94: 188702 35 Watts D J, Dodds P S, Newman M E J. Identity and search in social networks. Science, 2002, 296: 1302 1305 36,,.,, 2009, 15(1) 37 Newman M E J, Strogatz S H, Watts D J. Random graphs with arbitrary degree distribution and their applications. Phys Rev E, 2001, 64: 026118 38 Barabási A L, Oltvai Z N. Network biology: understanding the cell s functional organization. Nature Reviews Genetics, 2004, 5: 101 113 39 Li L, Alderson D, Doyle J C, Willinger W. Towards a theory of scale-free graphs: definition, properties, and implications. Internet Mathematics, 2005, 2: 431 523 40 Newman M E J, Barabási A L, Watts D J. The Structure and Dynamics of Networks. Princeton: Princeton University Press, 2006 41,,.. :, 2006 42 Barabási A L, Albert R, Jeong H. Mean-field theory for scale-free random networks. Physica A, 1999, 272: 173 187 43 Shi D H, Zhu S X, Liu L M. Clustering coefficient of growing networks. Physica A, 2007, 381: 515 524
6 : 691 44 Albert R, Barabási A L. Topology of evolving networks: local events and universality. Phys Rev Lett, 2000, 85: 5234 5237 45 Krapivsky P L, Redner S, Leyvraz F. Connectivity of growing random networks. Phys Rev Lett, 2000, 85: 4629 4632 46 Krapivsky P L, Redner S. Organization of growing random networks. Phys Rev E, 2001, 63: 066123 47 Dorogovtsev S N, Mendes J F F. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford UK: Oxford University Press, 2003 48 Shi D H, Guo J L, Liu L M. SPH-distributions and the rectangle iterative algorithm. In: Chakravarthy S R, Alfa A S, eds. Matrix-Analytic Methods in Stochastic Models, New York: Marcel Dekker, Inc., 1997. 207 224 49 Hou Z T, Kong X X, Shi D H, et al. Degree-distribution stability of scale-free networks. 2008, arxiv: 0805. 1434v1 50,.., 2006, 3(1): 1 12 51 MacArthur B D, Sánchez-Garcia R J, Anderson J W. Symmetry in complex networks. 0705.3215v2, 2007 http://lanl.arxiv.org/abs/ 52 Golubitsky M, Stewart I. Nonlinear dynamics of networks: the groupoid formalism. Bulletin of the AMS, 2006, 43: 305 364 53 Oliveira J G, Barabási A L. Darwin and Einstein correspondence patterns. Nature, 2005, 437: 27 54 Pastor-Satorras R, Vespignani A. Epidemic spreading in scale-free networks. Phys Rev Lett, 2001, 86: 3200 3203 55 Abate J, Whitt W. Asymptotics for M/G/1 low-priority waiting-time tail probabilities. Queueing Systems, 1997, 25: 173 233 56,,.., 2007, 4(4): 1 5 57 Blanchard P, Hongler M O. Modeling human activity in the spirit of Barabási s queueing systems. Phys Rev E, 2007, 75: 026102 58 Clegg R G, Dodson M. Markov chain-based method for generating long-range dependence. Phys Rev E, 2005, 72: 026118 59 César A, Hidalgo R. Conditions for the emergence of scaling in the inter-event time of uncorrelated and seasonal systems. Physica A, 2006, 369: 877 883 60 Vázquez A, Oliveira J G, Dezsö Z, et al. Modeling bursts and heavy tails in human dynamics. Phys Rev Lett, 2006, 73: 036127 STOCHASTIC FEATURES OF COMPLEX NETWORKS AND THEIR PATTERNS IN DYNAMIC EVOLUTION * SHI Dinghua Department of Mathematics, Shanghai University, Shanghai 200444, China Abstract How to characterize the stochastic features of complex networks is discussed and their patterns in dynamic evolution are found out from four aspects: classical models and network characters, empirical studies and mathematical modeling, theoretical methods for analyzing networks, and human behaviors in network society. It is emphasized how a good model of networks describes the evolutionary mechanisms of actual networks and how various measures characterize the structural properties of actual networks. Based on stochastic and dynamic features of complex networks, the existing theoretical methods are commented and possible developments of analytic methods are discussed. The modeling of human dynamics and its influence on collective performances in the networked society are finally reviewed. Keywords complex network, human behavior, network society, Markov chain, queueing theory The project supported by the National Nature Science Foundation of China (60874083, 10872119) E-mail: shidh2001@263.net