基于Centrality的Cluster发现算法设计与实现

论文字数:20022,页数:46 有开题报告，任务书

摘   要
 现实世界中的许多复杂系统都可以使用网络模型进行描述。复杂网络的结构和性质研究已经成为引人注目的领域。对复杂网络进行中心化，发现复杂网络中的重要节点，具有重要的应用价值。
 软件系统其实也是一类非常重要的复杂网络，不过目前为止对这方面的研究非常少见。软件一般由许多相互关联的单元和子系统（如子程序，类，源程序文件，库文件等）以及这些组成元素间的交互和协作关系组成。软件的组成元素可以看成复杂网络中的节点，而他们之间的相互调用或是消息通信关系可以看成复杂网络中的边。目前，软件系统规模日趋庞大，系统间的协作日趋紧密，特别是开源软件的发展更促进这一趋势。将复杂的大型软件系统分解成相对独立的软件集群，具有重要的研究意义。
 本课题运用复杂网络中心化（Centrality）思想和集群（Cluster）分析思想，针对软件系统这类复杂网络，设计并实现了一种通过计算各边的介数指标值找到核心节点，然后移除指标值大的节点边从而发现软件系统代码集群的算法，达到分解大型软件系统的目的，将复杂问题简单化。
 本论文详细阐述了算法的设计与实现过程，简述了设计本算法所依赖的理论基础，包括复杂网络、复杂网络中心化、集群分析、软件系统等；着重介绍了在实现过程中，计算最短路径使用的弗洛伊德算法，判断回路的深度优先遍历算法，C#图形编程等。

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