The size of the world It is a small world Araseki Hitoshi Can you believe that everyone is at most six steps away from any other person on the Earth? This phenomenon, which is called small world phenomenon, was found by social psychologist S. Milgram in 1967. However, we could not recognize that it was important network structure until to prove by D.J.Watz and S.H.Strogatz in 1998. Recently, it has been understood that the small world phenomenon is a general network structure in various fields. In this paper, we discuss the small world network by simple mathematics. small world, scale free, random graph 1 k k = 0: k = 1: k = 2: k = 3:... Sean Penn (Mystic River) Woody Allen (Sweet and Lowdown)
k = 2 2003 The Last Samurai Tom Cruise [1] http://oracleofbacon.org/ Oracle Ken Watanabe (I) has a Bacon number of 2. 1: 6(k 6) 6 6 2 6 (small world phenomenon, small world effect) 20
Stanley Milgram 1967 (small world experiment) 6 6 (Six Degrees of Separation) (P.Erdös) (A. Rényi) [6] 1998 (Duncan J. Watts and Stevn H. Strogatz) [3] 3 [2] A (k) (L) 2 A : :L log n :C 1 n P (k) k k e k k! n 1 : L
: C 0 (Free-scale) : P (k) k ν, 2 < ν < 3 : L : C 2 2: n 1 ( ) 3 (p)
Regular( ) Small-world Random (p = 0) (p = 1) 3: (p) from Nature[3] (p) L(p) C(p) 4 p k 4 4 L(0) C(0) (p) 4: from Nature[3]
L(p) C(p) L C HUB 4 (C) (L) 1999 A.-L. Barabási and R. Albert [7, 8] HUB HUB HUB ( ) exponential network scale-free network
5: Visual illustration of the difference between an exponential and a scale-free network. from Nature[4] 5 5 HUB HUB HUB DNA [9, 10, 11] DNA DNA DNA
[12] [1] Tom Siegfried,,, 2008 [2] Rick Durrett, Random Graph Dynamics, Cambridge Univ. Press, 2007 [3] Duncan J. Watts and Stevn H. Strogatz, Collective dynamics of small-world networks, Nature 393, 440-442 (4 June 1998) [4] Reka Albert, Hawoong Jeong and Albert-Laszlo Barabasi, Error and attack tolerance of complex networks, Nature 406, 378-382 (27 July 2000) [5] C. Song, S. Havlin and H. A. Makse, Self-similarity of complex networks, Nature 433, pp.392-395 (30 November 2004) [6] P.Erdös and A. Rényi, On the evolution of random graph, Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5, 17, 1960 [7] A.-L. Barabási, and R. Albert, Emergence of scaling in random networks, Science 286, pp.509-512 (1999) [8] A.-L. Barabási,, NHK, 2002 [9] Stuart A. Kauffman, The Origins of Order: Self-Organization and Selection in Evolution, Oxford Univ Press, 1993 6 [10] Stuart A. Kauffman,,, 1999 9 [11] Stuart A. Kauffman,,, 2002 9 [12],,,, 2005
A [6] n n 2 nc 2 = n! 2!(n 2)! = 1 n(n 1) (1) 2 p(0 p 1) (1 p) 6: (n = 3) k P (k) n 1 k ( n 1 C k ) p k (n 1 k) (1 p) n 1 k P (k) = n 1 C k p k (1 p) n 1 k (2) k n 1 k = kp (k) = (n 1)p (3) k=0 (3) (2) n 1 n 1 k = kp (k) = k n 1 C k p k (1 p) n 1 k = k=1 n 1 k=1 = (n 1)p k=0 (n 1)! (k 1)!(n 1 k)! pk (1 p) n 1 k n 2 m=0 (n 2)! m!(n 2 m)! pm (1 p) n 2 m = (n 1)p(p + 1 p) n 2 = (n 1)p (n 1) (2) ( ) P (k) = (n 1)(n 2) (n k) k!(n 1) k kk (1 k n 1 )n 1 k
= k k k! 1 (1 1 n 1 )(1 2 n 1 ) (1 k 1 k k k! { lim (1 + 1 z z )z } k k k e k k! n 1 )(1 k n 1 )n 1 k A.1 k P (k) L n k log k n L n k 1 + L k z = z=1 L k z n (4) z=0 4 1 L f( k) = L z=0 k z = (1 k L+1 ) (1 k) (5) 5 f( k) n L log L L log n log k + ( k 1) 1 k n 1 L log n L log n log n (6) log k A.2 C = 1 n n i=1 C i i C i i k i n i C i = n i / ki C 2 n i i k i 2 p n i = ki C 2 p
C C (7) C = 1 n n i=1 n i k i C 2 = 1 n n k i C 2 p i=1 k i C 2 = p (7) (7) (3) n 1 (8) C = p = k (n 1) k n 1 n (8)