基于Centrality的Cluster发现算法设计与实现
资料包括： 论文(46页20027字) 任务书 开题报告
说明：
摘 要：现实世界中的许多复杂系统都可以使用网络模型进行描述。复杂网络的结构和性质研究已经成为引人注目的领域。对复杂网络进行中心化，发现复杂网络中的重要节点，具有重要的应用价值。
软件系统其实也是一类非常重要的复杂网络，不过目前为止对这方面的研究非常少见。软件一般由许多相互关联的单元和子系统（如子程序，类，源程序文件，库文件等）以及这些组成元素间的交互和协作关系组成。软件的组成元素可以看成复杂网络中的节点，而他们之间的相互调用或是消息通信关系可以看成复杂网络中的边。目前，软件系统规模日趋庞大，系统间的协作日趋紧密，特别是开源软件的发展更促进这一趋势。将复杂的大型软件系统分解成相对独立的软件集群，具有重要的研究意义。
本课题运用复杂网络中心化（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 课题背景及来源
复杂网络(Complex Networks)是自然界和人类社会中普遍存在的一类复杂系统，现实世界中的复杂网络无处不在。复杂网络的研究以数学中的图论作为理论基础，大量应用统计物理学的方法和工具，对网络的几何性质、形成机制、演化规律、结构稳定性和动力学等多个方面进行了大量的研究，也取得了丰硕的研究成果。近年来，科学家发现复杂网络的不确定性中蕴涵着规律性，可以使用定量的方法进行表示和分析，而且其规律所呈现的形式非常直观，也符合人们对事物认识的常识。复杂网络已经成为不同学科共同关心的热点，科学家预言21世纪的科学将是复杂网络和复杂系统的科学。复杂网络研究的对象多是人类社会和自然界中的自组织进化型网络，即由大量个体经过自发的相互作用最终形成复杂的网络结构，其中没有使用工程设计的方法。实验证明，像软件这类完全由人工设计和实现的系统，也具有复杂网络的特征。虽然复杂网络在社会学、经济学、生态学及统计学中都应用广泛，但是在软件系统方面的研究还非常少见。随着软件系统的发展，其规模日趋扩大，彼此间的协作也更为紧密，特别是开源软件的发展，更推动这一趋势。国内外的研究学者也开始将复杂网络中的某些理论研究应用到大型的软件系统中，将软件系统网络化。
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 发现Cluster28
4.3 结果分析28
4.3.1 开发难点及相关策略28
4.3.2 工作展望及见解29
4.3.3 创新思想29
5. 总结31
致谢32
参考文献33
附录35
参考文献：
韩明畅,李德毅,刘常昱,李华. 软件中的网络化特征及其对软件质量的贡献[J]. 计算机工程与应用，2006,42(20)：29-31，186.
吴彤. 复杂网络研究及其意义[J]. 哲学研究，2004,8：58-63.
Watts，D.J. & Strogatz，S.H.. Collective dynamics of “small—world” networks. Nature，1998，393．
Strogatz S.H.. Exploring complex networks，Nature，2001，410.
Barabasi,A-L & Albeat. Emergence of scaling in random networks. Science，1999，286．
吴金闪,狄增如等. 从统计物理学看复杂网络研究[J]. 物理学进展，2004,24(1)：18-46.
方锦清,汪小帆,刘曾荣等. 略论复杂性问题和非线性复杂网络系统的研究[J]. 科技导报（北京）,2004,2：9-12.
Wasserman S,Faust K. Social Network Analysis: Methods and App lications[M]. New York: Cambridge University Press，1994.
KoschützkiD,Schreiber F. Comparison of centralities for biological networks[A]. Giegerich R,Stoye J,Eds. Proc German ConfBioinformatics(GCB’04)[C]，LNIP-53：2004,199-206.
Kohler E,Mohring R,SkutellaM. Traffic networks and flows over time[R]. TU2Berlin Technical Report, Technical Report，2002.
Crucitti P,Latora V,Porta S. Centralitymeasures in urban networks[J]. Physics，2005, 0504163.
Girvan M, NewmanM E.J.. Community structure in social and biological networks[J]. Proc Natl Acad Sci USA，2002, 99: 7821-7826.
Carpenter T,Karakostas G,Shallcross D. Practical issues and algorithms for analyzing terrorist networks[J/OL]. http://www.cas.mcmaster.ca/~gk/papers/wmc2002.pdf，2002.
Gomez D,Gonzalez Aranguena E,Manuel C. Centrality and power in social network: a game theoretic app roach[J]. Mathematical Social Sciences，2003, 46(1): 27-54.
[15] 王林,张婧婧等. 复杂网络的中心化[J]. 复杂系统与复杂性科学，2006,4(1)：120-128.
[16] DependencyFinder-1.1.1. http://HDepfind.sourceforge.net，2005.
[17] Jung-1.6.0. http://mung.sourcrforge.net，2005.
[18] S.R Albert,A.L Bambasi. Statistical mechanics of complex networks[J]. Review of Modem Physics，2002,74:47-97.
[19] H.Muller, M.Orgun,S.Tilley,J.Uhl. A reverse engineering approach to subsystem structure identification[R]. Journal of Software Maintenance: Research and Practice，1993.
[20] S.Choi,WScacchi. Extracting and restructuring the design of large systems[S]. IEEE Software， 1990.
[21] R.Schwanke. An intelligent tool for reengineering software modularity[R]. International Conference on Software Engineering，1991.
[22] K Sartipi, K Kontogiannis. A graph pattern matching approach to software architecture recovery[R]. International Conference on Software Maintenance，2001.
[23] M.Siff, T.Reps. Identifying modules via concept analysis[R]. Proceedings of the 19th International Conference on Software Maintenance，1997.
[24] 齐晶晶,郭跟成等. 基于图的谱分割技术的面向对象软件系统分解[J]. 计算机应用研究，2007,24(1)：54-57.
[25] 胡华,石世光等. Floyd算法分析与演示系统设计[J]. 电脑学习, 2007,6：63-64.
[26] 徐翠霞等. 基于DFS的图的双向连通性研究[J]. 科技广场，2007,5：55-56.
作者点评：
本课题是基于Centrality的Cluster发现算法的设计与实现。算法针对软件系统这类复杂系统，其设计以复杂网络、复杂网络中心化、集群分析等理论知识为重要参考依据，通过介数指标这种中心化过程发现系统中的重要节点，并借鉴谱图分割技术分解软件系统识别软件集群，达到将复杂系统简单化的目的。
本课题结合复杂网络和集群分析两大理论内容，创造性地应用到软件系统分析中，其中间产物——发现的软件系统核心代码对防止软件系统被破坏或被盗版有重要帮助意义，而且对软件测试保证质量也有很重要的价值。其最后的成果——发现的软件集群对代码的重用、分析软件结构都有很大的研究意义。虽然本课题只是在这方面进行比较简单的探讨应用，但是这种研究对软件工程领域提供新的研究视角。
通过本科毕业设计，我涉足到复杂网络、集群分析等新领域，拓宽了知识面。从某些角度来说，这两个知识内容是基于一个较高的层次，对普遍问题的简单化与抽象，应用范围极其广泛，具有很重要的研究意义。而且，对他们的研究让我在思考和解决问题方面有很大的收获，掌握如何从错综复杂的问题中抽象出共性和特性及如何有条理、合理地分解问题的思考方式。通过本课题，让我初步尝试了如何利用已有的理论结合自己的实际研究情况设计合适的算法方案，并学会了简单的C#图形编程。