關鍵詞：復雜網絡，中心化，軟件系統，集群分析
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 論文組織結構 2
2. 基本理論知識及其應用 3
2.1 復雜網絡 3
2.1.1 概念 3
2.1.2 度量參數 6
2.1.3 研究意義 7
2.2 復雜網絡中心化 10
2.2.1 度指標 11
2.2.2 緊密度指標 12
2.2.3 特征向量指標 13
2.2.4 介數指標 14
2.2.5 流介數指標 15
2.3 軟件系統網絡化特征 16
2.4 集群分析 18
3. 算法設計 20
3.1 算法設計分析 20
3.1.1 軟件系統拓撲圖 20
3.1.2 交通網絡的中心化 21
3.2 算法思想 22
4. 算法實現 24
4.1 開發環境及工具 24
4.2 算法實現 24
4.2.1 用戶輸入界面實現 24
4.2.2 節點圖形表示 25
4.2.3 計算最短路徑 26
4.2.4 計算Centrality值 27
4.2.5 發現Cluster 28
4.3 結果分析 28
4.3.1 開發難點及相關策略 28
4.3.2 工作展望及見解 29
4.3.3 創新思想 29
5. 總結 31
致謝 32
參考文獻 33
附錄 35
