ER Eröds-Rényi ER p ER 1 2.3BA Balabasi 9 1 f (k) k 3 1 BA KN KN 8,10 KN 2 2 p 1 Rich-club 11 ( f (k) = 1 +

Size: px

Start display at page:

Download "ER Eröds-Rényi ER p ER 1 2.3BA Balabasi 9 1 f (k) k 3 1 BA KN KN 8,10 KN 2 2 p 1 Rich-club 11 ( f (k) = 1 +"

みさえことじ
6 years ago
Views:

1 Vol.4, No.2, pp.33-40, * * 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 Watts 1 Pintado 2 binary decision with externalities 4 5,6 7,

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.

2 ER Eröds-Rényi ER p ER 1 2.3BA Balabasi 9 1 f (k) k 3 1 BA KN KN 8,10 KN 2 2 p 1 Rich-club 11 ( f (k) = p + 1 ) k (2+ 1 2p+1 ) φ i i d i i s ij i j 1 0 φ i j s ij d i 3 3 φ i d i d i

3 35 1 Torus Random Regular ER BA KN 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) G 0 (1) = k(k 1)ρ k p k = z k=0 7 7 G 0 (1) < z ,12 KN BA BA λ max (A KN ) 1 3

4 λ max (A) N L 13 k λ max (A) 2L N k two-step flow 14 Watts 15 Watts Lopez 1 1,2,15 2 0% 10% N z φ 2 2 aba KN (b) BA KN z φ 4

5 37 a z = (2, 4,, 14) 1 N 0.2%(= 6) a 2 a KN b N 0.2%(= 6) 2 a ? 4 φ 0,1 m 0,0.10 f (m,φ) φ m f m, φ 5

6 φ 0.25 φ < 0.25 φ < BA f (m,φ) 1 5 φ φ 0.5 BA 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.

7 39 6 KN φ m f m, φ BA BA 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 , April

8 D. López-Pintado. Contagion and coordination in random networks. International Journal of Game Theory, Vol. 34, No. 3, pp , H. Peyton Young. The evolution of conventions. Econometrica, Vol. 61, pp , T.C. Schelling. Hockey helmets, concealed weapons, and daylight saving: A study of binary choices with externalities. Journal of Conict Resolution, Vol. 17, pp , 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 , Y. Moreno, J.B. Gómez, and A.F. Pacheco. Epidemic incidence in correlated complex networks. Physical Review E, Vol. 68, No. 3, p , 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 , Takanori Komatsu and Akira Namatame. Dynamic diffusion process in evolutionary optimized networks. International Journal of Bio-Inspired Computation, Vol. 3, No. 6, pp , A. L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, Vol. 286, pp , pp , S. Zhou and R. J. Mondragón. The rich-club phenomenon in the internet topology. Communications Letters, Vol. 8, No. 3, pp , March D. Cvetkovi c and P. Rowlinson. On connected graphs with maximal index. Publi-cations de l Institut Mathematique, Vol. 44, No. 58, pp , Hong Yuan. A bound on the spectral radius of graphs. Linear Algebra and its Applications, Vol. 108, pp , September Katz Elihu and Paul Flelix Lazarsfled. Personal influence; the part played by peple in the flow of mass communications. Glencoe, Vol. 3,, Duncan J. Watts and Peter Sheridan Dodds. Influentials, networks, and public opinion formation. Journal of Consumer Research, Vol. 34, December Adaptation and Evolution in Collective Systems World Scientific Journal of Economic Interaction and Coordination Editor-in-Chief & AAAI, ACM, IEEE 8

k = The Last Samurai Tom Cruise [1] Oracle Ken Watanabe (I) has a Bacon number of 2. 1: 6(k 6) (small world p

k = The Last Samurai Tom Cruise [1] Oracle Ken Watanabe (I) has a Bacon number of 2. 1: 6(k 6) (small world p 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,