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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2607201015130200
中文論文名稱 高連線密度下的叢聚係數網路
英文論文名稱 Extreme Clustering Coefficients In High Edge Density Networks
校院名稱 淡江大學
系所名稱(中) 資訊工程學系資訊網路與通訊碩士班
系所名稱(英) Master's Program in Networking and Communications, Department of Computer Science and Information En
學年度 98
學期 2
出版年 99
研究生中文姓名 梁捷翔
研究生英文姓名 Chieh-Hsiang Liang
電子信箱 lgsjeffrey@gmail.com
學號 697420106
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2010-06-28
論文頁數 40頁
口試委員 指導教授-蔡憶佳
委員-林慶昌
委員-陳伯榮
委員-蔡憶佳
中文關鍵字 小世界網路  叢聚係數 
英文關鍵字 Small World  Clustering Coefficients 
學科別分類 學科別應用科學資訊工程
中文摘要 根據我們的研究,可得到對於高密度無權重網路下最大與最小的叢聚係數的上下限。我們並設計了網路拓樸來產生最大最小叢聚係數網路,此網路拓樸擁有的最大特徵是具有極端的叢聚係數。和常用的網路模型:隨機網路模型、小世界網路模型相比較,我們提出的最大與最小模型在平均網路叢聚係數上與已知的網路模型相比更高(低),並且發現了在高密度網路結構下,網路直徑將不再是一個特殊的網路特徵,每當網路拓樸增加連線數時,每種網路模型的網路直徑均會下降且網路直徑都為同一值,這個現象說明了,在高密度網路下,網路直徑已不會受到增加新連線而會產生巨大的變化
英文摘要 This paper proposed two models with extreme average clustering coefficients and small path length properties for high edge density network. High density networks are common in the analysis of social networks and biological networks. This paper studies networks with extreme statistical properties, that is, max/min clustering coefficients and short average distances. In addition to those properties, the proposed models indicated that in addition to the existing small-world network model and random network model, there are other network models that may produce clustering coefficients filling the gap between those two models and the maximal achievable clustering coefficients.
論文目次 第一章 緒論 1
第一節 網路模型 1
第二節 研究目的 2
第三節 研究方法 2
第二章 相關研究 2
第三章 背景知識 3
第一節 叢聚係數(Clustering coefficient) 3
第二節 網路直徑(Network diameter) 4
第三節 網路密度(Edge density) 4
第四節 網路模型介紹 5
第一項 隨機網路(Random network) 6
第二項 小世界網路(Small world network) 7
第三項 無尺度網路(Scale free network) 9
第五節 權重網路 10
第四章 實驗結果 10
第一節 符號定義 10
第二節 實驗模型 12
第一項 最大叢聚係數網路 12
第二項 最小叢聚係數網路 17
第三項 最多三角連結網路 20
第五章 實驗與結果 21
第六章 結論與未來展望 29
參考文獻 30
附錄-英文論文 31

圖 1叢聚係數範例(以邊為參考) 3
圖 2 網路直徑範例(此網路的網路直徑為3) 4
圖 3 規律網路範例圖 5
圖 4 格子網路範例圖 6
圖 5 隨機網路範例圖 7
圖 6 小世界網路範例圖 8
圖 7 無尺度網路範例圖 9
圖 8 網路拓樸 12
圖 9 網路拓樸 13
圖 10 網路拓樸 13
圖 11 網路拓樸 14
圖 12 網路拓樸 14
圖 13 網路拓樸 15
圖 14 網路拓樸 15
圖 15 網路拓樸 16
圖 16 網路拓樸 16
圖 17 網路拓樸 17
圖 18 二分網路範例圖 18
圖 19 二分網路連線情況 18
圖 20 二分網路子網路情形 19
圖 21 二分網路子網路最大連接情況 19
圖 22 二分網路子子網路連線情形 20
圖 23 叢聚係數模擬結果(n=30) 21
圖 24 網路直徑模擬結果(n=30) 22
圖 25 叢聚係數範例(以三角形數為參考) 23
圖 26 交換連線後的叢聚係數情形(n=30) 24
圖 27 交換連線後的叢聚係數情形(n=50) 25
圖 28 網路中三角連結數目 26
圖 29 叢聚係數模擬結果 26
圖 30 擁有尾巴節點的三角連結網路 27
圖 31 叢聚係數模擬結果(n=50) 28
圖 32 網路直徑模擬結果(n=50) 28


參考文獻 [1] R. Luce and A. Perry, "A method of matrix analysis of group structure," Psychometrika, vol. 14, pp. 95-116, 1949.
[2] P. Erdös and A. Rényi, "On random graphs. I," Publ. Math. Debrecen, vol. 6, pp. 290-297, 1959.
[3] D. J. Watts and S. H. Strogatz, "Collective dynamics of `small-world' networks," Nature, vol. 393, pp. 440-442, 1998.
[4] A.-L. Barabási and R. Albert, "Emergence of Scaling in Random Networks," Science, vol. 286, pp. 509-512, October 15, 1999 1999.
[5] P. Fu and K. Liao, "An Evolving Scale-free Network with Large Clustering Coefficient," in Control, Automation, Robotics and Vision, 2006. ICARCV '06. 9th International Conference on, 2006, pp. 1-4.
[6] P. Holme and B. J. Kim, "Growing scale-free networks with tunable clustering," Physical Review E, vol. 65, p. 026107, 2002.
[7] T. Schank and D. Wagner, "Approximating clustering coefficient and transitivity," Journal of Graph Algorithms and Applications, vol. 9, 2005.
[8] M. E. J. Newman, "Models of the Small World," Journal of Statistical Physics, vol. 101, pp. 819-841, 2000.
[9] K. Gabriela and J. H. Desmond, "A clustering coefficient for weighted networks, with application to gene expression data," vol. 20, pp. 263-271, 2007.
[10] S. Wasserman and K. Faust, Social network analysis: Methods and applications: New York, NY, US: Cambridge University Press, 1994.
[11] C. J. Melián and J. Bascompte, "FOOD WEB COHESION," Ecology, vol. 85, pp. 352-358, 2004.
[12] K. Klemm and V. M. Eguíluz, "Highly clustered scale-free networks," Physical Review E, vol. 65, p. 036123, 2002.
[13] J.-P. Onnela, J. Saramäki, J. Kertész, and K. Kaski, "Intensity and coherence of motifs in weighted complex networks," Physical Review E, vol. 71, p. 065103, 2005.
[14] I. E. Antoniou. and E. T. Tsompa., "Statistical Analysis of Weighted Networks," Discrete Dynamics in Nature and Society, vol. 2008, p. 16, 2008.

論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2010-07-27公開。
  • 同意授權瀏覽/列印電子全文服務,於2010-07-27起公開。


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