臺灣博碩士論文加值系統

隨著Web 2.0技術的發展，許多社群網路(如: Facebook, Twitter, 與Digg等)蓬勃發展，了解這些社群網站的成長模型與結構特徵，不但有助於提升經營網站的技術，亦可增進網站的價值，以及更有效地計劃與執行管理策略。因此，在本篇論文中，我們利用網站外部與內部吸引力，提出了社群網站的對數成長模型，來描述社群網站的成長模式與分析其網路特徵。本篇論文可分為三個部份。首先，我們利用網站外部與內部吸引力，提出一個社群網站成長模型；接著，分析模型的特性，並証明所提出的模型具無尺度網路的特徵；最後，我們利用真實社群網站的資料評估所提出的模型，結果顯示，我們所提出的模型可解釋真實世界的社群網站的成長模式及結構特徵，並藉由此模型提出管理上的應用與策略，以提升社群網站的價值。

With advance of Web 2.0 technology, many social networks such as Facebook, Twitter, and Digg, have been highly developed in recent years. Understanding the growth patterns and the characteristics of social networks helps us to promote the technology of running social networks, increase the networks’ value, and formulate marketing and pricing strategies. Therefore, in this thesis, we first utilize the concept of internal and external attractions to propose a population growth model. Next, we analyze the properties of the proposed model and show that the model has the characteristics of sale-free networks. Finally, we collect the data from two real world social networks to evaluate the proposed model. The experimental results show that these two social networks can be well fitted by the proposed model. Furthermore, we address the management implications of the proposed model and discuss how to promote the value of social networks.

Table of Contents
Table of Contents i
List of Figures ii
Chapter 1 Introduction 1
Chapter 2 Preliminaries and Problem Definitions 4
Chapter 3 The Proposed Model 5
3.1 Degree distribution 8
3.2 Degree correlation 9
3.3 Clustering coefficient 10
3.4 Diameter 11
Chapter 4 Numerical Study 13
Chapter 5 Conclusions and Future Work 23
References 26
Appendix A 29
Appendix B 32

List of Figures
Figure 1. The number of nodes in a social network. 6
Figure 2. The number of users in Facebook. 14
Figure 3. The value of αt for Facebook. 15
Figure 4. The number of users in Digg. 15
Figure 5. The value of αt for Digg. 16
Figure 6. The value of βt for Facebook. 17
Figure 7. The value of βt for Digg. 18
Figure 8. Diameter at each step for Facebook. 19
Figure 9. Diameter at each step for Digg. 19
Figure 10. Average friends by join time for Facebook. 20
Figure 11. Average friends by join time for Digg. 21













List of Tables
Table 1. Notations of the proposed model. 5

References

B.N. Adam, Interaction theory and the social network, Sociometry, Vol. 30, 1967, pp. 64-78.
A.L. Baraba ́si, E. Ravasz, T. Vicsek, Deterministic scale-free networks, Physica A-Statistical Mechanics and Its Applications, Vol. 299, 2001, pp. 559-564.
A.L. Baraba ́si, R. Albert, Emergence of scaling in random networks, Science, Vol. 286, 1999, pp. 509-512.
A.L. Baraba ́si, R. Albert, H. Jeong, Mean-field theory for scale-free random networks, Physica A, Vol. 272, 1999, pp. 173-187.
A. Broder, R. Kumar, F. Maghoul, P. Raghavan, A. Rajagopalan, R. Stata, A. Tomkins, J. Wiener, Graph structure in the Web, Computer Networks, Vol. 33, 2000, pp. 309-320.
T. Carletti, S. Righi, Weighted fractal networks, Physica A, Vol. 389, 2010, pp. 2134-2142.
X. Cheng, H. Wang, Q. Quyang, Scale-free network model of node and connection diversity, Physical Review E, Vol. 65, 2000, pp. 4633-4636.
H. Chun, H. Kwak, Y.H. Eom, Y.Y. Ahn, S. Moon, H. Jeong, Comparison of online social relations in terms of volume vs. interaction: A case study of Cyworld, Proceedings of the 8th ACM SIGCOMM Conference on Internet Measurement, 2008, pp.57-69.
S.N. Dorogovtsev, A.V. Goltsev, J.F.F. Mendes, Pseudofractal scale-free web, Physical Review E, Vol. 65, 2002, pp. 1-4.
S.N. Dorogovtsev, J.F.F. Mendes, A.N. Samukhin, Structure of growing networks with preferential linking, Physical Review Letters, Vol. 85, 2000, pp. 4633-4636.
P. Erdos, A. Renyi, On the evolution of random graphs, Bulletin of the International Statistical Institute, Vol. 38, 1960, pp.343-347.
T. Fenner, M. Levene, G. Loizou, A model for collaboration networks giving rise to a power-law distribution with an exponential cutoff, Social Networks, Vol. 29, 2007, pp. 70-80.
T. Fenner, M. Levene, G. Loizou, G. Roussos, A stochastic evolutionary growth model for social networks, Computer Networks, Vol. 51, 2007, pp. 4586-4595.
P.A. Geroski, Models of technology diffusion, Research Policy, Vol. 29, 2000, pp. 603-625.
H. Jeong, B. Tombor, R. Albert, Z.N. Oltvai, A.L. Barabasi, The large-scale organization of metabolic networks, Nature, Vol. 407, 2000, pp. 651-654.
S. Jung, S. Kim, B. Kahng, Geometric fractal growth model for scale-free networks, Physical Review E, Vol. 65, 2002, pp. 1-6.
P.L. Kraplvsky, S. Redner, F. Leyvraz, Connectivity of growing random networks Pyhsocial Review Letter, Vol. 85 , 2000, pp. 1-4.
T.R. Malthus, An Essay on the Principle of Population, J. Johnson & Co, St. Paul''s Church-yard, London, 1798.
R. Matei, A. Iamnitchi, P. Foster, Mapping the Gnutella network, IEEE Internet Computing, Vol. 6, 2002, pp. 50-57.
A. Mislove, H.S. Koppula, K.P. Gummadi, P. Druschel, B. Bhattacharjee, Growth of the Flickr social network, Proceedings of the First Workshop on Online Social Networks, 2008, pp. 25-30.
A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, B. Bhattacharjee, Measurement and analysis of online social networks, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, 2007, pp. 29-42.
M.E.J. Newman, Assortative mixing in networks, Physical Review Letters, Vol. 89, 2002, pp. 1-4.
P.F. Verhulst, Notes on the law as the population continues its growth, Correspondance Mathematique et Physique, Vol. 10, 1838, pp. 113-121.
D.J. Watts, S.H. Strogatz, Collective dynamics of “small-world” networks, Nature, Vol. 393, 1998, pp. 440-442.
Z. Zhang, L. Rong, C. Guo, A deterministic small-world network created by edge iterations, Physica A, Vol. 363, 2006, pp. 567-572.
Z. Zhang, L. Rong, S. Zhou, A general geometric growth model for pseudofractal scale-free web, Physica A, Vol. 377, 2007, pp. 329-339.
Y. Zhu, Measurement and analysis of an online content voting network: A case study of Digg, Proceedings of the 19th International Conference on World Wide Web, 2010, pp. 1039-1048.