1 vertex edge 1(a) 1(b) 1(c) 1(d) 2
(a) (b) (c) (d) 1: (a) (b) (c) (d) 1 2 6 1 2 6 1 2 6 3 5 3 5 3 5 4 4 (a) (b) (c) 2: (a) (b) (c) 1(b) [1 10] 1 degree k n(k) walk path 4
1: Zachary [11] [12] [13] World-Wide Web [14] [15] [16] [17] i k i k i k i (k i 1)/2 q i i q i C i = q i k i (k i 1)/2 (1) i 3 k 1 = 3 2, 3, 4 (2, 3), (3, 4), (4, 2) 1 5 3: 2 4 3 q 1 = 1 C 1 = 1/3 N i = 1, 2, 3,..., N N N A A ij i j 1 0 3
0 1 1 1 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 0 (2) 1(c) 1(d) i j A ij = 1 1(a) 1 2 1 4(a) 1 4(b) 4 5 µ 200 σ 15 n(k) e (k µ)2 /(2σ 2 ) (3) n(k) = λ k e λ /k! λ µ = λ σ = λ k n(k) k γ (4) (3) (4) (4) (4) 2 2 γ (3) σ (4) 4 Barabási-Albert [13]
10 9 8 11 7 6 12 5 13 4 14 3 15 2 16 1 17 30 18 29 28 192021 22 23 24 25 2627 12 14 15 16 17 18 19 11 9 8 7 20 22 23 24 25 26 27 6 5 4 3 2 29 1 30 10 13 21 28 (a) (b) 4: 30 50 (a) (b) 300 250 200 150 100 50 (a) 0 0 100 200 300 400 500 600 300 250 200 150 100 50 (b) 0 0 100 200 300 400 500 600 5: 1000 200 000 (a) (b)
4 Watts-Strogatz [18] 3 4 5 universality universal gravity T c (T T c ) γ γ (T c T ) β β (T T c ) γ (T c T ) β Z 2 Z 2
2 4 5
(a) (b) 6: Barabási-Albert m = 2 (a) m = 2 (b) m = 2 (5) 4 Barabási-Albert [13] Watts-Strogatz [18] 4.1 Barabási-Albert Barabási-Albert [13] (i) m 6(a) m 1,2,3 (ii) (a) n m m i = 1, 2,..., N k i N m p i = k i N i=j k j (5) (b) N 1 (5) preferential attachment
5(a) (b) hub k n(k) k 3 (6) (4) γ = 3 k (5) [19] p i = k i + a N i=j (k j + a) (7) a (6) n(k) k 3+a/m (8) γ 3 2 γ 3 m a 0 (6) t m t = 0 1 1 t N(t) = m + t m(m 1)/2 m E(t) = m(m 1)/2 + mt i = 1, 2,..., N(t) k i (t) t N(t) [ ] m(m 1) k j (t) = 2 + mt 2mt (9) 2 j=1 (5) p i (t) k i(t) 2mt (10) i t + 1 m mp i k i
dk i dt = mp i = k i 2t (11) ( ) 1/2 t k i (t) = m (12) t i t i i i m k i (t i ) = m (12) t ki n(k) k (12) t i = t(m/k) 2 t k m [ ( m ) ] 2 N(t) N(t i ) = t t i = t 1 k (13) n(k) (13) k (6) (5) n(k) = 2m2 t k 3 (14) p i = k i + a N i=j (k j + a) (15) a (14) n(k) k 3+a/m (16) γ 3 2 γ 3 m a 0 p i p i = 1 N 1 t (17) (11)
(a) (b) 7: Watts-Strogatz (a) m N (b) dk i dt = m t (18) k i = m + m log t t i (19) k i = m[1 + log(t/t i )] n(k) exp( k/m) (20) 4.2 Watts-Strogatz Watts-Strogatz m N 7(a) Nm/2 pnm/2 7(b) p = 0 p = 1 p = 0 7(a) m/2 1 x x/(m/2)
N/2 N/(m/2) L 1 N/2 N x=1 x m/2 2N m (21) m m(m 1)/2 m 2 m 3 m/2 m/2 1 1 [ ( m )] 2 (m 2) + 2 1 m 2 = 3 m(m 2) (22) 8 C = 3(m 2) 4(m 1) (23) p = 1 Watts-Strogatz N N(N 1)/2 Nm/2 m/(n 1) C = m N 1 (24) 8 l N(l) m N(l) m(m 1) l 1 m l (25)
8: N(l) N(l 1) m N L N m L (26) L ln N (27) p = 0 O(N 1 ) p = 1 O(N 0 ) p = 0 p = 1 O(N 1 ) p O(N 0 ) O(N 1 ) 5 4 [20] 3
[21 25] [26 29] [26] (i) (ii) q H = i j (A ij γp ij )δ(σ i, σ j ) (28) q (28) σ i 1 q δ(σ i, σ j ) σ i = σ j 1 A ij A p ij i j γ [26] (28) A ij > γp ij i j [26]
4 6 communicability [30, 31] 6.1 Communicability 1 9(a) 2 9(b) 3 9(a) 9(b) 1 Estrada communicability [30,31] G ij = n=0 1 n! (An ) ij (29) A 1 (A n ) ij i j n (A n ) ij = i 1,i 2,...,i n 1 A ii1 A i1 i 2 A i2 i 3 A in 1 j (30) (a) (b) 9: (a) 2 (b) 3
(a) (b) 10: (a) (b) A 1 i i 1 i 2 i n 1 j (29) i j 1/n! 1/n! (29) G ij = ( e A) ij (31) G ij (β) = n β n n! (An ) ij = ( e βa) ij (32) β A 10(a) H (32) communicability [30,31] λ µ ψ µ N N N µ = 1, 2,..., N (31) G ij = N ψ µ (i)ψ µ (j)e λµ (33) µ=1 ψ µ (i) ψ µ i A H = A λ 1 λ 1 λ 2 λ 2 10(b)
12 10 8 6 4 2 (a) 40 35 30 25 20 15 10 5 (b) 0 4 3 2 1 0 1 2 3 4 0 10 8 6 4 2 0 2 4 6 8 10 11: (a)zachary [11] (b) [16] i j ψ 2 (i) ψ 2 (j) ψ 3 (i) ψ 3 (j) λ 3 i j ψ 2 (i) ψ 2 (j) ψ 3 (i) ψ 3 (j) (33) ψ µ (i) ψ µ (j) G ij = G ij ψ 1 (i)ψ 1 (j)e λ 1 = µ ++/ ψµ (i)ψ µ (j) e λµ µ + / + ψµ (i)ψ µ (j) e λµ. (34) i j G ij communicability network 6.2 [32] 11
2: [11] [16] [17] [12] / 34/78 297/2148 2114/2203 40421/175692 10 15 888 2678 ( ) ( 0) ( 0) ( 268) ( 844) 29.4% 5.1% 29.3% 4.5% 0 0 412 5 ( ) ( 0) ( 0) ( 265) ( 5) 0% 0% 6.9% 0% 12: 11(b) 2 2 [32] 12 12
(a) (b) 13: (a)zachary 12 (b) 12 13 [32] 7 [1], 2005 [2], 2010 [3] A.-L. Barabási Linked: The New Science of Networks (Perseus Publishing, 2002) [4] M. Newman, A.-L. Barabási, D.J. Watts The Structure and Dynamics of Networks (Princeton University Press, 2006) [5] M. Newman Networks: An Introduction (Oxford University Press, 2010) [6] R. Cohen, S. Havlin Complex Networks: Structure, Robustness and Function (Cambridge University Press, 2010) [7] E. Estrada The Structure of Complex Networks: Theory and Applications (Oxford University Press, 2012)
[8] R. Albert, A.-L. Barabási, Rev. Mod. Phys. 74 (2002) 47 [9] S.N. Dorogovtsev, J.F.F. Mendes, Adv. Phys. 51 (2002) 1079 [10] M.E.J. Newman, SIAM review 45 (2003) 167 [11] W.W. Zachary, J. Anthoropological Res. 33 (1977) 452 [12] M.E.J. Newman, Proc. Natl. Acad. Sci. USA 98 (2001) 404 [13] A.-L. Barabási, R. Albert, Science 286 (1999) 509 [14] R. Albert, H. Jeong, A.-L. Barabási, Nature 401 (1999) 130 [15] V. Batagelj, A. Mrvar, http://vlado.fmf.uni-lj.si/pub/networks/data/ [16] D.J. Watts and S.H. Strogatz, Nature 393 (1998) 440 [17] H. Jeong, S. Mason, A.-L. Barabási, Z.N. Oltvai, Nature 441 (2001) 411 [18] D.J. Watts, S.H. Strogatz, Nature 393 (1998) 440 [19] S.N. Dorogovtsev, J.F.F. Mendes, A.N. Samukhin, Phys. Rev. Lett. 85 (2000) 4633 [20] S.N. Dorogovtsev, A.V. Goltsev, J.F.F. Mendes, Rev. Mod. Phys. 80 (2008) 1275 [21] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.-U. Hwang, Phys. Rep. 424 (2006) 175 [22] G. Szabó, G. Fáth, Phys. Rep. 446 (2007) 97 [23] K. Szhajd-Weron, Acta Physica Polonica B 36 (2005) 2537 [24] A. Grabowski, R.A. Kosiński, Physica A 361 (2006) 651 [25] Q. Li, L.A. Braunstein, H. Wang, J. Shao, H.E. Stanley, S. Havlin, J. Stat. Phys. 151 (2013) 92 [26] J. Reichardt, S. Bornholdt, Phys. Rev. Lett. 93 (2004) 218701; Phys. Rev. E 74 (2006) 016110 [27] I. Ispolatov, I. Mazo, A. Yuryev, J. Stat. Mech. (2006) P09014 [28] S.W. Son, H. Jeong, J.D. Noh, Eur. Phys. J. B 50 (2006) 431 [29] P. Ronhovde, Z. Nussinov, Phys. Rev. E 81 (2010) 046114 [30] E. Estrada, N. Hatano, Phys. Rev. E 77 (2008) 036111; ibid. 78 (2008) 026102; Appl. Math. Comp. 214 (2009) 500 [31] E. Estrada, N. Hatano, M. Benzi, Phys. Rep. 514 (2012) 89 [32] B. Ruben, N. Hatano, in preparation