淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


  查詢圖書館館藏目錄
系統識別號 U0002-2301200723240900
中文論文名稱 通訊網路分析與模型建置
英文論文名稱 Analysis and Modeling of Communication Networks
校院名稱 淡江大學
系所名稱(中) 資訊工程學系博士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 95
學期 1
出版年 96
研究生中文姓名 林政錦
研究生英文姓名 Cheng-Chin Lin
學號 890190019
學位類別 博士
語文別 英文
口試日期 2006-12-30
論文頁數 97頁
口試委員 指導教授-蔡憶佳
委員-方鄒昭聰
委員-黃俊堯
委員-施國琛
委員-陳伯榮
委員-蔡憶佳
中文關鍵字 小世界網路  無尺度網路  s-度量標準  通訊網路  網路模型  連線交換 
英文關鍵字 small-world network  scale-free network  s-metric  communication network  network model  edge switching 
學科別分類 學科別應用科學資訊工程
中文摘要 在現代研究中,網路模型已經被應用在許多不同的領域中。例如社會學(Social science)、代謝網路(Metabolic network)、生物學,網頁圖(Webpage graph)和網際網路等等的網路。在研究網路模型上,有很多的網路特性被用來量測網路模型,例如群聚性,節點度分佈,平均網路路徑長度和s-度量標準。依據網路特性量測的結果,網路模型除了被描述成隨機網路(Random netowrks)以外,而且也可以描述成小世界網路(Small-world networks)或者無尺度網路(Scale-free networks)。因此,通信網路的分析和模型化,可以利用量測網路特性的方式作為分析或是建立網路模型的依據,以期結果能接近實際網路。為了要了解目前現行的網路的特性以及將來設計網路通訊協定時的依據,一個精確的通訊網路模型是一個很重要的課題。
在這篇論文中我們量測通信網路,並且基於量測的結果提出建立網路模型的方法。在論文中主要是探討的議題是如何建立通信網路模型以及利用已知的各種網路特性來評估分析網路。我們提出二個建立人際通信網路模型的方法。這些方法是利用社群緊密關係(Socail affinity)的概念來實踐在實際網路中的人際的緊密關係特性。
通常網路特性都只是統計的結果,因此網路特性並沒有辦法分辨網路拓撲之間的不同。在無尺度網路中,冪次律分佈(Power-law distribution)只能表示網路中的節點分支度分佈的特性。因此,可能有無尺度網路具有相同的網路冪次律分佈特性,而事實上這些網路的網路拓撲是不同的。例如,假設在一個網路中有二個分離的連結(edge)。這二個分離的連結可以重新連接成新的二條連結並且保持原來的節點分支度。這樣就會有二個有不同網路拓撲的網路,但是具有相同的節點分支度。我們提出連結交換演算法(Edge switching algorithm)來研究在具有相同網路特型的網路之間,這些網路的差異性。依據我們的模擬結果顯示,我們可以在無尺度網路中可以調整網路叢集度以及s-度量標準的高低,但調整後的網路仍保有相同的無尺度網路的特性。
英文摘要 Network models are commonly used in many branches of science, such as social networks in sociology, web page graph and Internet in computer science, etc. Many network properties are proposed to studying network models, such as clustering, node degree distribution, network path length and s-metric. From network properties, network models are not only described as random networks but also described as small-world networks or scale-free networks. The analysis and modeling of communication networks therefore rely on those measurements of networks to verify that the generated network models are similar to real data. Accurate modeling of communication networks is an important issue in both understanding the current networks and designing future communication protocols.
This thesis measures communication network data and proposes network models based on those measurements. Issues covered in this thesis include the modeling of communication networks and the evaluation and analysis of networks based on some well-known network properties. Two models are proposed to modeling human communication networks. The proposed network models use the concept of social affinity to capture the closeness property presented in real world networks.
Usually, network properties are based on aggregate statistics and are not good indicators to differentiate different topologies. In scale-free networks, the power law distribution only related to graph connectivity. Therefore, the scale-free networks which have different topologies may have equal power-law degree distributions. For example, assume that, there are two separate edges in a network. The two edges can be rewired and preserved node degree. And then, there exist two networks which have different topologies and node degree preserving. Edge switching algorithms are proposed to studying differences between networks that have same network properties. The simulation results showed that the clustering coefficient and s-metric of scale-free networks can be tuned while preserving scale-free property.
論文目次 CONTENTS
ABSTRACT VI
LIST OF FIGURE X
LIST OF TABLE XIII
CHAPTER 1 INTRODUCTION 1
1.1 WHAT ARE NETWORKS? 4
1.2 NETWORK PROPERTIES 6
CHAPTER 2 NETWORK MODELS 10
2.1 RANDOM NETWORKS 10
2.2 SMALL-WORLD NETWORKS 12
2.3 SCALE-FREE NETWORKS 16
2.4 MODELING OF SMALL-WORLD AND SCALE-FREE 19
2.5 SUMMARY 19
CHAPTER 3 AFFINITY BASED NETWORK MODELS 21
3.1 SOCIAL AFFINITY 21
3.2 NOTATIONS 23
3.3 PA MODEL 24
3.4 NPA MODEL 33
3.5 SIMULATION RESULTS 43
3.6 SUMMARY 44
CHAPTER 4 WEIGHTED NETWORKS 46
4.1 WEIGHT NETWORKS 46
4.2 RELATED WORKS 47
4.3 WEIGHT 50
4.3 NODE WEIGHT 51
4.4 WEIGHTED CLUSTERING COEFFICIENT 52
4.5 EMPIRICAL RESULTS 54
4.6 SUMMARY 59
CHAPTER 5 GROUP GROWTHS 60
5.1 DEFINITIONS 60
5.2 GROUP COMMUNICATIONS 60
5.3 GROUP GROWTH 62
5.4 SUMMARY 63
CHAPTER 6 EDGE SWITCHING 64
6.1. NOTATIONS AND DEFINITIONS 65
6.2. CLUSTERING COEFFICIENT 66
6.3 SIMULATIONS OF CONTROLLING CLUSTERING COEFFICIENT 76
6.4 DEFINITIONS OF EDGES 80
6.5 THE S-METRIC 82
6.6 SMAX AND SMIN ALGORITHMS 85
6.7 SUMMARY 90
CHAPTER 7 CONCLUSIONS AND FUTURE WORKS 91
REFERENCES 94

