Vol.4, No.2, pp.33-40, 2012 33 * * Relation between network structure and cascade phenomena Takanori Komatsu* and Akira Namatame* Abstract Which social network structures are suitable for diffusion of innovation, new products, or new convention? There are many papers to answer this question. The main stream of the study is to find the relationship between social network structure and diffusion rate of innovation. In this paper we show relation between network structure and cascade phenomena and three characteristic elements maximum eigenvalue of adjacency matrix of the social network, the number of innovator and the deployment of innovator decide the dynamics of cascade phenomena. Key words Network topology, Cascade phenomena, Threshold model, Social consensus formation 1 OS 1,2,3 Pintado 2 Watts 1 Department of Computer Science National Defence Academy of Japan 2011 12 22 2012 7 17 Watts 1 Pintado 2 binary decision with externalities 4 5,6 7,8 3 2 3 4 5 1
34 4 2 2012 2 2.1 2.1.1 1 2.1.2 1 2.2ER Eröds-Rényi ER p ER 1 2.3BA Balabasi 9 1 f (k) k 3 1 BA 1 2.4 KN KN 8,10 KN 2 2 p 1 Rich-club 11 ( f (k) = 1 + 1 2p + 1 ) k (2+ 1 2p+1 ) 2 3 3.1 1 0 1 2 1 3 0 1 3 φ i i d i i s ij i j 1 0 φ i j s ij d i 3 3 φ i d i d i 1 1 1 2
35 1 Torus Random Regular ER BA KN 3000 3000 3000 3000 3000 4.0 4.0 4.0 4.0 4.0 2 0 0 19.8 49.6 158.9 77.5 6.6 6.0 9.1 3.8 0.00 0.00 0.00 0.01 0.10 4 4 5.2 12.4 32.9 0 1 1 3.2 0 1 1 1 k φ i 4 4 φ k 1/φ 4 k p k k ρ k k ρ k p k φ 5 G 0(x) = ρ k p k x k k=0 { 1 k 1/φ ρ k = 0 k > 1/φ 5 5 n 6 6 z z early n = 1 + zz early z G 0 (1) 6 6 7 G 0 (1) = k(k 1)ρ k p k = z k=0 7 7 G 0 (1) < z 7 3.3 4 8,12 KN BA BA λ max (A KN ) 1 3
36 4 2 2012 λ max (A) N L 13 k λ max (A) 2L N + 1 8 k 4 4.1 2 two-step flow 14 Watts 15 Watts Lopez 1 1,2,15 2 0% 10% 4.2 1 N 3000 4.2.1 z φ 2 2 aba KN (b) BA KN z φ 4
37 a z = (2, 4,, 14) 1 N 0.2%(= 6) 200 2 a 2 a KN 10 4.2.2 2 b N 0.2%(= 6) 2 a 4.3 2 1? 4 φ 0,1 m 0,0.10 f (m,φ) 200 1 4.3.1 3 0.25 0.5 3 φ m f m, φ 5
38 4 2 2012 0.5 0.25 1 2 1 4.3.2 4 φ 0.25 φ < 0.25 φ < 0.25 4.3.3BA f (m,φ) 1 5 φ 0.25 2 φ 0.5 BA 4.3.4 KN KN BA Susceptible Infected Susceptible SIS 8 6 KN 4 φ m f m, φ 5 BA φ m f m, φ 6
39 6 KN φ m f m, φ BA BA 0.5 0 KN 5 Pintado 2 Watts 1 Pintado 2 KN KN 1 D. J. Watts. A simple model of global cascades on random networks. Proceedings of the National Academy of Sciences, Vol. 99, No. 9, pp. 5766-5771, April 2002. 7
40 4 2 2012 2 D. López-Pintado. Contagion and coordination in random networks. International Journal of Game Theory, Vol. 34, No. 3, pp. 371-381, 2006. 3 H. Peyton Young. The evolution of conventions. Econometrica, Vol. 61, pp. 57-84, 1993. 4 T.C. Schelling. Hockey helmets, concealed weapons, and daylight saving: A study of binary choices with externalities. Journal of Conict Resolution, Vol. 17, pp. 381-428, 1973. 5 T.Zhou, G. Yan, and B.H. Wang. Maximal planar networks with large clustering coefficient and power-law degree distribution. Physical Review E, Vol. 71, No. 4, p. 46141, 2005. 6 Y. Moreno, J.B. Gómez, and A.F. Pacheco. Epidemic incidence in correlated complex networks. Physical Review E, Vol. 68, No. 3, p. 35103, 2003. 7 Y. Wang, D. Chakrabarti, C. Wang, and C. Faloutsos. Epidemic spreading in real networks: An eigenvalue viewpoint. International Symposium on Reliable Distributed Systems SRDS'03, pp. 25-34, 2003. 8 Takanori Komatsu and Akira Namatame. Dynamic diffusion process in evolutionary optimized networks. International Journal of Bio-Inspired Computation, Vol. 3, No. 6, pp. 384-392, 2011. 9 A. L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, Vol. 286, pp. 509-512, 1999. 10 7 pp. 57-64, 2011. 11 S. Zhou and R. J. Mondragón. The rich-club phenomenon in the internet topology. Communications Letters, Vol. 8, No. 3, pp. 180-182, March 2004. 12 D. Cvetkovi c and P. Rowlinson. On connected graphs with maximal index. Publi-cations de l Institut Mathematique, Vol. 44, No. 58, pp. 29-34, 1988. 13 Hong Yuan. A bound on the spectral radius of graphs. Linear Algebra and its Applications, Vol. 108, pp. 135-139, September 1988. 14 Katz Elihu and Paul Flelix Lazarsfled. Personal influence; the part played by peple in the flow of mass communications. Glencoe, Vol. 3,, 1955. 15 Duncan J. Watts and Peter Sheridan Dodds. Influentials, networks, and public opinion formation. Journal of Consumer Research, Vol. 34, December 2007. 2001 2003 2008 2010 1973 1976 79 1987 88 Adaptation and Evolution in Collective Systems World Scientific Journal of Economic Interaction and Coordination Editor-in-Chief & AAAI, ACM, IEEE 8