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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2607201016202900
中文論文名稱 用區域連線交換技術來控制有向和有權重網路的叢聚度
英文論文名稱 Using local link switching algorithm to control directed and weight network clustering coefficient
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 98
學期 2
出版年 99
研究生中文姓名 蔡凱翔
研究生英文姓名 Kai-Siang Tsai
學號 697410610
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2010-06-28
論文頁數 38頁
口試委員 指導教授-陳伯榮
委員-蔡憶佳
委員-林慶昌
委員-陳伯榮
中文關鍵字 叢聚係數  有向網路 
英文關鍵字 clustering coefficient  directed network 
學科別分類 學科別應用科學資訊工程
中文摘要 過去幾十年來很多複雜網路都被研究分析,在分析中,叢聚度是重要的概念,有關網路模型緊密性的一個主要特徵,它是一個重要的網路統計數值在許多真實網路,尤其是近幾年發展迅速的社群網路、通訊網路。在此論文中提出在保持各個節點的分支度不變的情況下用維持連線數不變的連線重接演算法和區域連線交換技術來增加網路叢聚度,所以它可以被廣泛的用在製造出相似的模型從已選出的網路模型。這個演算法是基於區域鄰接點的資訊來執行。如何在有向和有權重的網路中執行這演算法將是本論文的研究重點。
英文摘要 Over the past decade the studies of complex networks have been analyzed and researched. In analyzing Clustering coefficient is a important concept Clustering coefficient characterizes the relative tightness of a network and is a defining network statistics that appears in many “real-world” network data.
This paper proposed a local link switching algorithm which effectively increases the clustering coefficient of a directed weight network while preserving the network node degree distributions. This link switching algorithm is based on local neighborhood information. Link switching algorithm is widely used in producing similar networks with the same degree distribution, that is, it is used in ‘sampling’ networks from the same network pool. How to use this algorithm to implement in directed and weight network is major study in this paper.
論文目次 第一章 緒論 1
1.1 研究動機與相關研究 1
1.2 研究方法 1
1.3 預期貢獻 2
第二章 背景知識及相關研究 3
2.1 什麼是網路 3
2.2 真實網路 4
2.3 圖形結構 5
2.3.1相鄰(adjacent) 5
2.3.4 方向性 5
2.3.2 分支度 6
2.3.3 分支度序列(degree sequence) 6
2.5 權重圖形 7
2.5.1 無向權重圖形 7
2.5.2 權重圖形 7
2.6 網路模型介紹 8
2.6.1 隨機網路 8
2.6.2 小世界網路 8
2.7 叢聚度 11
2.7.1 無向具權重叢聚度 12
2.7.2 有向無權重叢聚度[6] 13
2.7.3 有向權重叢聚度 14
2.7.4 叢聚度高的優點 15
2.8 連線交換演算法 17
2.8.1 維持連線數不變的連線交換演算法 17
2.8.2 區域連線交換演算法[9] 18
第三章 實驗過程 21
3.1 權重網路 21
3.1.1 權重網路模型 21
3.1.2 提高在權重網路下的叢聚度 21
3.1.3 權重邊的設定 24
3.2 有向網路 24
3.2.1 有向網路模型 24
3.2.2 提高在有向網路下的叢聚度 24
第四章 實驗結果 28
4.1 無向權重網路實驗 28
4.2 有向網路實驗 30
第五章 結論與未來研究方向 33
參考資料 34
附錄-英文論文 35

圖目錄
圖 1 基本網路圖範例 3
圖 2 臉書網路(人際關係網路圖範例) 4
圖 3 全球資訊網路圖 5
圖 4 無向網路圖 6
圖 5 有向網路圖 6
圖 6 分支度範例圖 6
圖 7 權重網路圖 7
圖 8 有向權重網路圖 7
圖 9 隨機網路圖 8
圖 10 小世界網路的產生情形 9
圖 11 小世界網路圖發展過程的路徑長度和叢聚度變化情形 9
圖 12 小世界網路圖 10
圖 13 計算節點i的叢聚度 12
圖 14 有向圖叢聚度解說 14
圖 15 網路圖範例 16
圖 16 圖15(a)衍生介紹從傳染病來觀察叢聚度低的缺點 16
圖 17 由圖15(b)衍生介紹從傳染病來觀察叢聚度高的優點 17
圖 18 交換連線的過程 18
圖 19 區域交換連線演算法 19
圖 20 三種可進行區域連線交換技術的圖型 20
圖 21 找出j1,i2,j2的過程圖 23
圖 22 對於(i1,i2)、(j1,j2)轉換成(i1,j1)、(i2,j2)有向連線交換的所有情形 26
圖 23 隨機權重網路經過區域連線交換技術後叢聚度變化結果 28
圖 24 隨機權重網路經過區域連線交換技術平均最短路徑變化結果 29
圖 25 小世界權重網路經過區域連線交換技術後叢聚度變化結果 29
圖 26 小世界權重網路經過區域連線交換技術平均最短路徑變化結果 30
圖 27 有向連通隨機網路經過區域連線交換技術後叢聚度變化結果 31
圖 28 獼猴大腦半球外皮層連通網路經過區域連線交換技術後叢聚度變化結果 31
圖 29 線上社群連通網路經過 區域連線交換技術後叢聚度變化結果 32

參考文獻 1. Scott, J., Social Network Analysis. 1988. p. 109-127.
2. Albert, R., H. Jeong, and A.-L. Barabasi, Internet: Diameter of the World-Wide Web. Nature, 1999. 401(6749): p. 130-131.
3. Renyi, E.a., On the evolution of random graphs. publications of the mathematical institute, 1960. 6 p. 290-297.
4. Watts, D.J. and S.H. Strogatz, Collective dynamics of /`small-world/' networks. Nature, 1998. 393(6684): p. 440-442.
5. Onnela, J.-P., et al., Intensity and coherence of motifs in weighted complex networks. Physical Review E, 2005. 71(6): p. 065103.
6. Fagiolo, G., Clustering in complex directed networks. Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), 2007. 76(2): p. 026107-8.
7. Maslov, S., K. Sneppen, and A. Zaliznyak, Detection of topological patterns in complex networks: correlation profile of the internet. Physica A: Statistical and Theoretical Physics, 2004. 333: p. 529-540.
8. Lin, Y.T.a.C.-C., Node Degree Sequence Preserving and Constant Clustering -Coefficient Link Transformation. WSEAS Information Sciences and Applications, 2006. 3(9): p. 1661-1668.
9. YihjiaTsai, Clustering Coefficient Increasing Local Link Switching Algorithm. 2008 ICS, 2008.




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


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