Greedy Network Growth Model of Social Network Service
Shohei Usui*, Fujio Toriumi*, Masato Matsuo**,
Takatsugu Hirayama***, and Kenji Mase***
*Graduate School of Engineering, The University of Tokyo, 7-3-1 Hongo, bunkyo-ku, Tokyo 113-8656, Japan
**NTT Network Innovation Laboratories, 3-9-11 Midori-cho, Musashino-shi, Tokyo 180-8585, Japan
***Graduate School of Information Science, Nagoya University, Furo-cho, Chikusa-ku, Nagoya 464-8603, Japan
As new network communication tools are developed, social network services (SNS) such as Facebook and Twitter are becoming part of a social phenomenon globally impacting on society. Many researchers are therefore studying the structure of relationship networks among users. We propose a greedy network growth model that appropriately increases nodes and links while automatically reproducing the target network. We handle a wide range of networks with high expressive ability. Results of experiments showed that we accurately reproduced 92.4% of 189 target networks from real services. The model also enabled us to reproduce 30 networks built up by existing network models. We thus show that the proposed model represents the expressiveness of many existing network models.
-  A. L. Barabási and R. Albert, “Emergence of Scaling in Random Networks,” Science, Vol.286, No.5439, pp. 509-512, 1999.
-  G. Bianconi and A. L. Barabási, “Competition and multiscaling in evolving networks,” Europhysics Letters, Vol.54, pp. 436-442, 2001.
-  G. Bianconi and A. L. Barabási, “Bose-Einstein Condensation in Complex Networks,” Phys. Rev. Lett., Vol.86, pp. 5632-5635, 2001.
-  A. Vázquez, “Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations,” Phys. Rev. E, Vol.67, 2003.
-  K. Yuta, N. Ono, and Y. Fujiwara, “A Gap in the Community-Size Distribution of a Large-Scale Social Networking Site,” ArXiv:physics/0701168, 2007.
-  K. Ishida, F. Toriumi, and K. Ishii, “Proposal for a Growth Model of Social Network Service,” IEEEWeb Intelligence, pp. 91-97, 2008.
-  R. Cowan and N. Jonard, “Network structure and the diffusion of knowledge,” J. of Economic Dynamics and Control, Vol.28, No.8, pp. 1557-1575, 2004.
-  P. Holme, B. J. Kim, C. N. Yoon, and S. K. Han, “Attack vulnerability of complex networks,” Phys. Rev. E, Vol.65, No.5, p. 056109, 2002.
-  D. J. Watts and S. H. Strogatz, “Collective dynamics of “smallworld” networks,” Nature, Vol.393, pp. 440-442, 1998.
-  M. E. J. Newman, “Mixing patterns in networks,” Phys. Rev. E, Vol.67, No.2, p. 026126, 2003.
-  P. Holme and B. J. Kim, “Growing scale-free networks with tunable clustering,” Physical Review E, Vol.65, No.2, p. 026107, 2002.
-  K. Klemm and V. M. Eguiluz, “Growing scale-free networks with small-world behavior,” Physical Review E, Vol.65, p. 057102, 2002.
-  A. Vázquez, M. Boguñá, Y. Moreno, R. Pastor-Satorras, and A. Vespignani, “Topology and correlations in structured scale-free networks,” Physical Review E, Vol.67, p. 046111, 2003.
-  K. I. Goh, B. Kahng, and D. Kim, “Universal behavior of load distribution in scale-free networks,” Physical Review Lettters, Vol.87, p. 278701, 2001.
-  S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, “Pseudofractal scale-free web,” Physical Review E, Vol.65, p. 066122, 2002.