臺灣博碩士論文加值系統

在近幾年的研究中，社群網路模型已經被應用在許多的領域中，例如在流行病學的傳染模擬、謠言散布模擬、意見形成的模擬、電腦病毒模擬等，這些都是與我們生活息息相關的，因此社群網路模型的研究一直是值得關注的議題。
在社群網路模型中，大家著重關注的是網路中的叢集度(clustering coefficient)及無尺度(scale-free)特性。在2005年時，加州理工學院的Lun Li等人提出了對於s-metric的觀察，這是對於網路中高連結節點與其他高連結節點彼此連結程度的觀察指標。我們所提出的新模型即針對此點來做加強。
在這篇論文中，我們提出了兩個社群網路模型，一是基於穴居人網路(caveman network)的靜態模型，一是基於成長網路(growing network)的動態模型。在模擬中，我們的網路模型都能提供叢集度及無尺度的特性，對於s-metric，亦有非常好的效果。同時，我們從Internet上取得了三個實際社群網路資料來做實驗比對，在模擬實驗中，雖然無法找到完全符合的參數，但亦提供了相當好的參考。

The social network model has been used for the simulation of epidemiological transmission, rumor spreading, opinion formation, and the spread of computer viruses in email network. Since social networks can be found in many aspects of our lives, it is worth to investigate how they work precisely.
The study suggests two models for social network based on a caveman network and growing network. The models we propose can fit the following two properties basically: (1) ''scale-free property'' which has power law degree distribution, and (2) ''small-world property'' which has high clustering coefficient. In addition, the models are modified for high hub connectivity which is a new viewpoint in scale-free network. This study also provided some empirical data for analysis.

CONTENTS
List of Figures III
List of Tables VI
CHAPTER 1 Introduction 1
CHAPTER 2 Background Knowledge 3
2.1 Scale-Free 3
2.2 Small-World 4
2.3 S-metric 6
CHAPTER 3 Related Works 8
3.1 The Evolution of the Social Network of Scientific Collaborations 8
3.2 The Highly Clustered Scale-Free Networks 9
3.3 The Growing Scale-Free Networks with Tunable Clustering 10
3.4 The Growing Scale-Free Networks with Small-World Behavior 10
3.5 The Geography in a Scale-Free Network Model 11
3.6 The Structure of a Large Social Network 11
3.7 The Models of Social Networks Based on Social Distance Attachment 12
3.8 The Evolving Scale-Free Network Model with Tunable Clustering 12
3.9 A Spatial Model for Social Networks 13
3.10 A Model for Social Networks 14
3.11 Summary 14
CHAPTER 4 Empirical Networks 15
4.1 The Opel Astra Club (OAC) 15
4.2 The Mygrizzie Website (Grizzie) 15
4.3 The People Fisher Website (PFW) 16
4.4 Empirical results 16
CHAPTER 5 New Models 21
5.1 Static Model 21
5.2 Dynamic Model 23
CHAPTER 6 Simulation 26
6.1 Static Model 26
6.2 Dynamic model 32
CHAPTER 7 Conclusions and Future Works 45
Reference 47
Publication List 51


List of Figures