參考文獻 References:
[1] Y. Tsai, C.-C. Lin, P.-N. Hsiao, “Heavy Tail Distribtion in Email Network”, Proceedings of the 2002 SoftCOM, 2002, pp.167-170
[2] M. E. J. Newman, S. Forrest and J., Balthrop, “Email networks and the spread of computer viruses”, Phys. Rev. E 66, 035101, 2002.
[3] D. J. Watts, P. S. Dodds and M. E. J. Newman, “Identity and search in social networks”, Science 296, 2002, pp.1302-1305
[4] H. Jeong, B. Tombor, R. Alert, Z. N. Oltvai and A.-L. Barabái, “The large-scale organization of metabolic networks”, Nature 407, 2000, pp.651-654
[5] S. L. Pimm, “Food Webs”, University of Chicago Press, Chicago, 2nd ed, 2002.
[6] M. E. Crovella, M. S. Taqqu, A. Bestavros, “Heavy-tailed probability distributions in the World Wide Web”, in A Practical Guide To Heavy Tails, chapter 1, pp.3-25, Chapman & Hall, New Work, 1998
[7] R. Albert, H. Jeong, A.-L. Barabási, “Internet: Diameter of the World Wide Web”, Nature 401, 1999, pp.130-131
[8] T. Bu and D. Towsley, “On distinguishing between internet power law topology generator”, IEEE Infocom: The 21st Annual Joint Conference, NY, USA, 2002
[9] K. L. Calvert, M.B. Doar, and E. W. Zegura, “Modeling Internet topology”, IEEE Communication Magazine, 35(6):, 1997 pp.160-163.
[10] R. Kumer, P. Raghavan, S. Rajalopagan, D. Sivakumar, and A. S. Tomkins Proceeding of 9th ACM Symposium on Principles of Data Systems, pp. 1, 1999 .
[11] M. Faloutsos, P. Faloutsos, and C. Faloutsos, 1999, Computer Communication Rev. 29, 251.
[12] R. Govindan, and H. Tangmunarunkit, “Heuristics for Internet Map Discovery,” proceedings of IEEE INFOCOM 2000, Tel Aviv. Israel
[13] A.-L. Barabasi, & R. Albert, “Emergence of Scaling in Random Networks,” Science 286, 509-511, 1999
[14] S. Render, "How popular is your paper? An empirical study of the citation distribution", Eur. Phys. J B 4, 131-134 , 1998.
[15] J. Kleinfeld, “Six degree of separation: Urban myth?”, Psychology Today, Mar/Apr 2002
[16] S. Milgram. “The small world problem”. Psychology Today, May 1967. pp. 60-67
[17] M. E. J. Newman, S. H. Strogatz, and D. J. Watts. “Random graphs with arbitrary degree distributions and their applications”. Physical Review E, 64(2):026118, 2001
[18] D. J. Watts, D. H. Strogatz, “Collective dyanmics of 'small-world' networks,” Nature 393, 1998, pp.440-442.
[19] R. Albert, A.-L. Barabái, “Statistical mechanies of complex networks”, Reviews of Modern Physics, Jan. 2002, Volumne 74, pp.48-97
[20] M.E.J. Newman, D. J. Watts, and H. Strogatiz, Random graph models of social networks, Proceedings of the National Academy of Sciences, 2002, 99(Suppl. 1): 2566-2572,
[21] J. Davidsen, H. Ebel, and S. Bornholdt. “Emergence of a small world from local interactions: Modleing acquaintance networks” Physical Review Letter, 88(12):128701, 2002
[22] Y. Tsai, P.-N. Hsiao, C.-C. Lin and C.-C. Lin, “A Small-World and Scale-Free Model for Email Communication”, Proceedings of the 2003 IEEE SoftCOM, October 2003, pp.242-246.
[23] P. Erdös, A. Rényi, “On Random Graphs,” Publications of the Mathematical 6, pp. 290-297, 1959.
[24] P.Erdős, A. Rényi, “On the evolution of random graphs,” Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5, pp.17-61. 1960
[25] B. Bollobás, “Random Graphs,” Academic Press, New York, 1985.
[26] Chung, F., and L. Lu, “The Diameter of Sparse Random Graphs”, Adv. Appl. Math. 26, 257, 2001
[27] Amaral, L. A. N., Scala, A., Barthelemy, M., and Stanley, H. E., "Classes of small-world networks," Proceedings Natl. Acad, Sci. USA 97, pp.11149-11152, 2000
[28] A. Barrat, M. Barthelemy, R. Pastor-Satorras, and A. Vespignani, "The architecture of complex weighted networks," PROC.NATL.ACAD.SCI.USA, vol. 101, pp. 3747, 2004.
[29] S.H. Yook, H. Jeong, and A.-L. Barab´asi, and Y. Tu, Phys. Rev. Lett. 86, 5835, (2001).
[30] D. Zhang, S. Trimper, B. Zheng, and P.M. Hui, Phys. Rev. E 67, 040102, (2003).
[31] K. Park, Y.-C. Lai, and N. Ye, Phys. Rev. E 70, 026109 (2004).
[32] A. Barrat, M. Barth´elemy, R. Pastor-Satorras, and A. Vespignai, Phys. Rev. 70, 066149 (2004)
[33] A. Barrat, M. Barth´elemy, R. Pastor-Satorras, and A. Vespignai, Proc. Natl. Acad. Sci. U.S.A.
[34] D. J. Watts, S.H. Strogatz, "Collective dynamics of small-world networks," Nature 393, pp.440-442, 1998
[35] R. de Castro and J.W. Grossman, “Famous trails to Paul Erdős," Mathematical Intelligencer 21, pp. 51-63, 1999
[36] J.W. Grossman and P.D.F. Ion, "On a portion of the well-known collaboration graph," Congressus Numerantium 108, pp.129-131, 1995
[37] Q. Chen, H. Chang, R. Govindan, S. Jamin, S.J. Shenker and W. Willinger, "The origin of power laws in Internet topologies revisited," INFOCOM 2002, Vol 2, pp.23-27, 2002
[38] M. Faloutsos, P. Faloutsos and C. Faloutsos, "On power-law relationships of the Internet topology," Computer Communication review 29, pp.251-262, 1999
[39] P. Sen, S. Dasgupta, A. Chatterjee, P.A. Sreeram, G.Mukherjee and S.S.Manna, "Small-world properties of the Indian railway network," Preprint cond-mat/ 0208535, 2002
[40] J.G. White, E. Southgate, J.N. Thompson and S. Brenner, “The structure of the nervous system of the nematode C. Elgans," Phil. Trans. Royal Soc. London. Series B, Biol Scien. Vol.314, Issue 1165 (Nov 12, 1986), 1-340
[41] S.N. Dorgovtesev and J.F.F. Mendes, and A.N. Samulhin, “Structure of growing networks with preferential linking,” Physical Review Letters, 2000, 85 (21) :4633-4636
[42] T. Bu and D. Towsley, “On distinguishing between internet power law topology generators,” IEEE Proceeding of INFOCOM, Los Alamitos, CA, USA, 2002.
[43] Y. Tsai, C.-C. Lin, P.-N. Hsiao, “Modeling Email Communications,” IEICE Transactions on Information and Systems, 2004, Vol.E87-D No.6 p.1438
[44] Barabisi, A.-L., and R. Albert. “Emergence of scaling in random networks.” Science 286, pp. 509-512, 1999.
[45] Bilke, S. and C. Peterson. “Topological Properties of Citation and Metabolic Networks.” Physical Review, E 64, 036106, 2001.
[46] Faloutsos, M., P. Faloutsos, and C. Faloutsos. “On Power-Law Relationships of the Internet Topology.” ACM SIGCOMM ’99, Computer Communication Review 29, pp. 251-263, 1999.
[47] Ferrer-i-Cancho, R. and R.V. Sole, “The Small World of Human Language.” Proceedings of the Royal Society London B 268, 2261-2266, 2001.
[48] De Moura, A.P.S., Y.C. Lai, and A.E. Motter. “Signatures of Small-World and Scale-Free Properties in Large Computer Programs.” Physical Review E 68, 017102, 2003.
[49] Raine, D.J. and V. Norris. “Network Structure of Metabolic Pathways.” Journal of Biological Physics and Chemistry 1, 89-94, 2001.
[50] Vazquez, A., R. Pastor-Satorras, and A. Vespignani. “Large-Scale Topological and Dynamical Properties of the Internet.” Physical Review E, 65, 066130, 2002.
[51] Wagner, A. and D.A. Fell. “The Small World Inside Large Metabolic Networks.” Proceedings of Royal Society London B 268, 1803-1810, 2001.
[52] Y. Tsai and C.-C. Lin, "Affinity Based Email Communication Models," WSEAS Information Sciences and Applications, pp. 998-1006, Issue 6, Vol 3, June. 2006 ( EI )
[53] Y. Tsai, C.-C. Lin and C.-C. Lin, "Characteristics of Weighted Email Communications", Proceedings of ICICS '05, IEEE , Bangkok, Dec. 6-9 2005, pp 399~403
[54] Y. Tsai and C.-C. Lin , "Node Degree Sequence Preserving and Constant Clustering -Coefficient Link Transformation," WSEAS Information Sciences and Applications, pp.1661-1668, Issue 9, Vol 3, September, 2006 ( EI )
[55] L. Li, D. Alderson, R. Tanaka, J. C. Doyle, and W. Willinger, “Towards a Theroy of Scale-Free Graph: Definition, Properties, and Implications.” arXiv:cond-mat /0501169 v2, 2005
[56] Y. Tsai, C.-C. Lin P.-N. Hsiao and W.-F. Huang, "Node Degree Sequence Preserving and Controlling S-metric," Accepted by ICACT’07, Seoul Korea, Feb. 2007
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2010-02-02公開。
  • 不同意授權瀏覽/列印電子全文服務。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信