(a) (b) (c) (d) 1: (a) (b) (c) (d) (a) (b) (c) 2: (a) (b) (c) 1(b) [1 10] 1 degree k n(k) walk path 4

Size: px

Start display at page:

Download "(a) (b) (c) (d) 1: (a) (b) (c) (d) (a) (b) (c) 2: (a) (b) (c) 1(b) [1 10] 1 degree k n(k) walk path 4"

まいえおとべ
5 years ago
Views:

1 1 vertex edge 1(a) 1(b) 1(c) 1(d) 2

2 (a) (b) (c) (d) 1: (a) (b) (c) (d) (a) (b) (c) 2: (a) (b) (c) 1(b) [1 10] 1 degree k n(k) walk path 4

3 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: q 1 = 1 C 1 = 1/3 N i = 1, 2, 3,..., N N N A A ij i j 1 0 3

4 (2) 1(c) 1(d) i j A ij = 1 1(a) (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]

5 (a) (b) 4: (a) (b) (a) (b) : (a) (b)

6 4 Watts-Strogatz [18] universality universal gravity T c (T T c ) γ γ (T c T ) β β (T T c ) γ (T c T ) β Z 2 Z 2

7 2 4 5

8 (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

9 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 = 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

10 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)

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)

12 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) 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)

13 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

14 [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]

15 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

16 (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)

17 (a) (b) : (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

18 2: [11] [16] [17] [12] / 34/78 297/ / / ( ) ( 0) ( 0) ( 268) ( 844) 29.4% 5.1% 29.3% 4.5% ( ) ( 0) ( 0) ( 265) ( 5) 0% 0% 6.9% 0% 12: 11(b) 2 2 [32] 12 12

19 (a) (b) 13: (a)zachary 12 (b) [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)

20 [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, [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) ; Phys. Rev. E 74 (2006) [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) [30] E. Estrada, N. Hatano, Phys. Rev. E 77 (2008) ; ibid. 78 (2008) ; 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

untitled

untitled - - GRIPS 1 traceroute IP Autonomous System Level http://opte.org/ GRIPS 2 Network Science http://opte.org http://research.lumeta.com/ches/map http://www.caida.org/home http://www.imdb.com http://citeseer.ist.psu.edu