基于Centrality的Cluster发现算法设计与实现(含开题+任务书)

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

摘   要

现实世界中的许多复杂系统都可以使用网络模型进行描述。复杂网络的结构和性质研究已经成为引人注目的领域。对复杂网络进行中心化，发现复杂网络中的重要节点，具有重要的应用价值。

软件系统其实也是一类非常重要的复杂网络，不过目前为止对这方面的研究非常少见。软件一般由许多相互关联的单元和子系统（如子程序，类，源程序文件，库文件等）以及这些组成元素间的交互和协作关系组成。软件的组成元素可以看成复杂网络中的节点，而他们之间的相互调用或是消息通信关系可以看成复杂网络中的边。目前，软件系统规模日趋庞大，系统间的协作日趋紧密，特别是开源软件的发展更促进这一趋势。将复杂的大型软件系统分解成相对独立的软件集群，具有重要的研究意义。

本课题运用复杂网络中心化（Centrality）思想和集群（Cluster）分析思想，针对软件系统这类复杂网络，设计并实现了一种通过计算各边的介数指标值找到核心节点，然后移除指标值大的节点边从而发现软件系统代码集群的算法，达到分解大型软件系统的目的，将复杂问题简单化。

本论文详细阐述了算法的设计与实现过程，简述了设计本算法所依赖的理论基础，包括复杂网络、复杂网络中心化、集群分析、软件系统等；着重介绍了在实现过程中，计算最短路径使用的弗洛伊德算法，判断回路的深度优先遍历算法，C#图形编程等。

关键词：复杂网络，中心化，软件系统，集群分析

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