Figure 1. Random rewiring procedure between a regular ring lattice and a random network. 6
Figure 2. The log-log degree distribution plot of the OAC, the slope of the line is -1.232. 17
Figure 3. The log-log degree distribution plot of the Grizzie, the slope of the line is -1.198. 18
Figure 4. The log-log degree distribution plot of the PFW, the slope of the line is -1.292. 18
Figure 5. The log-log rank versus degree distribution plot of OAC. 19
Figure 6. The log-log rank versus degree distribution plot of Grizzie 19
Figure 7. The log-log rank versus degree distribution plot of PFW. 20
Figure 8. Left is an initial caveman network with n=30 and w=5. Right is after added edges. 23
Figure 9. The double circle nodes are the neighbor nodes of PA or FA. (a) is FA1 connects to the neighbor node of PA1; (b) is FA2 connects to the neighbor node of PA3; (c) is FA3 connects to the neighbor node of FA2; (d) is FA4 connects to the neighbor node of FA3. 25
Figure 10. The clustering coefficient when degree k=6 to 12. 28
Figure 11. The tail index when degree k=6 to 12. 28
Figure 12. The average distance L when degree k=6 to 12. 29
Figure 13. The s(g)/smax when degree k=6 to 12. 30
Figure 14. The log-log degree distribution plots, the parameters are w=3, k=12, (a) n=900, (b) n=3000, (c) n=9000, (d) n=15000. 30
Figure 15. The log-log rank versus degree distribution plots, the parameters are w=3, k=12, (a) n=900, (b) n=3000, (c) n=9000, (d) n=15000. 31
Figure 16. The log-log degree distribution plot of our dynamic model with N=866, k=8.907, f=0.30, x=0.40. The slope of the line is -1.342. 33
Figure 17. The log-log degree distribution plot of our dynamic model with N=1975, k=7.764, f=0.35, x=0.20. The slope of the line is -1.507. 34
Figure 18. The log-log degree distribution plot of our dynamic model with N=2738, k=6.817, f=0.35, x=1.0. The slope of the line is -1.285. 34
Figure 19. The value of S with N=2738, f=0.05~0.55. The average degree k by (12) in the constructed network before extra edges added is 5.991, and the others after edges added by (13) are 6.817. 37
Figure 20. The clustering coefficient C with N=2738, f=0.05~0.55. The average degree k by (12) in the constructed network before extra edges added is 5.991, and the others after edges added by (13) are 6.817. 37
Figure 21. The tail index with N=2738, f=0.05~0.55. The average degree k by (12) in the constructed network before extra edges added is 5.991, and the others after edges added by (13) are 6.817. 38
Figure 22. The S with N=2000, m=3, f=0.10, and the extra edges added are from 100 to 1000. 39
Figure 23. The clustering coefficient C with N=2000, m=3, f=0.10, and the extra edges added are from 100 to 1000. 39
Figure 24. The tail index with N=2000, m=3, f=0.10, and the extra edges added are from 100 to 1000. 40
Figure 25. The log-log degree distribution plots, the parameters are f=0.5, x=0.8, k=12, (a) n=900, (b) n=3000, (c) n=9000, (d) n=15000. 40
Figure 26. The log-log rank versus degree distribution plots, the parameters are f=0.5, x=0.8, k=12, (a) n=900, (b) n=3000, (c) n=9000, (d) n=15000. 41
Figure 27. The OAC network topology. 42
Figure 28. The static model topology with N=864,w=4. 43
Figure 29. The dynamic model topology with N=866,m=4, f=0.3, x=0.3. 44


List of Tables

Table 1. The algorithm of calculating smax in a simple graph. 7
Table 2. The empirical data of the three real networks 20
Table 3. The comparison with three models when adding one new node. 25
Table 4. The static model simulation results with OAC, Grizzie and PFW. 29
Table 5. The s(g)/smax in multi graph and s(g)/smax in simple graph. 31
Table 6. The comparison between OAC and simulation of dynamic model. 35
Table 7. The comparison between Grizzie and simulation of dynamic model. 36
Table 8. The comparison between PFW and simulation of dynamic model. 36

