《基于复杂网络的大型软件复杂性度量》-工学论文，软件工程论文-论文范文参考-科学狗论文网

标题

基于复杂网络的大型软件复杂性度量

范文

王伟

摘要：软件系统的复杂性不断增长，这与软件的开发成本、质量以及效率等息息相关，传统的复杂性度量已经不能满足需要。因此，度量一个大型软件系统的复杂性有助于保证软件质量和优化软件结构。复杂网络理论的研究为软件复杂性度量提供了理论依据和新的方向。从大型软件系统的结构出发通过数学建模可以发现其具有复杂网络特性，进而提出了一个新的方法对大型软件系统的结构复杂性进行度量。

关键词：软件复杂性；复杂网络；复杂性度量；大型软件系统

中图分类号：TP391.41

文献标识码：A

DOI：10.3969/j.issn.1003-6970.2015.11.023

0 引言

质量是工程技术领域中不可缺少的一个重要因素，随着软件工程的发展，软件质量受到越来越广泛的关注，度量技术在软件工程领域的作用越来越重要，因为“任何不可度量的都是不可控的”。软件设计开发的过程中软件度量是其科学性的重要保证，缺乏合理的度量往往会使得软件开发处于失控状态。软件度量的基础性工作早就已经进行，之后McCabe和Halstead提出了结构化程序度量方法McCabe环复杂度，它首次考虑了软件内部的拓扑结构特性。

面向对象设计已经成为软件设计和开发中应用的主要方法，但是之前提出的度量方法不能满足面向对象软件的特性。因此，学者们开始研究面向对象的软件度量方法，Brit和Abreu提出了MOOD方法，Chidamber和Kemerer提出了C&K方法。它们主要的关注点在于类，衡量类与类之间以及类的内部关系的复杂性。随着软件规模的不断增大软件系统的复杂程度也越来越高，软件质量保证变得尤其重要，而软件复杂性的度量关系到软件的可靠性、可维护性等质量因素。以上的方法对于大型软件而言有如下问题：只注重统计关系，不能反映类之间的相互作用；仅注重统计与对象类有关的数量和规模，没有关注粗粒度的模块构件等方面的度量；缺乏全局的复杂性度量。

近年来复杂网络理论的提出使得大型软件系统的度量有了全新的研究角度。研究表明，Internet、生态网络、社交网络等都具有明显的复杂网络特性，通过将这些真实的网络用复杂网络建模进行研究可以发现它们的形成和演化的规律。这对于生物学、物理学、社会学等的发展具有积极的影响。不仅如此，软件系统中存在大量的类、对象、构件等，对这些元素进行建模可以发现明显的复杂网络现象。因此，将复杂网络的性质、规律等用于软件系统结构特性的研究中可以让我们对软件系统有更加充分的理解并能够更好的对软件系统进行控制。

本文首先分析了大型软件系统的结构，发现其具有明显的复杂网络特性，然后介绍复杂网络的基本理论和大型软件系统的网络性质，利用复杂网络理论进行软件复杂性度量并对实例进行了分析。

1 复杂网络与软件网络特性

1.1 复杂网络

随着计算机的数据处理能力和计算能力的快速发展，大量的、真实系统的网络模型都被证明具有明显的统计特征，由于这些网络是从真实复杂系统的拓扑结构抽象得到，所以被称为复杂网络（Complex net-works）。Barabasi和Watts等通过对现实世界中的大量真实网络进行研究证明了它们都具有小世界（SW，Small-World）效应和无标度特性（SF，Scale-Free）。小世界特性表明了复杂网络中的大部分连结集中在少数节点之上，无标度特性是指网络的度分布服从幂级分布。

1.2 软件系统的复杂网络特性

复杂网络理论的深入研究，带动了其在软件领域的应用研究。大型复杂软件通常由多人协同开发，在开发过程中复杂的功能会被分解为若干可重用的单元，因此大型软件系统中存在大量不同粒度的单元，如方法、类、包、接口、编译单元等。这些元素之间的关系是多样的，如类的继承、方法的调用，以这些单元为节点，它们之间的关系为边，就可以构成一个复杂网络，对这种软件复杂网络研究表明，大型软件系统的拓扑结构具有明显的复杂网络特性。

Potanin等对几个大型面向对象的软件系统的研究，它们的网络都具有明显的复杂网络特征。Valverde等研究了软件的拓扑结构，发现它们都呈现出明显的复杂网络特征。Myers研究了软件系统中模块之间的协作和调用关系的网络模型，证明了软件网络的无标度特性。Wheeldon等以大型软件系统的不同属性和关系构造多个网络，证明了这些软件网络都具有无标度特性。Tamai等通过统计学方法证明了大型软件中类的方法数和方法的代码行数所具有的无标度特性。

因此随着软件系统的发展，软件与网络之间的关系越来越密切。从复杂网络的角度，它为我们重新认识软件和软件工程提供了坚实的数学理论基础。

2 软件复杂性度量

2.1 大型软件系统的网络化建模

