
系統識別號 
U00020306200811192700 
中文論文名稱

社群網路模型與模擬 
英文論文名稱

Modeling and Simulation of Social Networks 
校院名稱 
淡江大學 
系所名稱(中) 
資訊工程學系博士班 
系所名稱(英) 
Department of Computer Science and Information Engineering 
學年度 
96 
學期 
2 
出版年 
97 
研究生中文姓名 
蕭炳南 
研究生英文姓名 
PingNan Hsiao 
學號 
893190180 
學位類別 
博士 
語文別 
英文 
口試日期 
20080523 
論文頁數 
52頁 
口試委員 
指導教授蔡憶佳 委員方鄒昭聰 委員陳伯榮 委員黃俊堯 委員顏淑惠 委員蔡憶佳

中文關鍵字 
社群網路模型
穴居人網路
成長網路
無尺度
小世界
複雜網路

英文關鍵字 
Social network model
caveman network
growing network
scalefree
smallworld
complex network

學科別分類 
學科別＞應用科學＞資訊工程

中文摘要 
在近幾年的研究中，社群網路模型已經被應用在許多的領域中，例如在流行病學的傳染模擬、謠言散布模擬、意見形成的模擬、電腦病毒模擬等，這些都是與我們生活息息相關的，因此社群網路模型的研究一直是值得關注的議題。
在社群網路模型中，大家著重關注的是網路中的叢集度(clustering coefficient)及無尺度(scalefree)特性。在2005年時，加州理工學院的Lun Li等人提出了對於smetric的觀察，這是對於網路中高連結節點與其他高連結節點彼此連結程度的觀察指標。我們所提出的新模型即針對此點來做加強。
在這篇論文中，我們提出了兩個社群網路模型，一是基於穴居人網路(caveman network)的靜態模型，一是基於成長網路(growing network)的動態模型。在模擬中，我們的網路模型都能提供叢集度及無尺度的特性，對於smetric，亦有非常好的效果。同時，我們從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) 'scalefree property' which has power law degree distribution, and (2) 'smallworld property' which has high clustering coefficient. In addition, the models are modified for high hub connectivity which is a new viewpoint in scalefree 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 ScaleFree 3
2.2 SmallWorld 4
2.3 Smetric 6
CHAPTER 3 Related Works 8
3.1 The Evolution of the Social Network of Scientific Collaborations 8
3.2 The Highly Clustered ScaleFree Networks 9
3.3 The Growing ScaleFree Networks with Tunable Clustering 10
3.4 The Growing ScaleFree Networks with SmallWorld Behavior 10
3.5 The Geography in a ScaleFree 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 ScaleFree 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 loglog degree distribution plot of the OAC, the slope of the line is 1.232. 17
Figure 3. The loglog degree distribution plot of the Grizzie, the slope of the line is 1.198. 18
Figure 4. The loglog degree distribution plot of the PFW, the slope of the line is 1.292. 18
Figure 5. The loglog rank versus degree distribution plot of OAC. 19
Figure 6. The loglog rank versus degree distribution plot of Grizzie 19
Figure 7. The loglog 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 loglog 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 loglog 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 loglog 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 loglog 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 loglog 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 loglog 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 loglog 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 wellknown collaboration graph,” Congressus Numerantium 108, pp. 129131, 1995.
[2] R. D. Castro, J. W. Grossman, “Famous trails to Paul Erdos,” Mathematical Intelligencer 21, pp. 5163, 1999.
[3] L. A. N. Amaral, A. Scala, M. Barthélémy, H. E. Stanley ,”Classes of smallworld networks,” Proceedings of the National Academy of Sciences, 97(21), pp.1114911152, 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. 907908, 2001.
[6] M. E. J. Newman, “The structure of scientific collaboration networks,” Proceedings of the National Academy of Sciences, 98(2), pp. 404409, 2001.
[7] D. J. Watts, S. H. Strogatz, “Collective dynamics of ‘smallworld’ networks,” Nature 393, pp. 440442, 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. 590614, 2002.
[9] K. Klemm, V. M. Eguiluz, “Highly clustered scalefree networks,” Physical Review E 65, pp. 036123, 2002.
[10] P. Holme, B. J. Kim, “Growing scalefree networks with tunable clustering,” Physical Review E 65, pp. 026107, 2002.
[11] K. Klemm, V. M. Eguiluz, “Growing scalefree networks with smallworld behavior,” Physical Review E 65, pp. 057102, 2002.
[12] C. P. Warren, L. M. Sander, and I. M. Sokolov, “Geography in a scalefree 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. PastorSatorras, A. DíazGuilera, 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 scalefree 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. 99120, 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.E87D No.6, pp. 14381445, 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 20022003 epidemic,” Philosophical Transactions: Biological Sciences 359, pp. 10911105, 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. 7181, 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. 631643, 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, “Heavytailed probability distributions in the World Wide Web,” In A Practical Guide To Heavy Tails, Chap.1, pp. 325, 1998.
[26] R. Albert, H. Jeong, A.L. Barabási, “Internet: Diameter of the WorldWide Web,” Nature 401, pp. 130131, 1999.
[27] Y. Tsai, C.C. Lin, P.N. Hsiao, “Heavy tail distribution in email network,” Proceedings of the 2002 SoftCOM, pp. 167170, 2002.
[28] H. Ebel, L.I. Mielsch, S. Bornholdt, “Scalefree topology of email 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. 4897, 2002.
[30] R. Tanaka, T.M. Yi, J. Doyle, “Some protein interaction data do not exhibit power law statistics,” FEBS Letters, Vol.579, pp.51405144, 2005.
[31] L. Li, D. Alderson, J. C. Doyle, W. Willinger, “Towards a theory of scalefree graphs: definition, properties, and implications,” Internet Mathematics, 2(4), pp. 431523, 2006.
[32] A.L. Barabási, R. Albert, “Emergence of scaling in random networks,” Science 286, pp. 509512, 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. 226251, 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. 4051, 2006.
[40] R. L. Cross, A. Parker, and S. P. Borgatti, “A bird’seye view: Using social network analysis to improve knowledge creation and sharing,” Knowledge Directions, 2(1), pp. 4861, 2000.
[41] A. Abbott, H. Pearson, “Fear of human pandemic grows as bird flu sweeps through Asia,” Nature 427, pp. 472473, 2004. 
論文使用權限 
同意紙本無償授權給館內讀者為學術之目的重製使用，於20080609公開。同意授權瀏覽/列印電子全文服務，於20080609起公開。 


