2006 338 8570 255 Tel : 048 858 3577, Fax : 048 858 3716 Email : tohru@ics.saitama-u.ac.jp URL : http://www.nls.ics.saitama-u.ac.jp/ tohru 2006 p.1/58
1 2 : etc = x(t + 1) = 1 ax(t) 2 + y(t) y(t + 1) = bx(t) x y 2006 p.2/58
( ) x 4 x 7 x 3 x 5 x 8 x 6 x 2 x 1 2006 p.3/58
1.? 2. 3. 4. 2006 p.4/58
[ ] World Wide Web [ ] ( SARS) ( / ) 2006 p.5/58
2006 p.6/58
Stanley Milgram ( ) Witchita (Kansas ) Boston (Massachusetts ) Omaha(Nebraska ) Boston (Massachusetts ) 2006 p.7/58
2006 p.8/58
2006 p.9/58
? 2006 p.10/58
S. Milgram: The Small-World Problem, Psychology Today, Vol.1, pp.67 67, 1967. 2006 p.11/58
http://www.cs.virginia.edu/oracle/ : The Oracle says: Harrison Ford has a Bacon number of. Harrison Ford was in Clear and Present Danger (1994) with John Lafayette. John Lafayette was in Loverboy (2005) with Kevin Bacon. 2006 p.12/58
0 1 1 1 1,975 1,976 2 172,390 174,366 3 488,225 662,591 4 117,091 779,682 5 8,192 787,874 6 776 788,650 7 79 788,729 8 3 788,732 2.949 788,732 (http://www.cs.virginia.edu/oracle/ 2006 7 11 ) 2006 p.13/58
[ ] World Wide Web [ ] ( SARS) ( / ) 2006 p.14/58
? 6 ( ) 2.949 6 2.949 WWW ( ) ( ) OK 2006 p.15/58
2006 p.16/58
(1736 ) Euler, Cauchy, Hamilton, Cayley, Kirchhoff... Erdös, Rényi (random network, 1950 s) (1998 ) Watts and Strogatz (small world network, 1998) Barabási and colleagues (scale free network, 1999) (graph) 2006 p.17/58
(1736) ( ) (1875 ) c d g e a b f 2006 p.18/58
Euler (1736) c d g e a b f 2006 p.19/58
C A D B 2006 p.20/58
Euler (1736) ( ) 2006 p.21/58
1875 C c d g A e D a b f B 2006 p.22/58
c C d g A e D a b f B 2006 p.23/58
1 2006 p.24/58
2 2006 p.25/58
2006 p.26/58
2006 p.27/58
(20 ) 2006 p.28/58
(the number of vertices) N (degree) k i (i = 1, 2,..., N) v i = v i (degree distribution) p(k) (degree) < k >= kp(k) k=0 (avarege path length) L (clustering coefficients) C ( ) 2006 p.29/58
v i v i v i v i C i C 2006 p.30/58
1 2006 p.31/58
? 2006 p.32/58
Random Rewiring (Watts and Strogatz, 1998) p = 0 p = 1 p random rewiring 2006 p.33/58
Random Rewiring 1 0.9 0.8 0.7 0.6 L,C 0.5 0.4 0.3 0.2 0.1 C(p)/C(0) L(p)/L(0) 0 10 4 10 3 10 2 10 1 10 0 p 2006 p.34/58
L C L L R L/L R C C R C/C R 3.65 2.99 1.22 0.79 0.00027 2926.0 18.7 12.4 1.51 0.080 0.005 16.0 2.65 2.25 1.18 0.28 0.05 5.6 2006 p.35/58
P(k) k γ ( ) ( ) 2006 p.37/58
2006 p.38/58
2006 p.39/58
2006 p.40/58
2006 p.41/58
2006 p.42/58
2006 p.43/58
2006 p.44/58
p(k) ( ) p(k) k γ k ( ) 2006 p.45/58
WWW Yahoo Google 2006 p.46/58
1. m 0 2. m(< m 0 ) 3. v i k i v i Π(k i ) = k i, (1 i n) n k i i=1 4. 2006 p.47/58
t = 0 t = 1 t = 2 t = 3 t = 4 t = 5 2006 p.48/58
10 5 10 5 10 4 10 4 10 3 10 3 p(k i ) p(k i ) 10 2 10 2 10 1 10 1 10 0 10 0 10 1 10 2 10 3 k i p(k) k 3 10 0 10 0 10 1 10 2 k i 2006 p.49/58
= etc 2006 p.50/58
? 80 20 ( )? 2006 p.51/58
: NHK 2002 2006 p.52/58
: 2005 2006 p.53/58
: SYNC 2005 2006 p.54/58
Duncan J. Watts, Six Degrees, The Science of a Connected Age, W. W. Norton & Company, 2003 2006 p.55/58
Duncan J. Watts, Small Worlds, The Dynamics of Networks between Order and Randomness, Princeton University Press, 1999; : 2006 2006 p.56/58
: 2005; : 2006 2006 p.57/58