[1] J. W. Grossman, P. D. F. Ion, “On a portion of the well-known collaboration graph,” Congressus Numerantium 108, pp. 129-131, 1995.
[2] R. D. Castro, J. W. Grossman, “Famous trails to Paul Erdos,” Mathematical Intelligencer 21, pp. 51-63, 1999.
[3] L. A. N. Amaral, A. Scala, M. Barthélémy, H. E. Stanley ,”Classes of small-world networks,” Proceedings of the National Academy of Sciences, 97(21), pp.11149-11152, 2000.
[4] M. E. J. Newman, “Clustering and preferential attachment in growing networks,” Physical Review E 64, pp. 025102, 2001.
[5] F. Liljeros, C. R. Edling, L. A. N. Amaral, H. E. Stanley, Y. Åberg, “The web of human sexual contacts,” Nature 411, pp. 907-908, 2001.
[6] M. E. J. Newman, “The structure of scientific collaboration networks,” Proceedings of the National Academy of Sciences, 98(2), pp. 404-409, 2001.
[7] D. J. Watts, S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature 393, pp. 440-442, 1998.
[8] A.-L. Barabási, H. Jeong, Z. Neda, E. Ravasz, A. Schubert, T. Vicsek, “Evolution of the social network of scientific collaborations,” Physica A 311, pp. 590-614, 2002.
[9] K. Klemm, V. M. Eguiluz, “Highly clustered scale-free networks,” Physical Review E 65, pp. 036123, 2002.
[10] P. Holme, B. J. Kim, “Growing scale-free networks with tunable clustering,” Physical Review E 65, pp. 026107, 2002.
[11] K. Klemm, V. M. Eguiluz, “Growing scale-free networks with small-world behavior,” Physical Review E 65, pp. 057102, 2002.
[12] C. P. Warren, L. M. Sander, and I. M. Sokolov, “Geography in a scale-free network model,” Physical Review E 66, pp. 056105, 2002.
[13] G. Csanyi, B. Szendrői, “Structure of a large social network,” Physical Review E 69, pp. 036131, 2004.
[14] M. Boguñá, R. Pastor-Satorras, A. Díaz-Guilera, and A. Arenas, “Models of social networks based on social distance attachment,” Physical Review E 70, pp. 056122, 2004.
[15] B. Wang, H. Tang, Z. Zhang, Z. Xiu, “Evolving scale-free network model with tunable clustering,” International Journal of Modern Physics B, 19(26), pp. 3951–3959, 2005.
[16] L. H. Wong, P. Pattison, G. Robins, “A spatial model for social networks,” Physica A 360, pp. 99-120, 2006.
[17] R. Toivonen, J.-P. Onnela, J. Saramäki, J. Hyvönen, and K. Kaski, “A model for social networks,” Physica A 371, pp. 851–860, 2006.
[18] Y. Tsai, C.-C. Lin, P.-N. Hsiao, “Modeling email communications,” IEICE Transactions on Information and Systems, Vol.E87-D No.6, pp. 1438-1445, 2004.
[19] R. M. Anderson, C. Fraser, A. C. Ghani, C. A. Donnelly, S. Riley, N. M. Ferguson, G. M. Leung, T. H. Lam, A. J. Hedley, “Epidemiology, transmission dynamics and control of SARS: the 2002-2003 epidemic,” Philosophical Transactions: Biological Sciences 359, pp. 1091-1105, 2004.
[20] L. A. Meyers, B. P. Pourbohloul, M. E. J. Newman, D. M. Skowronski, R. C. Brunham, “Network theory and SARS:predicting outbreak diversity,” Journal of Theoretical Biology 232, pp. 71-81, 2005.
[21] Y. Moreno, M. Nekovee, A.F. Pacheco, “Dynamics of rumor spreading in complex networks,” Physical Review E 69, pp. 066130, 2004.
[22] P. G. Lind, L. R. da Silva, J. S. Andrade and H. J. Herrmann, “The spread of gossip in American schools,” Europhysics Letters 78, pp. 68005, 2007.
[23] K. Kacperski, J. A. Hoyst, “Phase transitions as a persistent feature of groups with leaders in models of opinion formation,” Physica A 287, pp. 631-643, 2000.
[24] M. E. J. Newman, S. Forrest, J. Balthrop, “Email networks and the spread of computer viruses,” Physical Review E 66, pp. 035101, 2002.
[25] M. E. Crovella, M. S. Taqqu, A. Bestavros, “Heavy-tailed probability distributions in the World Wide Web,” In A Practical Guide To Heavy Tails, Chap.1, pp. 3-25, 1998.
[26] R. Albert, H. Jeong, A.-L. Barabási, “Internet: Diameter of the World-Wide Web,” Nature 401, pp. 130-131, 1999.
[27] Y. Tsai, C.-C. Lin, P.-N. Hsiao, “Heavy tail distribution in email network,” Proceedings of the 2002 SoftCOM, pp. 167-170, 2002.
[28] H. Ebel, L.-I. Mielsch, S. Bornholdt, “Scale-free topology of e-mail networks,” Physical Review E 66, pp. 035103, 2002.
[29] R. Albert, A.-L. Barabási, “Statistical mechanics of complex networks,” Reviews of Modern Physics, Vol.74, pp. 48-97, 2002.
[30] R. Tanaka, T.-M. Yi, J. Doyle, “Some protein interaction data do not exhibit power law statistics,” FEBS Letters, Vol.579, pp.5140-5144, 2005.
[31] L. Li, D. Alderson, J. C. Doyle, W. Willinger, “Towards a theory of scale-free graphs: definition, properties, and implications,” Internet Mathematics, 2(4), pp. 431-523, 2006.
[32] A.-L. Barabási, R. Albert, “Emergence of scaling in random networks,” Science 286, pp. 509-512, 1999.
[33] http://www.oac.idv.tw
[34] http://www.mygrizzie.com
[35] http://www.peoplefisher.com
[36] H. Zhou, “Scaling exponents and clustering coefficients of a growing random network,” Physical Review E 66, pp. 016125, 2002.
[37] D. M. Pennock, G. W. Flake, S. Lawrence, E. J. Glover, and C. L. Giles, “Winners don’t take all: Characterizing the competition for links on the web,” Proceedings of the National Academy of Sciences, 99(8), pp. 5207–5211, 2002.
[38] M. Mitzenmacher, “A brief history of generative models for power law and lognormal distributions,” Internet Mathematics, 1(2), pp. 226-251, 2004.
[39] M. Huysman, V. Wulf, “IT to support knowledge sharing in communities, towards a social capital analysis,” Journal of Information Technology, Vol. 21, pp. 40-51, 2006.
[40] R. L. Cross, A. Parker, and S. P. Borgatti, “A bird’s-eye view: Using social network analysis to improve knowledge creation and sharing,” Knowledge Directions, 2(1), pp. 48-61, 2000.
[41] A. Abbott, H. Pearson, “Fear of human pandemic grows as bird flu sweeps through Asia,” Nature 427, pp. 472-473, 2004.