Vol. 47 No. 3 Mar. 2006,, SNS: Social Networking Services Web SNS SNS mixi link community 3 Zipf SNS Structural Analy

Size: px

Start display at page:

Download "Vol. 47 No. 3 Mar. 2006,, SNS: Social Networking Services Web SNS SNS mixi link community 3 Zipf SNS Structural Analy"

そうあきくぼ
4 years ago
Views:

1 Vol. 47 No. 3 Mar. 2006,, SNS: Social Networking Services Web SNS SNS mixi link community 3 Zipf SNS Structural Analysis of Human Network in Social Networking Services Kikuo Yuta,, Naoaki Ono, and Yoshi Fujiwara Social Networking Services (SNS) have recently prevailed all over the World Wide Web. People grow up connections by making a tie to another who acknowledges as being a friend. Such a giant network of people, with each link being a mutually acknowledged friendship, has not ever been under previous investigation. This work analyzed the largest SNS in japan, called mixi, comprised of 360,000 nodes and 1.9 million links as of February 15, Our analysis shows scale-free distribution of degree in its tail, and high cliquishness. To observe structure by coarse-graining, we employed a community (highly intra-connected group) extracting method developed by other researchers. As a result, we uncovered three classes of communities according to size. Overall rank-size plot shows Zipf s law for community-size distribution. Nevertheless, we found the existence of a skip in size, which implies absence of community between 100 and 300 in the number of people. This structure cannot be explained by models such as preferential attachment nor connecting nearest neighbor. We report some results of our analysis in anticipation to future advent and development of SNS as an innovative human communication infrastructure. 1. ATR Network Informatics Laboratories, ATR Graduate School of Informatics, Kyoto University ERATO Presently with Complex Systems Biology Project, ER- ATO, JST 1) 2) Affiliation Network 865

2 866 Mar ) Cross 4) who knows what 5),6) 5) 6) Web SNS Web SNS Friendster 1 Web ,400 Friendster Myspace Friendster ,500 3 SNS SNS mixi 4 GREE 5 GREE mixi 100 GREE mixi 250 SNS SNS 1 6 SNS SNS Holme SNS 7) SNS dating site SNS Friendster: 2 Myspace: /1/10 4 mixi: 5 GREE: 6 mixi GREE Myspace

3 Vol. 47 No mixi SNS Holme community site SNS mixi mixi 3 Girvan Newman 8),9) mixi 4 Preferential Attachment Connecting Nearest Neighbor mixi 5 4 SNS mixi ,819 SNS mixi mix i 2005/8/3 1 mixi = Fig. 1 Growth in the number of mixi users (nodes). mixi 1,906, ,802 mixi 2.1 k =10.4 SD =19.4 k max = 1, ,846 mixi 1,000 2 k P ( k) k i k i k i k i (k i 1)/2 1 E i mixi ID ID 3 SNS

4 868 Mar blocking model 3) UCINET Negopy 36 2 mixi Fig. 2 Cumulative distribution of degree in the mixi network. Fig. 3 3 Scatter plot for degree and clustering coefficient. i C i C i = 2E i k i (k i 1) (1) 3 k C i C = Girvan Newman mixi 36 Girvan Newman 8),9) community 9) SNS SNS Girvan Newman GNS Girvan Newman Substructure GNS GNS 3.1 GNS n m GNS O((m + n)n) O(n 2 ) Girvan 8) Betweenness Centrality O(m 2 n) O(n 3 ) UCINET6= 32,767 5,000 10,000 An algorithm for extracting community structure

5 Vol. 47 No Newman 9) 1 modularity i j i j e ij e ii a i = e j ij Q Q = (e ii a 2 i ) (2) i i j 1 Q Q ij Q ij = e ij + e ji 2a i a j =2(e ij a i a j )(3) Q ij 1 1 Q ij 1 Q GNS GNS GNS GNS Clauset 10) group 9) O(n log 2 n) Linux PentiumIV 2.8 GHz 1GB mixi GNS mixi GNS GNS GNS GNS GNS GNS GNS 4 3D view 1 1 GNS GNS 3 GNS GNS GNS GNS GNS GNS GNS mixi 2D view 3.3 GNS GNS 2 mixi Preferential Attachment PA Connecting Nearest Neighbor CNN 2 PA Barabási BA 11) m 0 = m =1 10 m 0 m 1 1 1

