关键词：复杂网络，中心化，软件系统，集群分析
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