目前，进行软件系统的复杂网络研究时实现软件系统网络化的方法主要是逆向工程方法，即从代码中获得类图，在进一步得到网络图。从而，我们可以分析大型复杂软件系统的组织结构，发现其整体的复杂网络特性，而不是一些独立的组件堆积出的软件所具有的性质。

因此我们定义一个复杂网络G=（V，E），其中V为节点的集合，E为边的集合，E中的边代表元素之间的关系。

2.2 复杂性的度量

大量研究已经证明，复杂软件系统的拓扑结构具有小世界特性和无标度特性。目前，大型复杂软件系统的发展主要是以组件软件技术为基础，架构主要是面向服务的，每个组件的编程方法用面向对象进行设计。因此，现在的软件系统与客观的世界更相似，具有更加明显的无标度特性，而软件中组件的复用则使得其小世界特性更加显著。软件中组件的自主性和异质性使得它们成为不同的层次。这些组件以服务的方式相互作用，因此，组件之间的耦合较为松散。综上所述，大型复杂软件系统的拓扑结构具有明显的复杂网络特性。

在大型软件系统的复杂性度量中，将软件的类、对象、方法等定义为节点，它们之间的关系定义为边。软件复杂性度量中基于复杂网络理论得出的参数有以下几种。

平均距离D（Average distance）。网络中节点i到节点j至少要经过的边的数目为两点间的最短距离，用dmin（i，j）表示。在无向网络中，网络的平均距离定义如下：

根据网络的定义可知，V为网络中所有节点的集合，而N则为网络中所拥有的节点总数。

聚集系数C（Clustering coefhcient）。某节点i的集聚系数为：

Ci=2Ei/[ki（ki-1）]

其中ki表示节点i的邻边个数，这些邻边之间有Ei条连边。它度量的是节点的聚集程度。

整个网络的聚集系数是每个节点聚集系数的平均值：

度和度分布（Degree&Degree-distribution）。节点的度用来描述该节点在网络中的重要程度，用网络中与其相连的边的个数表示。在有向网络中，节点的度分为人度和出度，入度为指向该节点的边的个数，出度为从该节点指出的边的个数。在无向网络中，不区分入度和出度。P（k）表示网络中度数为k的节点在网络中所占的比例。在复杂网络中它服从幂级分布P（k）=k-r，即具有无标度特性。

模块性T（Community modularity）。社区模块性的定义需要基于以下两个前提：（1）社区间的结点之间应尽可能少的相连；（2）社区内的结点之间应尽可能多的相连。模块性的定义如下：

其中，L为图G中的总边数。It社区Qt内各节点之间的总边数，kt为社区Qt内所有节点的总度数。T值越大表明越多的边在属于选定的社区，社区的模块性越为明显。软件系统的构件、包等就是由许多类构成的一个聚合性高且耦合性低的类集合。因此，对于特定的构件或包，T值越大，则该划分的模块性越好。

介数B（Betweenness centrality））。介数的定义分为节点的介数和边的介数。网络中任意连通的两个节点之间都至少存在着一条最短路径。因此对于节点而言，其介数可用整个网络中最短路径总数与通过该节点的最短路径的条数之比来表示，通过某节点的最短路径数量越多则该节点越重要。因此结点的介数定义如下：

相关性R（Correlation）。度和聚集系数之间的相关性描述了不同网络结构的差异，它包括以下两个方面：度数不同的节点之间的相关性、节点的聚集系数与度之间的相关性。

3 实验验证

3.1 建模

实验选择一个开源的大型软件系统进行研究，把它的类作为一个单元，并将软件系统分解成类单元的不同集合。通过这些类单元之间的交互，软件系统的所有功能都可以实现。用这些类单元作为节点，它们之间的相互作用作为边，则软件的系统结构和其中复杂的连接关系可以用如下的网络图进行表示：

3.2 仿真结果和复杂性分析

利用本文提出的复杂性度量方法可以得到表2所示的统计计算结果。从表中可以看出，这个网络的平均最短距离是3.6012，它反映了网络中信息传播的便利程度。网络聚集系数是0.1012，这一参数值相对较高，说明网络中不同实体间的信息交换较为顺畅。这只是基本的统计结果，需要进一步进行分析才能获得软件系统的复杂性。

通过在双对数坐标下对网络中节点的度进行分析可以发现其度分布为P（k）～k-r。这一现象表示这一软件网络符合幂级分布，即网络具有无标度特性。这一特性表明软件中存在一些中心节点与其他大多数节点相连，这些节点在网络中具有重要的作用，可以影响其他度数相对小的节点。而且，软件网络中如果新增节点也会优先与中心节点相连.

4 结论

本文中应用复杂网络的理论从全局角度分析了大型软件系统的统计特性。并对其进行了深入的研究，结果表明这一软件网络中的平均最短距离、聚集系数等都比随机网络要高，并且网络的度呈幂级分布。进而可以得出结论：该软件系统网络的小世界特性和无标度特性较为明显。

然而，将复杂网络理论用于软件度量的研究工作尚为完善，沿着这一思路进行深入的研究，会让我们更加了解软件系统复杂网络特性，对软件度量以及软件工程也具有重要的意义。

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。