（系统分析与集成专业论文）基于复杂网络的软件模型测度研究.pdf

南京信息工程大学硕士学位论文基于复杂网络的软件模型测度研究 摘要 复杂网络理论研究在近几年得到了逐步发展，它能从整体上对网络结构特性进行分析， 研究系统结构与功能、性能之间的关系。目前复杂网络研究范围已扩展至现实生活的各个领 域。软件作为一种人工智能系统，由于信息技术的发展和外界环境的快速变化，使得复杂度 剧增，软件开发经常处于失控状态。已有研究人员将一些面向对象软件进行抽象分析后发现， 软件网络呈现出复杂网络的无标度特性。本文从复杂网络的角度对软件网络结构特性进行检 测分析，以简化软件复杂性，提高软件开发效率和质量。 本文首先阐述了复杂网络基础理论知识，着重介绍复杂网络的几个静态特征参数和常用 四个经典模型的构成机理，并对比分析了它们的特征参数。随后简要介绍了c k 度量方法和 m o o d 度量方法两种经典的面向对象软件度量方法，分析比较了二者的度量指标，并揭示 了它们的局限性。 接着，从复杂网络角度，对面向对象软件结构进行分析。先简述软件体系结构特性和将 软件抽象为网络模型的具体方法。并根据软件元素粒度的不同大小，建立层次度量模型，介 绍了不同层次间各组成元素之间的关系。重点分析在软件类级网络中，节点在入度和出度方 向上的度分布特性，并解释二者在实际软件中所代表的含义。适时提出了依赖度参数和累积 缺陷性指标，详述二者的产生机理和检测方法。 最后，通过对实例彩扩机软件抽象分析，并与t o m c a t 、j d k 软件模型的统计结果进 行逐步对比后得出：累积缺陷性指标在查找软件结构中存在缺陷的节点及适度判断网络结构 的合理性是有效的。有助于指导软件的设计开发，提高软件开发效率和降低开发成本。 关键字：复杂网络；软件网络：无标度；依赖度；累积缺陷性 南京信息工程大学硕士学位论文 基于复杂网络的软件模型测度研究 a b s t r a c t t h e o r e t i c a ls t u d yo fc o m p l e xn e t w o r k sh a sb e e ng r a d u a l l yd e v e l o p e di nr e c e n ty e a r s ，i tc a l l a n a l y s i st h es t r u c t u r a lc h a r a c t e r i s t i c so ft h en e t w o r ko nt h ew h o l ea n ds t u d yt h er e l a t i o n s h i p s b e t w e e ns 缸1 l c t u r ea n df u n c t i o n p e r f o r m a n c ei ns y s t e m t h es c o p eo ft h es t u d yi nc o m p l e x n e t w o r k sh a sb e e ne x t e n d e dt oa l la r e a si nl i f e a sak i n do fa r t i f i c i a li n t e l l i g e n c es y s t e m ，t h e c o m p l e x i t yo fs o f t w a r eh a sd r a m a t i c a l l yi n c r e a s e da n di t sd e v e l o p m e n to f t e ni so u to fc o n t r o l ， b e c a u s eo ft h ei n f o r m a t i o nt e c h n o l o g ya n dt h ee x t e r n a le n v i r o n m e n tr a p i d l yc h a n g i n g a f t e r 代络e a r c h e ra n a l y s i san u m b e ro fa b s t r a c to b j e c t - o r i e n t e ds o f t w a r e ，t h e yf o u n dt h em o d e l ss h o w i n g t h ec h a r a c t e r i s t i co fs c a l e - f r e e f r o mt h ep e r s p e c t i v eo fc o m p l e xn e t w o r k , t h i sp a p e ra n a l y z e s s t r u c t u r a lc h a r a c t e r i s t i c so ft h es o f t w a r en e t w o r k , s i m p l i f ys o f t w a r ec o m p l e x i t ya n di m p r o v et h e e f f i c i e n c ya n dq u a l i t yo f s o f t w a r ed e v e l o p m e n t f i r s t l y , i td e s c r i b e st h eb a s i ct h e o r yo fc o m p l e xn e t w o r k s ，f o c u s i n go ns e v e r a lp a r a m e t e r so f s t a t i cc h a r a c t e r i s t i c sa n dt h ef o u rc l a s s i c a lm o d e lo ft h em e c h a n i s m ，a n dc o m p a r e st h e i rs t a t i s t i c a l c h a r a c t e r i s t i c s t h e n ，i n t r o d u c et w oc l a s s i cm e t h o d sw h i c hi n c l u d et h em e a s u r eo ft h ec k a n d m o o dm e t r i c si no b j e c t - o r i e n t e ds o f t w a r e ，t h e na n a l y z et h e ma n dr e v e a lt h e i rl i m i t a t i o n s s e c o n d l y , t h i sp a p e rm a i n l ys t u d i e st h es o r w a r ca r c h i t e c t u r ef r o mt h ep e r s p e c t i v eo fc o m p l e x n e t w o r k a n dd e s c r i b et h ec h a r a c t e r i s t i co ft h es o f t w a r es t r u c t u r ea sw e l la si n l r o d u c et h ew a yt o m a k es o f t w a r ei n t oa b s t r a c tn e t w o r k a c c o r d i n gt ot h ed i f f e r e n ts i z eo fs o f t w a r ee l e m e n t s ， e s t a b l i s ht h el e v e lm e a s u r e m e n tm o d e l ，a n dd e s c r i b e st h ei n t e r - r e l a t i o n s h i p so fc o n s t i t u e n t e l e m e n t sb e t w e e nd i f f e r e n tl e v e l s i tf o c u s e so na n a l y z i n gt h en o d ei n - d e g r e ea n do u t - d e g r e ei nt h e d i r e c t i o no fi t sd i s t r i b u t i o na n dr e v e a l si t sr e a lm e a n i n gi ns o , w a r ed e v e l o p m e n t b a s e do nt h e a b o v e ，r a i s et h ed e p e n d e n c ed e g r e ep a r a m e t e r sa n dc u m u l a t i v ed e f e c t si n d e x ，d e t a i l i n gt h e i n f o r m a t i o no f b o t ht h em e c h a n i s ma n dd e t e c t i o nm e t h o d f i n a l l y , a f t e ra n a l y z et h ee n l a r g e rs o f t w a r ea n dc o m p a r ew i t ht h es t a t i s t i c a l r e s u l t so f t o m c a ta n dj d ki tp r o v e st h a tt h ei n d e xo fc u m u l a t i v ed e f e c t si sa v a i l a b l ew h e ns e a r c h i n gt h e d e f e c t i v en o d e sa n dj u d g e st h er a t i o n a l i t yo ft h es t r u c t u r e i ti sh e l p f u li ns o f t w a r ed e v e l o p m e n t a n di m p r o v i n gi t se f f i c i e n c ya sw e l la sr e d u c e st h ec o s t k e yw o r d s ：c o m p l e xn e t w o r k s ；s o f t w a r en e t w o r k ；s c a l e f l e e ；d e p e i l d e n c yd e g r e e ； c u m u l a t i v ed e f e c t s 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。本论文除了文中特别加以标注和致谢的内容外，不包含其他人或其他机 构已经发表或撰写过的研究成果，也不包含为获得南京信息工程大学或其他教育 机构的学位或证书而使用过的材料。其他同志对本研究所做的贡献均已在论文中 作了声明并表示谢意。 学位论文作者签名：杜签字吼五纽哔 关于论文使用授权的说明 南京信息工程大学、国家图书馆、中国学术期刊( 光盘版) 杂志社、中国科 学技术信息研究所的中国学位论文全文数据库有权保留本人所送交学位论文 的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文，并通过网 络向社会提供信息服务。本人电子文档的内容和纸质论文的内容相一致。除在保 密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全 部或部分内容。论文的公布( 包括刊登) 授权南京信息工程大学研究生部办理。 口公开口保密(年月) ( 保密的学位论文在解密后应遵守此协议) 学位论文作者签名： 狂蚴 指导教师签名：当芝酷 签字日期： 签字日期： 南京信息工程大学硕士学位论文 基于复杂网络的软件模型测度研究 1 1 复杂网络研究背景 1 1 i 复杂网络研究历程 第一章前言 近几年，随着复杂网络研究热潮的兴起，人们开始广泛关注网络结构与行为之间的关系。 有关复杂网络研究最早起源于1 8 世纪瑞士伟大的数学家e u l e r 对著名的“k o n i g s b e r g 七桥 问题”的探索研究。他利用数学抽象方法，把“七桥问题”抽象为一个由四个点和七条边构 成的图，并通过数学理论思维验证分析后，给出了自己的论证思想，由此开启了图论的研究。 随后一直到2 0 世纪6 0 年代，由匈牙利的两位数学家e r d o s 和r 6 n y i 提出的随机图理论开创 了数学史上复杂网络理论研究的新篇章【1 1 并在随后的4 0 年中，随机图理论一直是进行各 种复杂网络研究的理论基础，但此时绝大多数研究对象的网络结构并不是完全随机的。与此 同时，人们也对一些现实网络进行了相关的实验研究，并试图揭示其特性，这些工作为后来 “小世界”和“无标度”理论的建立奠定了基础。早在2 0 世纪6 0 年代，美国哈佛大学社会 心理学家m i l 鲜锄就通过随机发送连锁信件的社会调查给出了这样一个推断：地球上任意两 个人之间的平均距离是6 ，也就是平均中间只要通过5 个人，一个人就能与地球上任何一个 角落的任何一个人联系上，这就是著名的“六度分离”推断【2 】。实际上它是对“小世界”特 性的最初研究。在这之后，为了检验该推断的正确性，人们又做了一些其他有关“小世界” 特性的实验。其中较为著名的有：“l 沁血b a c o n 游戏”、“e r d o s 数”和“w a t t s 的小世界 网站实验”等，实验的最终结果都证明了网络中“小世界”特性的存在，而且实验所求得的 平均距离都很小。 在2 0 世纪末期，人们对复杂网络理论的研究范畴不再仅局限于数学领域，开始研究一 些节点数量众多，结构连接复杂的现实网络的整体结构特性，由此掀起了从物理学到生物学 等在众多学科领域中共同研究复杂网络的热潮。其中，由w a t t s 和s t r o g a t z 发表的题为 c o l l e c t i v ed y n a m i c so fs m a l l - w o r l dn e t w o r k s ) 【3 】以及由b a r a b h s i 和a l b e r t 发表的题为 e m e r g e n c eo fs c a l i n gi nr a n d o mn e t w o r k s ) ) 【4 】的两篇文章可以看作是复杂网络研究新纪元 开始的标志。它们分别揭示了复杂网络中的“小世界”特征和“无标度”特性，并分别建立 模型介绍这些特性实际产生的机理。 到目前为止，人们对许多现实网络结构特性的研究，包括对交通网络、软件网络等的研 究都是基于“小世界”特征和“无标度”性质的基础上进行的。除此之外，众多研究者还通 l 南京信息工程大学硕士学位论文 基于复杂网络的软件模型测度研究 过对现实网络抽象模型的扩展来研究复杂网络的动力学特性。 1 1 2 复杂网络研究意义 复杂网络的“小世界”特性和“无标度”性质，为其应用领域展现了广阔的应用前景。 目前，复杂网络的研究领域已涉及社会、医学、经济、生物等多个不同层面。研究者们发现， 现实中的很多网络，包括因特网、社会关系网、生物的新陈代谢网等都是属于“无标度”网 络。这些网络中绝大多数的节点只有少量的连接，仅有极少数的节点却承载着网络的大量连 接，维系着网络整体的稳定性。通过进一步研究发现，这类网络在面对随机攻击时具有异常 的承受强度，但在蓄意攻击面前却显得脆弱不堪。根据复杂网络的这一特性，可以解决现实 生活中很多棘手问题。 首先，复杂网络理论研究可用于保证许多复杂系统的稳定运行。在日常生活中，诸如万 维网、电力网、交通网等现实网络，在人们日常生活的影响指数中所占据的地位越来越高。 如何保证这些网络的稳定性，或提高它们的可靠性引起了人们广泛的关注。结合复杂网络对 这些网络的拓扑结构进行研究，对于维护现实网络布局稳定性具有重要意义。例如a l b e r t ， j e o n g 和b a r a b 矗s i t 5 】对万维网子网的网络分布特征进行分析后发现：网络中8 0 以上节点的 页面链接数量不到4 个，但占节点总数不到万分之一的极少数节点，却有1 0 0 0 个以上的链 接，甚至更多。显然，这些集散节点掌控着网络整体的稳定性。陈洁等介绍了中国电力网的 共性，以及基于这些共性的中国电力网发展历程的动力学模型【6 】。 复杂网络理论也可应用于社会、医学等领域。近几年，传染病在社会上肆虐，对人类生 命安全和社会稳定构成了极大的威胁。一方面，人们可以借助复杂网络理论从整体上对传染 病受感染人群的抽象网络模型进行研究分析，将处于集散节点的人群进行集中治理，防止传 染源进一步扩散。另一方面，利用复杂网络的动力学特征，研究传染病抽象网络模型的动态 扩展特性，为决策人员控制病毒蔓延、维护公共卫生安全等提供有效保证。例如黄淑琼等利 用网络模型和常用软件分析传染病传播过程，深入理解网络拓扑结构对疾病传播的重要影 响，从而找到控制疾病传播更有效的方法阴。余雷等从复杂网络理论出发，通过建立复杂网 络模型的方法模拟了传染病传播过程，对s a r s 的传播过程成功进行了模拟，并给出了一些 控制这类问题的建议【8 l 。 此外，复杂网络在社会经济领域也有其广阔的应用前景。它有助于人们了解企业内部产 业与经济之间的连接方式。利用复杂网络可以分析企业内部之间的信息传播、交换以及战略 同盟等信息。通过对不同企业的经济关系进行抽象分析，有助于了解区域整体经济结构发展 模式。例如常慧等通过建立动态的地区间经济贸易网络，从地区间经济贸易角度对我国贫富 2 南京信息工程大学硕士学位论文基于复杂网络的软件模型测度研究 差距成因进行分析【9 】。此外，还有买者与卖者网络、技术创新网络等模型试图从微观经济原 理上来解释经济网络形成的原因，同时还引入了经济网络稳定性和有效性的概念【l 们。 复杂网络作为对现实系统的一种整体抽象和结构描述，突出强调了系统的拓扑结构特 征，同时它为系统科学的研究提供了新的视角。现实世界中几乎任何一种系统都可以抽象为 复杂网络。通过对其整体结构进行抽象研究，一方面可以加深人们对系统全局性的了解；另 一方面可以简化系统的复杂性，为研究结构特性提供一种新的思路。随着研究工作的继续深 入，有关复杂网络理论研究势必会出现新的成果。 1 2 软件网络研究意义 伴随着计算机应用范围的不断推广和深入，软件在人类社会中所承担的作用越来越重 要。同时由于软件应用范围在广度和深度上的不断拓展，包括它与网络的结合，使得系统规 模增大，系统元素之间的交互等也呈数量级增长，软件成为了一类复杂系统。由此引起软件 开发的难度增加，同时导致软件开发和维护的费用也居高不下，软件开发经常超出人类的理 解和控制。此时，以往的软件开发技术和软件度量方法显然已不能满足软件发展的需要，“软 件危机”骤然产生。 纵观软件发展历程，“软件危机”问题的产生除了由于外界应用环境的复杂性加剧之外， 其根源主要在于软件本身复杂性的提高。包括软件内部元素交互的复杂性，软件所描述问题 的复杂性，开发人员的认知复杂性以及软件开发过程中人员的交互、调配复杂性等【1 1 1 。这 些不定性因素导致软件开发经常超出人员的控制，软件系统也容易变得不稳定，甚至软件中 一个极小的错误都会引发巨大的灾难【1 2 1 。诸如在航空、军事领域，软件中某个变量的赋值 错误，都有可能会导致巨额经济损失或者引发战争恐慌。因此，解决“软件危机”迫在眉睫， 而其关键就在于解决软件本身的复杂性因素。 类似于其他复杂系统，软件也呈现出了体系结构的复杂性，而且在不同层次上可以展现 出不同粒度的抽象模型。通过众多研究表明：网络模型是描述复杂系统的一种有效方法。同 时，复杂网络的“小世界”【1 3 1 和“无标度”特性 1 4 , 1 5 , 16 】，为复杂网络的研究展现了广阔的前 景，也为我们从全局角度研究系统结构特性提供了一种有力工具。软件系统可以看作是由一 系列元素以及这些元素之间的交互所形成的集合。随着软件系统规模的剧增，软件的“网络 化”趋势愈加明显。此时，如何分析和探索软件网络的结构特性逐渐成为人们关注的焦点。 软件是一种智能型产品，当前软件的设计与开发技术尚不成熟，在开发过程中，开发人 员的经验所占比重仍较大，理论化程度比较低。一直以来，由于缺乏相应的方法，开发者很 难从整体上对软件结构和演化规律有一个清晰的认识f 1 7 】，使得软件的动态演化机制和产品质 3 南京信息工程大学硕士学位论文基于复杂网络的软件模型测度研究 量都受到了影响 1 8 , 1 9 2 0 】。随着软件的网络化趋势愈加明显，将促使软件工程从传统的经验型 设计模式向计算型模式方向发展，以满足软件系统日益复杂的设计和开发要求。所谓计算型 软件开发模式，就是通过量化分析，弄清楚软件结构与功能、性能等方面的关系，从而将软 件开发发展成为一个严谨的数学计算过程，并根据计算所得的量化依据简化软件结构复杂 性，最终提高软件可靠性和生产率，降低开发成本。与此同时，复杂网络理论及相关特性的 提出，为软件工程研究人员提供了一个从量化的角度研究软件工程的工具。其次，软件网络 中一些复杂特性的发现，也为结合复杂网络研究软件工程，解决软件的复杂性创造了条件。 此时，如何运用复杂网络理论成果，开发高质量软件已成为当前迫切需要解决的问题。 复杂网络虽然无法描述软件开发过程中的所有现象，但它可以从整体上对软件结构特性 进行分析研究。而且复杂网络理论具有良好的数学理论基础，对发展“计算型”的软件工程 具有积极意义。 1 3 软件网络研究进展 1 3 1 软件网络研究现状 复杂网络理论不仅关注系统局部的网络特征，同时它强调从整体上把握系统的结构特 性。由于现在的软件系统日益复杂，因此，结合复杂网络理论从整体上对软件结构进行分析， 为我们理解软件系统的复杂性【2 1 】提供了一个全新的视角和新的思维模式。同时，它能对软件 系统不同粒度层次的抽象模型进行分析，弥补了传统软件度量方法的缺陷。于是一些复杂网 络的研究方法便被引入到了软件度量学中。从复杂网络的角度对软件网络进行研究主要有两 个方向：其一是对软件拓扑结构特性进行分析研究，研究软件的可靠性等；其二是基于软件 的动态扩展特性，研究软件网络的动力学特性。 目前，利用复杂系统理论对软件网络进行研究主要集中在以下几方面：1 、g i r o l a m o 等 人针对面向对象软件根据介数等特征参数定义了一套度量指标，以在不同层次检测软件结构 设计的缺陷，对软件质量进行评价【2 4 】。2 、v a s a 等人根据软件网络中节点和边的关系，研究 软件结构的变化，以此预测软件设计的规模和系统开发所需的代价 2 2 】。他们又提出一套度 量方法用于在软件设计过程中检测软件结构的稳定性，并且发现软件中类的结构复杂性在长 时间内变化不大，但那些出度比较大的类被修改的频率比较高 2 3 1 。3 、l a b e l l e n 2 5 1 、m y e r s 2 6 1 、 h y i 锄d w 6 0 d 鲫、m o 啪【2 引、m e l t o n 2 9 1 等人从多个方面对软件的拓扑结构特性进行了分析、 验证和研究。最后的仿真结果都验证了他们所研究的软件系统都具有“无标度”的复杂网络 特性。而且他们还发现：在软件网络中，入度大的节点，对应在软件中该类的重用度大；出 4 南京信息工程大学硕士学位论文基于复杂网络的软件模型测度研究 度大的节点，在软件设计过程中复杂度较大1 6 4 。同时对一款经过长期验证，正常使用的软件， 研究分析后发现：在该软件网络模型中，一个节点的入度和出度数遵循一定的比例分配关系。 即入度大的节点，出度小，反之亦然。4 、在国内，李兵等人【3 0 】对软件系统的复杂性进行分 析，提出相应的度量指标和一种生长的软件网络演化模型，并将演化算法引入到软件复杂性 度量中。何克清、马于涛 3 1 。3 4 1 等人则更进一步对软件网络拓扑结构进行分析，研究系统结构 与系统稳定性、性能等之间的关系。诸如结构复杂性的简化、结构熵的有序性度量、基于 m o t i f 的结构稳定性度量等一系列度量方法体系。同时，他们也对面向对象软件网络的动态 演化模型进行了分析。 总体来说，从复杂网络角度研究软件工程才刚起步，目前虽已取得一些成果，但大部分 都是基于对软件网络进行理论研究的层面上，而且主要集中于研究软件间的共性机制，与实 际的应用环境仍有一段不小的差距。此外，当前提出的一些软件度量指标，缺乏相关有力工 具的支持，其实用性也缺乏大量实例的考证，还不能在实际的软件开发工作中发挥作用。这 些都是以后的软件研究工作需要解决的问题。 1 3 2 软件网络研究存在的问题 软件工程经过多年的发展，人们已经清晰地认识到软件结构在软件质量中所扮演的重要 角色。总结国内外相关研究结果得出：目前结合复杂网络理论研究软件系统主要集中在软件 的复杂性度量和软件的动态演化生长模型两个方面。虽已取得一定的研究成果，但在总体上， 对软件结构度量方面仍缺乏体系化的研究，且考虑不够完善。现将软件网络研究存在的一些 问题罗列如下： ( 1 ) 缺乏软件结构与质量对应关系的系统研究 目前主要利用复杂网络理论对软件的静态结构进行度量分析，但是软件是动态运行的， 与其对应的结构特性也处在不断地动态变化过程中，当前度量方法缺乏对软件动态结构特性 的系统研究。由此求得的结构度量值，很难直接对软件的质量进行评价。此外，软件结构度 量的稳定性参数与软件质量好坏之间没有一个严格的对应标准，使开发人员很难搞清楚当前 软件结构值对应的软件质量如何。 ( 2 ) 缺乏对软件结构优化的研究 当前复杂网络与软件工程的交叉研究，一般将对软件局部结构的度量值作为软件整体结 构度量值。方面缺乏整体上的结构度量求值，缺失准确性；另一方面未能对各局部结构间 的联系进行分析，缺少度量全面性。特别对于规模大的软件，软件内部元素交互甚为复杂， 这种过于简单化度量软件结构的研究方法已经逐步表现出了它的局限性。 5 南京信息工程大学硕士学位论文基于复杂网络的软件模型测度研究 ( 3 ) 缺乏将研究成果实用化的方法 由于复杂网络与软件工程交叉研究才刚起步，而且研究人员多为非软件开发人员，他们 的视觉只能看到软件系统的一些结构特征和表面规律。而且，目前对软件网络研究所得的成 果也都仅停留在理论解释的层面上，缺乏有力工具的支持。因此，对于软件开发人员来说， 想要借助软件网络的最新研究成果，在开发具有高复杂性的软件时进行指导，目前仍然难以 实现。 1 4 论文的研究内容和组织结构 1 4 1 研究内容 本文主要从复杂网络理论的角度对软件网络的结构特性进行研究，重点分析面向对象软 件类级网络的结构特性，提出了依赖度参数和累积缺陷性指标用以检测软件结构中缺陷率比 较高的节点，最后通过实例比较分析，验证了累积缺陷性性能指标的有效性。主要内容如下： ( 1 ) 系统阐述了复杂网络及图论的基础理论知识，着重分析了复杂网络常用的静态特 征参数，并分别介绍了常见的四种典型复杂网络模型的基本原理和统计特征。 ( 2 ) 简要介绍了m o o d 度量方法和c k 度量方法的原理及度量指标，叙述了软件结构 的特征和网络化模型的抽象方法，并适当阐述了不同粒度层次软件网络的度量模型。着重分 析软件网络中节点在入度和出度方向上的不同行为特性，并以此提出节点依赖度参数和累积 缺陷性指标，详述二者的构造机理。 ( 3 ) 将实例软件抽象为网络模型，并对其结构特性进行仿真分析。重点介绍通过实例 软件网络的统计结果在节点依赖度参数和累积缺陷性指标上进行比较分析，验证了该性能指 标在检测软件结构缺陷的有效性，并阐述了它的现实意义。 1 4 2 组织结构 本文共分六章对研究内容进行阐述，其中： 第一章主要介绍论文的研究背景、研究进展及研究意义，并提出本文的研究内容、组织 结构及创新点描述。 第二章着重介绍复杂网络的基本概念。首先介绍复杂网络的基本概念和理论知识及相关 图论的基础，重点阐述复杂网络的几个统计特征参数，最后介绍了四种经典网络模型的演化 机理和统计特征。 6 南京信息工程大学硕士学位论文基于复杂网络的软件模型测度研究 第三章简要介绍了m o o d 度量方法和c k 度量方法的运行机理和度量指标，并对比分 析了二者的优缺点。 第四章主要介绍软件结构的特征及网络化模型的抽象方法。适当阐述了对应元素粒度不 同大小软件网络的层次度量模型。着重分析软件网络中节点在入度和出度方向上的不同分布 特性，适时提出依赖度参数和累积缺陷性度量指标，着重分析了它们的形成原理和检测方法。 第五章在完成对软件网络中依赖度参数和累积缺陷性指标分析之后，将实例彩扩机软件 抽象为网络模型，并对软件网络节点的度分布特性进行仿真输出。然后从依赖度参数和累积 缺陷性指标两个方面，将彩扩机软件的统计结果与t o m c a t 、j d k 软件的统计结果进行对 比分析，验证了累积缺陷性指标的有效性，也说明了它的现实意义。 第六章对本文所做的研究工作进行概括总结，并对软件网络的进一步研究工作进行展 望。 1 5 论文的创新点 本文的主要创新在于一方面在理论上结合当前国内外复杂网络理论研究的最新成果，根 据软件元素粒度不同大小，提出层次度量模型，从整体上为软件度量提供新的视角。另一方 面，综合考虑软件网络的特殊性，分别从入度和出度两个方向对软件网络的节点度分布特性 进行分析研究，提出依赖度参数和累积缺陷性指标，并通过实例对比验证了算法的有效性。 现将创新点总体归纳如下： ( 1 ) 对复杂网络的基本统计特征和经典模型进行深入分析介绍，并适时对软件网络的 抽象模型和静态统计特征进行了仿真。从而加强了对软件网络模型的独特见解。 ( 2 ) 在面向对象软件中，根据软件网络中软件元素粒度的不同大小，提出层次度量模 型，并分析了该模型中不同层次之间组成元素的对应关系。由此可以视情况对不同粒度级的 软件网络结构进行度量分析。 ( 3 ) 根据软件网络中节点在入度和出度方向上所表现出来的不同复杂性，依次建立了 依赖度参数和累积缺陷性指标。依赖度参数一方面考虑了节点在出度方向上依赖其它节点构 造其功能的复杂性；另一方面可以判断由这些节点所构成的依赖关系网络结构的优劣性。累 积缺陷性指标不仅综合考虑了节点在入度和出度两个方向上的构造复杂性，还引进了实际软 件中类本身包含的方法数作为节点的权值，从而在总体上检测软件结构中是否存在有缺陷的 节点。 7 南京信包工程大学硕士学位论文基于复杂网络的软件模型测度研究 第二章复杂网络基本理论概述 2 1 复杂网络理论基础 随着近几年复杂网络( c o m p k xn e t w o r k s ) 的研究兴起，人们开始广泛关注系统结构与系 统功能、性能之间的关系。为研究各类不同复杂网络在结构上的共性，在此统一使用数学中 的 雪( g r a p h ) 来描述。通常任何一种网络( n e t w o r k ) 都可以看作是由顶点( 又称节点) 及项 点与顶点之间的关系边的集合所组成。它是那些具有一定功能和特征的单元，按相互之 间的特定联系所组成的网络系统。其中，在具体网络的抽象图中，顶点( w r t e x ) 表示独立的 功能单元，顶点之间相连的边( l i n k 或e d g e ) 表示功能单元之间的相互作用或联系。由此复杂 网络可以理解为：由大量节点以厦这些节点之间的关系所构成的具有复杂拓扑结构特征的网 络模型。 在当代生活中，复杂网络无处不在，例如互联n ( i n t e m e t l 、人体神经网、社会关系网、 电力网和万维网等。其中，互联网的阿络模型可以看作是将路由器或者网关视为节点它们 之间的互联关系视为边，由此所形成的复杂网络。社会关系网则是将人看作节点，人与人之 间的相识关系作为边所组成的网络模型。其它现实网络的抽象模型皆可通过该方法建立。如 图2 - 1 所示为互联网的复杂网络模型。 方面 蘩 图2 - i 互联网的复杂网络模型 f i g u r e2 - 1c o m p l e xn e t w o n m o d e so f i n t e m e t 通过对复杂网络的大量研究观察，一般而言，复杂网络的共性特征主要体现在以下几个 ( 1 ) 节点非线性的复杂性 南京信息工程大学硕士学位论文基于复杂网络的软件模型测度研究 一个网络中可能存在多个类型不同的节点；而且节点本身具有分岔和混沌等复杂非线性 动力学行为。例如神经网络中的每个节点都具有时间演化行为。 ( 2 ) 网络连接结构的复杂性 复杂网络结构连接复杂，既非完全规则，也非完全随机，而且网络本身具有内在的自组 织规律，其连接结构在一定程度上可能也会随着时间而变化。此外，节点之间的连接可能具 有不同的权重和方向。 ( 3 ) 复杂性因素间相互影响 对于一个具体的复杂网络，它本身易受外界因素的“干扰”而发生变动，例如软件网络 会由于客户需求的变化或者规模的升级而发生变化。此外，由于不同的复杂网络之间还存在 着或多或少的联系，一方的变动都会直接或者间接地引起其他相关联的网络发生连锁变化。 ( 4 ) 网络结构的墓他相关特性 一般复杂网络是由成千上万个，甚至更多的节点连接而成，并能从整体上反映网络的统 计特征。此外，网络模型具有时间和空间上的扩展性。容易随着外界因素的变化而变化。例 如在万维网中，手动增加或者删除数百张网页，包括不同时间段的网页链接数量变化，对于 一个局部的网络模型来说，其整体拓扑结构和连接性质都会发生变化。 以上四种特性描述基本上体现了具体实际网络的复杂性特征。需要指出的是，网络所表 征的不仅仅是抽象图中节点与节点之间的关系，网络本身还承载着一定的功能。复杂网络是 由许多组成元素( c o m p o n e n t ) 构成的，这些基本元素以及它们之间的关系决定了整个系统的 功能和性质。由于早期的网络研究基本是针对规则网和随机网进行的，仅限于复杂系统中的 局部，忽略了对各部分之间关系的研究，而复杂网络的研究则是从全局的角度来衡量整个系 统。到目前为止，大家虽然对复杂网络的认识较为统一，但是科学家们始终尚未给出一个明 确的定义。而从网络研究的历史进程来看，复杂网络定义的产生最初是介于规则网和随机网 之间提出的，故在此将处于规则网和随机网之间的网络统称为复杂网络。 2 2 复杂网络图论基础 在图论中，通常一个 虱( g r a p h ) 就是一个三元组；该三元组包含了一个顶点集v ( g ) ，一 个边集e ( g ) 和一个用于描述两个顶点之间的关系；它将一条边与两个顶点相关联，并把这 两个顶点称为这条边的端点。本文研究所涉及的网络，由于两个顶点之间的关系较为单一， 在此忽略两个顶点之间具体的联系，将图采用二元组g ( v ，e ) 来表示。其中，v ( g ) 为节点 9 南京信息工程大学硕士学位论文基于复杂网络的软件模型测度研究 集，其元素为节点( 也称顶点) ：e ( g ) 为边集，其元素为边。而且，边集合e = ( 巳，吃，e 3 ，乞) 中的每个元素，即每条边都有相应顶点集合y = ( m ，屹，b ，) 中的两个元素，即一对顶点 ( m ，) 与之对应。此外，网络中的节点数目称为网络的阶( o m 哪，用刊vl 表示，边数( s 埘 用m = i e i 表示。同时，用表示边集合e ( g ) 中节点_ 和之间联系的不同值，以此便 可绘制一条加权或者非加权( 通常= 1 ，如果只考虑两节点之间是否存在联系) 的边。 2 2 1 图的分类 已知将具体网络抽象图g ( v ，e ) ，v 为顶点集合，e 为边集合。 ( 1 ) 若顶点集合y 中的节点对( h ，) 和( ，v f ) 所对应的边为边集合e 中的同一条边 ，则该网络为无向图h d i r e c t e dg r a p h ) ；反之，若节点对“，) 和( 0 ，_ ) 分别对应边集 合e 中的不同边，则该网络为有向图( d i r e c t e d g r a p h ) 。在有向图中，根据与节点相连的边的 方向不同，节点的度分为入度( h d e g r e e ) 和出度( o u t - d e g r e e ) 。 ( 2 ) 对于图g ，如果仅需考虑边集合e 中的每条边所对应的节点( 匕，v ，) 之间的联系 是否存在，即只考虑是否为1 ，此时的图称为无权图( o u t w e i g l l t e dg r a p h ) ；反之若需考 虑的不同值，则称为加权图( w e i g h t e dg r a p h ) 。 ( 3 ) 此外，在图g ( v ，f ) 中， 与边相连的节点称为端f f , , ( e n d - v e r t i c e s ) 。同时，两个端 点相同的边则称为环( l o o p ) 。有相同起点和终点的两条边称为重边或者平行边。而一般无环 且无重边的图称为简单 ( s i m p l eg r a p h ) 。任何不同的两顶点之间都有相连的简单无向图称 为完全图( c o m p l e t eg r a p h ) 。 2 2 2 图的表示 对于顶点数和边数不是很多的图可以采用几何图形进行表示，这样直观形象，如图2 - 2 所示为一简单规则图。但当图的顶点数和边数上升到一定数量的时候，很难再采用拓扑结构 1 0 南京信息工程大学硕士学位论文基于复杂网络的软件模型测度研究 的形式进行直观描述，而且顶点之间的关系也容易变得不易分辨。一般在对图g 进行描述 或者运算时，需要采用代数方法进行表示。常用的方法有：邻接矩阵、权矩阵、关联矩阵、 正向表等。其中，邻接矩阵表示节点之间的邻接关系，权矩阵用来表示赋权图，关联矩阵表 示节点和边之间的关联关系，正向表则是对邻接矩阵的行进行压缩的结果。正向表等能表示 重边，也能表示自环，而且占据较小存储空间。邻接矩阵、关联矩阵和正向表之间等都可以 相互转换。但为了直观起见，在复杂网络中，特别在对实际网络进行分析研究时，由于网络 结构复杂，节点数量庞大，通常使用邻接矩阵( m a t r i x ) 方法来表示。例如将软件网络模型使 用邻接矩阵进行描述，这样不仅可以使用代数的方法来解决图论中的复杂问题，而且能够使 网络的高度复杂性展现更加直观，有利于在计算机上进行计算仿真。将图2 2 结构图采用邻 接矩阵表示，如图2 3 所示。 。| 图2 - 2 一个简单的规则图 f i g u r e2 - 2as i m p l er u l eg r a p h 图2 - 3 规则图对应的邻接矩阵图 f i g u r e2 - 3 t h ec o r r e s p o n d e da d j a c e n c ym a t r i xg r a p h 2 3 复杂网络基本特征参数 早期复杂网络的研究，大多从随机网络的节点连通度、结构连通性几个方面来考虑。随 着理论研究的进一步深入，近几年人们在刻画复杂网络结构的统计特性上提出了很多新的概 念和方法，其中几个比较重要的基本参数吲包括：度和度分布( d e g r e ea n dd e g r e e l l 南京信息工程大学硕士学位论文基于复杂网络的软件模型测度研究 d i s t r i b u t i o n ) 、平均路径长度( a v e r a g ep a t hl e n g t h ) 、聚集系数( c l u s t e r i n gc o e f f i c i e n t ) ( 也称集 聚系数或抱团系数) 和介数。以下将对复杂网络的几个基本参数进行相关介绍。 2 3 i 度和度分布 网络中度( d e g r e e ) 的定义是指与某个顶点相连的边的数目。在此，将网络中的节点碍的 度用岛表示，它是单独节点属性中简单而又重要的概念。在无向网络中，理论上一般使用节 点的连通度，即根据节点的度墨的大小来反映该节点在网络中的重要性，同时它也是用于 判断网络结构是否复杂的一个重要指标。在有向网络中，由于既存在从节点m 到节点0 方 向的边，也存在从节点到节点1 c f 方向的边，故对于节点k 和的度就存在着入度 ( i n d e g r e e ) 和出度( o u t - d e g r e e ) 之分。其中，节点的出度大小表示从该节点连接到其他节点的 边的数目，用七删表示。同理，对于节点的入度大小则是表示从其他节点到达该节点的边的 数目，用表示。 此外，将网络中所有节点的度的平均值称为网络的节点平均度，记为( j j ) 。并定义p ( j j ) ( 或雕) ) 为网络中度数为七的节点占节点总数的比例，也可表示在随机情况下从网络 中选出节点的度数恰好为k 的概率；以此表示网络节点度分布的情况。 对于任一给定的网络，p ) 可以使用节点度的直方图来表示，这个直方图就是网络节 点的度分布。对于规则网络，由于其节点度分布最为简单，且各节点都具有相同的度，故它 的度分布是呈现出d e l t a 分布( 即单个尖峰) 的形式。而在e r d o s 和r d n y i 3 5 1 所研究的随机网 络中，由于每条边存在的概率都是相同的。因此，在网络中它的节点度分布服从二项分布或 者在极限情况下的p o i s s o n 分布，其形状在远离峰值( 七) 处呈指数下降。也就是说当节点的 度指数七 七 时，度为七的节点实际上是不存在的，所以类似这类网络也被称为均匀网 络( h o m o g e n e o u sn e t w o r k ) 。但是，在近几年的大量研究表明，现实世界中许多网络的度分 布与随机网络度分布截然不同，大多数网络的顶点度分布都远远偏离p o i s s o n 分布，且明显 向右倾斜，这表明此类网络的度分布的右边尾部要长而且它的值要远大于平均数。通过对节 点度的累积度分布进一步进行分析，发觉很多度分布曲线确实右倾，而且在曲线尾部都服从 1 2 南京信息工程大学硕士学位论文基于复杂网络的软件模型测度研究 幂律分布：即对某些常数幂y ，存在p ( k ) 芘k 。特别对现实中的许多网络，例如万维网、 基因网等网络的度分布都可以使用幂律形式p ( j j )