6 870 Mar mixi GNS Fig. 4 3D & 2D views of connections between extracted substructure. CNN Davidsen DEB 12) DEB SNS Vázquez CNN 13) 13) CNN (1) 1 u (2) u 1 u = mixi Fig. 5 Graphical comparison between real data and models. 6 GNS Fig. 6 Rank-size plot of GNS with correspondence to 2D view for the mixi data. 2 mixi GNS 5

7 Vol. 47 No D view mixi 5(a) CNN 5(b) PA 5(c) (a) mixi GNS GNS GNS GNS 1 (b) CNN GNS (c) PA GNS GNS 10 GNS 500 5,000 7 mixi GNS Zipf Fig. 7 Rank-size plot of GNS with Zipf s law and sizeskip for the mixi data mixi GNS GNS mixi GNS GNS 6 GNS GNS GNS 4 2D view GNS GNS GNS x γ γ 1 Zipf GNS γ 1.3 GNS Zipf GNS 8 PA GNS Fig. 8 Rank-size plot of GNS for the PA model. 4.2 GNS PA CNN GNS PA 8 GNS PA GNS Zipf CNN GNS 9 GNS Zipf 10 1 realization GNS CNN

8 872 Mar CNN GNS Fig. 9 Rank-size plot of GNS for the CNN model. 10 Fig. 10 Absence of effect due to deletion of hubs in the mixi network. GNS 4.3 GNS GNS % 100 1% 2 10 Zipf GNS GNS GNS GNS Zipf CNN GNS Zipf CNN GNS CNN mixi mixi clique 2 CNN SNS Vázquez CNN CNN SNS 3 mixi 4

9 Vol. 47 No % 11 75% GNS CNN 1 SNS SNS SNS SNS SNS 1 1 SNS Web mixi Web 6 96% 6 8 FOAF: Friends Of A Friend FOAF SNS SNS Social Networking Service FOAF 6. SNS 36 Girvan Newman GNS GNS GNS GNS GNS Zipf PA GNS Zipf CNN Zipf GNS mixi mixi SNS

874 Mar. 2006 1) Barabási, A.L., Jeong, H., Neda, Z., Ravasz, E., Schubert, A. and Vicsek, T.: Evolution of the social network of scientific collaborations, Physica A, Vol.311, pp.590 614 (2002).

: The hidden power of social networks, Harvard Business School Press (2004). 5) Ebel, H., Mielsch, L.I. and Bornholdt, S.: Scale-free topology of e-mail networks, Physical Review E, Vol.

1st International Conference on Communities and Technologies, Kluwer,B.V. (2003). 7) Holme, P., Edling, C.R. and Liljeros, F.

10 874 Mar ) Barabási, A.L., Jeong, H., Neda, Z., Ravasz, E., Schubert, A. and Vicsek, T.: Evolution of the social network of scientific collaborations, Physica A, Vol.311, pp (2002). 2) Amaral, L.A.N., Scala, A., Barthélémy, M. and Stanley, H.E.: Classes of small-world networks, Proc. Natl. Acad. Sci. U.S.A., Vol.97, pp (2000). 3) (2003). 4) Cross, R. and Parker, A.: The hidden power of social networks, Harvard Business School Press (2004). 5) Ebel, H., Mielsch, L.I. and Bornholdt, S.: Scale-free topology of networks, Physical Review E, Vol.66, (R) (2002). 6) Tyler, J.R., Wilkinson, D.M. and Huberman, B.A.: as spectroscopy: automated discovery of community structure within organizations, Proc. 1st International Conference on Communities and Technologies, Kluwer,B.V. (2003). 7) Holme, P., Edling, C.R. and Liljeros, F.: Structure and time evolution of an internet dating community, Social Networks, Vol.26, pp (2004). 8) Girvan, M. and Newman, M.E.J.: Community structure in social and biological networks, Proc. Natl. Acad. Sci. U.S.A., Vol.99, No.12, pp (2002). 9) Newman, M.E.J.: Fast algorithm for detecting community structure in networks, Physical Review E, Vol.69, (2004). 10) Clauset, A., Newman, M.E.J. and Moore, C.: Finding community structure in very large networks, Physical Review E, Vol.70, (2004). 11) Barabási, A.L. and Albert, R.: Emergence of scaling in random networks, Science, Vol.286, pp (1999). 12) Davidsen, J., Ebel, H. and Bornholdt, S.: Emergence of a Small World from Local Interactions: Modeling Acquaintance Networks, Physical Review Letters, Vol.88, No.12, (2002). 13) Vázquez, A.: Growing network with local rules: Preferential attachment, clustering hierarchy and degree correlations, Physical Review E, Vol.67, (2003). ( ) ( ) ATR 17 ATR ATR International Society of Artificial Life ATR

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