論文字數(shù):20022,頁數(shù):46 有開題報告，任務(wù)書

摘   要
 現(xiàn)實世界中的許多復雜系統(tǒng)都可以使用網(wǎng)絡(luò)模型進行描述。復雜網(wǎng)絡(luò)的結(jié)構(gòu)和性質(zhì)研究已經(jīng)成為引人注目的領(lǐng)域。對復雜網(wǎng)絡(luò)進行中心化，發(fā)現(xiàn)復雜網(wǎng)絡(luò)中的重要節(jié)點，具有重要的應用價值。
 軟件系統(tǒng)其實也是一類非常重要的復雜網(wǎng)絡(luò)，不過目前為止對這方面的研究非常少見。軟件一般由許多相互關(guān)聯(lián)的單元和子系統(tǒng)（如子程序，類，源程序文件，庫文件等）以及這些組成元素間的交互和協(xié)作關(guān)系組成。軟件的組成元素可以看成復雜網(wǎng)絡(luò)中的節(jié)點，而他們之間的相互調(diào)用或是消息通信關(guān)系可以看成復雜網(wǎng)絡(luò)中的邊。目前，軟件系統(tǒng)規(guī)模日趨龐大，系統(tǒng)間的協(xié)作日趨緊密，特別是開源軟件的發(fā)展更促進這一趨勢。將復雜的大型軟件系統(tǒng)分解成相對獨立的軟件集群，具有重要的研究意義。
 本課題運用復雜網(wǎng)絡(luò)中心化（Centrality）思想和集群（Cluster）分析思想，針對軟件系統(tǒng)這類復雜網(wǎng)絡(luò)，設(shè)計并實現(xiàn)了一種通過計算各邊的介數(shù)指標值找到核心節(jié)點，然后移除指標值大的節(jié)點邊從而發(fā)現(xiàn)軟件系統(tǒng)代碼集群的算法，達到分解大型軟件系統(tǒng)的目的，將復雜問題簡單化。
 本論文詳細闡述了算法的設(shè)計與實現(xiàn)過程，簡述了設(shè)計本算法所依賴的理論基礎(chǔ)，包括復雜網(wǎng)絡(luò)、復雜網(wǎng)絡(luò)中心化、集群分析、軟件系統(tǒng)等；著重介紹了在實現(xiàn)過程中，計算最短路徑使用的弗洛伊德算法，判斷回路的深度優(yōu)先遍歷算法，C#圖形編程等。

關(guān)鍵詞：復雜網(wǎng)絡(luò)，中心化，軟件系統(tǒng)，集群分析
The Design and Realization of Cluster Detection Algorithm
Based On Centrality
Abstract                                                

 Most complex systems in nature can be described by models of networks, exploring the structure and property of complex networks has become one of hot topics in science. Centralization of complex networks, which can help us find important nodes in complex networks, is of great practical value in many applications.
 Software systems represent another important class of complex networks, which to date have received relatively little attention in this field. Software is built up out of many interacting units and subsystems at many levels of granularity (subroutines, classes, source files, libraries, etc.), and the interactions and collaborations of those pieces can be used to define networks or graphs that form a skeletal description of a system. Nowadays, the scale of software systems and the collaboration among software systems tend to be more huge and closer. What’s more, the development of open source software makes this trend badly. Then it is significantly useful to decompose the software system into smaller independent software clusters.
 Aimed at the software systems, according to the centralization of complex networks and cluster analysis principles，this research have been able to design and implement an algorithm that through finding and removing the key edges whose centrality value are the maximal to detecting the software clusters, which simplify the complex software networks.
 This paper detailedly discusses the design and development progress of this algorithm; simply talks about the theory the algorithm based on, including complex networks, centralization, cluster analysis, software systems, etc; mainly introduces the Floyd algorithm counting all the shortest path of all the nodes, the DFS algorithm judging the connectivity of graphic and the C# graphic programming, etc.
Key Words：Complex networks, Centralization, Software systems, Cluster analysis.
目   錄
1. 緒論 1
1.1 課題背景及來源 1
1.2 課題研究的意義 1
1.3 論文組織結(jié)構(gòu) 2
2. 基本理論知識及其應用 3
2.1 復雜網(wǎng)絡(luò) 3
2.1.1 概念 3
2.1.2 度量參數(shù) 6
2.1.3 研究意義 7
2.2 復雜網(wǎng)絡(luò)中心化 10
2.2.1 度指標 11
2.2.2 緊密度指標 12
2.2.3 特征向量指標 13
2.2.4 介數(shù)指標 14
2.2.5 流介數(shù)指標 15
2.3 軟件系統(tǒng)網(wǎng)絡(luò)化特征 16
2.4 集群分析 18
3. 算法設(shè)計 20
3.1 算法設(shè)計分析 20
3.1.1 軟件系統(tǒng)拓撲圖 20
3.1.2 交通網(wǎng)絡(luò)的中心化 21
3.2 算法思想 22
4. 算法實現(xiàn) 24
4.1 開發(fā)環(huán)境及工具 24
4.2 算法實現(xiàn) 24
4.2.1 用戶輸入界面實現(xiàn) 24
4.2.2 節(jié)點圖形表示 25
4.2.3 計算最短路徑 26
4.2.4 計算Centrality值 27
4.2.5 發(fā)現(xiàn)Cluster 28
4.3 結(jié)果分析 28
4.3.1 開發(fā)難點及相關(guān)策略 28
4.3.2 工作展望及見解 29
4.3.3 創(chuàng)新思想 29
5. 總結(jié) 31
致謝 32
參考文獻 33
附錄 35