,.,, Barabási [8] (human dynamics) Vázquez [9],..,.,,,.,,.. 2., 1/4. 6,. : 1, 6, (average path length)( ) ; 2,,.,,,,,. 3 (fract

Size: px

Start display at page:

Download ",.,, Barabási [8] (human dynamics) Vázquez [9],..,.,,,.,,.. 2., 1/4. 6,. : 1, 6, (average path length)( ) ; 2,,.,,,,,. 3 (fract"

足崩荀
5 years ago
Views:

1 38 6 Vol. 38 No ADVANCES IN MECHANICS Nov. 25, 2008 *, : ; ; ;..,.,.,,,, 1, 3., , Travers Milgram [1] (six degrees of separation) Watts Strogatz [2] (small world) (random shortcuts), Kleinberg [3] (navigable) ; 2006 Nevanlinna Barabási Albert [4] (scale-free) ; 2006 John Von Neumann (Medal).,. 20 [5].., (Euclid)., 1736 (Euler) Solomonoff Rapoport [6] Erdös Rényi [7] ( ). ( )., ( )., ( ), ( ).,,.,,.., ( ) : , : ( , ) shidh2001@263.net

2 ,.,, Barabási [8] (human dynamics) Vázquez [9],..,.,,,.,,.. 2., 1/4. 6,. : 1, 6, (average path length)( ) ; 2,,.,,,,,. 3 (fraction of transitive triples),. (clustering coefficient) , : (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 :, ;, ;..

3 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).

4 [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 [12],,,,,. 3,,. (complex),.,, ( ) ; ;.

5 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),

6 ,, [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):,

7 6 : 685 (3-2) (dynamic network): 4,,.. 4.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 ) (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].,, (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)

8 (6),,, k = q + m.,., [47], (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= ( ), ( ) ( ), 4.,.,. 4.2,., 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

9 6 : = r 1 > r 2 r N, r 2 [29] 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 ,.,.,. 5 [51] 5,.,.,,, [9].,,.,. (Praxeology) Victor, Hunter Anthroponomy, Anthropo, Nomy. Mises, :, Barabási [8]. Barabási [8]. : L, ρ(x) x. t > 0 p, 1 p.,..

10 : 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].

11 6 : [9] Blanchard Hongler [57]. ; G(x), (EDF),. EDF,. Barabási ;, G(x)..,..,,. Vázquez,.,,,., ;,. [58],.,,,. [59],., :,, [60].. 4 : ; ; ;.. 6. (1) :. :,. :. :. :,. (2) : :,. :,. :,. (3) : :,. :,.,,. :,,..,. (4) :.,..

12 ,.. 1 Travers J, Milgram S. An experiment study of the small world problem. Sociometry, 1969, 32: Watts D J, Strogatz S H. Collective dynamics of smallworld networks, Nature, 1998, 393: Kleinberg J M. Navigation in a small world. Nature, 2000, 406: Barabási A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286, :, Solomonoff R, Rapoport A. Connectivity of random nets. Bulletin of Math Biophys, 1951, 13: 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: Barabási A L. The origin of bursts and heavy tails in human dynamics. Nature, 2005, 435: 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: Molloy M, Reed B. A critical point for random graphs with a given degree sequence. Random Structures and Algorithms, 1995, 6: Kleinberg J M. Complex networks and decentralized search algorithms. ICM06, Albert R, Barabási A L. Statistical mechanics of complex networks. Rev Mod Phys, 2002, 74: Newman M E J. The structure and function of complex networks. SIAM Rev, 2003, 45: Boccaletti S, Latora V, Moreno Y, et al. Complex networks: structure and dynamics. Physics Reports, 2006, 424(4, 5): Newman M E J. Assortative mixing in networks. Phys Rev Lett, 2002, 89: Dorogovtsev S N, Mendes J F F. Effect of the accelerating growth of communication networks on their structure. Phys Rev E, 2001, 63: 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: Krapivsky P L, Redner S. Network growth by coping. Phys Rev E, 2005, 71: 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: Dorogovtsev S N, Mendes J F F, Samukhin A N. Structure of growth networks with preferential linking. Phys Rev Lett, 2000, 85: Albert R, Barabási A L. Topology of evolving networks: local events and universality. Phys Rev Lett, 2000, 85: Shi D H, Liu L M, Zhu S X, Zhou H. Degree distributions of evolving networks. Europhys Lett, 2006, 76: Chung F, Lu L, Dewey G, et al. Duplication models for biological networks. Journal of Computational Biology, 2003, 10: Amaral L A N, Scala A, Barthélémy M, et al. Classes of small-world networks. Proc Natl Acad Sci USA, 2000, 97: Klemm K, Eguiluz V M. Growing scale-free networks with small-world behavior. Phys Rev E, 2002, 65: Takemoto K, Oosawa C. Evolving networks by merging cliques. Phys Rev E, 2005, 72: Zhang Z Z, Rong L L, Zhou S G. Evolving Apollonian networks with small-world scale-free topologies. Phys Rev E, 2006, 74: ,. (I)., 2007, 4(4): ,,.. :, Fortunato S, Flammini A, Menczer F. Scale-free network growth by ranking. Phys Rev Lett, 2006, 96: Fang J Q, Bi Q, Li Y. Advances in theoretical models of network science. Front Phys China, 2007, 1: Barrat A, Barthélemy M, Vespignani A. Weighted evolving networks: coupling topology and weight dynamics. Phys Rev Lett, 2004, 92: 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: Wang W X, Wang B H, et al. General dynamics of topology and traffic on weighted technological networks. Phys Rev Lett, 2005, 94: Watts D J, Dodds P S, Newman M E J. Identity and search in social networks. Science, 2002, 296: ,,.,, 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: Barabási A L, Oltvai Z N. Network biology: understanding the cell s functional organization. Nature Reviews Genetics, 2004, 5: Li L, Alderson D, Doyle J C, Willinger W. Towards a theory of scale-free graphs: definition, properties, and implications. Internet Mathematics, 2005, 2: Newman M E J, Barabási A L, Watts D J. The Structure and Dynamics of Networks. Princeton: Princeton University Press, ,,.. :, Barabási A L, Albert R, Jeong H. Mean-field theory for scale-free random networks. Physica A, 1999, 272: Shi D H, Zhu S X, Liu L M. Clustering coefficient of growing networks. Physica A, 2007, 381:

13 6 : Albert R, Barabási A L. Topology of evolving networks: local events and universality. Phys Rev Lett, 2000, 85: Krapivsky P L, Redner S, Leyvraz F. Connectivity of growing random networks. Phys Rev Lett, 2000, 85: Krapivsky P L, Redner S. Organization of growing random networks. Phys Rev E, 2001, 63: Dorogovtsev S N, Mendes J F F. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford UK: Oxford University Press, 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., Hou Z T, Kong X X, Shi D H, et al. Degree-distribution stability of scale-free networks. 2008, arxiv: v1 50,.., 2006, 3(1): MacArthur B D, Sánchez-Garcia R J, Anderson J W. Symmetry in complex networks v2, Golubitsky M, Stewart I. Nonlinear dynamics of networks: the groupoid formalism. Bulletin of the AMS, 2006, 43: Oliveira J G, Barabási A L. Darwin and Einstein correspondence patterns. Nature, 2005, 437: Pastor-Satorras R, Vespignani A. Epidemic spreading in scale-free networks. Phys Rev Lett, 2001, 86: Abate J, Whitt W. Asymptotics for M/G/1 low-priority waiting-time tail probabilities. Queueing Systems, 1997, 25: ,,.., 2007, 4(4): Blanchard P, Hongler M O. Modeling human activity in the spirit of Barabási s queueing systems. Phys Rev E, 2007, 75: Clegg R G, Dodson M. Markov chain-based method for generating long-range dependence. Phys Rev E, 2005, 72: 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: Vázquez A, Oliveira J G, Dezsö Z, et al. Modeling bursts and heavy tails in human dynamics. Phys Rev Lett, 2006, 73: STOCHASTIC FEATURES OF COMPLEX NETWORKS AND THEIR PATTERNS IN DYNAMIC EVOLUTION * SHI Dinghua Department of Mathematics, Shanghai University, Shanghai , 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 ( , ) shidh2001@263.net

,,,.,. [16,17],, [18].,, [19 21]., Zheng [22,23] (low density parity check, LDPC). LDPC,. LDPC,.,,.,., LDPC. ( ),.,,.. ( ) ( )., [24,25],.,

,,,.,. [16,17],, [18].,, [19 21]., Zheng [22,23] (low density parity check, LDPC). LDPC,. LDPC,.,,.,., LDPC. ( ),.,,.. ( ) ( )., [24,25],., 38 6 Vol. 38 No. 6 2008 11 25 ADVANCES IN MECHANICS Nov. 25, 2008 *,,, /,.,,,., ( ),., ( ),.,,, 3 ( )., ( ).,.,,,,, 1,,. [1,2],,, [3 8].,.,, (autonomous system, AS)., AS.,, AS. : [9 13] [14 18]. 1999 Faloutsos