基于Centrality的Cluster发现算法设计实现论文.doc

毕业设计(论文)
设计论文题目：
基于Centrality的Cluster

发现算法的设计与实现

学生姓名：

学生学号：

专业班级：

学院名称：

指导老师：

学院院长：

年 5 月 23 日

毕业设计（论文） 第 41 页
基于Centrality的Cluster发现算法设计与实现

摘 要
现实世界中的许多复杂系统都可以使用网络模型进行描述。复杂网络的结构和性质研究已经成为引人注目的领域。对复杂网络进行中心化，发现复杂网络中的重要节点，具有重要的应用价值。
软件系统其实也是一类非常重要的复杂网络，不过目前为止对这方面的研究非常少见。软件一般由许多相互关联的单元和子系统（如子程序，类，源程序文件，库文件等）以及这些组成元素间的交互和协作关系组成。软件的组成元素可以看成复杂网络中的节点，而他们之间的相互调用或是消息通信关系可以看成复杂网络中的边。目前，软件系统规模日趋庞大，系统间的协作日趋紧密，特别是开源软件的发展更促进这一趋势。将复杂的大型软件系统分解成相对独立的软件集群，具有重要的研究意义。
本课题运用复杂网络中心化（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

1. 绪论
1.1 课题背景及来源
复杂网络(Complex Networks)是自然界和人类社会中普遍存在的一类复杂系统，现实世界中的复杂网络无处不在[1]。复杂网络的研究以数学中的图论作为理论基础，大量应用统计物理学的方法和工具，对网络的几何性质、形成机制、演化规律、结构稳定性和动力学等多个方面进行了大量的研究，也取得了丰硕的研究成果。近年来，科学家发现复杂网络的不确定性中蕴涵着规律性，可以使用定量的方法进行表示和分析，而且其规律所呈现的形式非常直观，也符合人们对事物认识的常识。复杂网络已经成为不同学科共同关心的热点，科学家预言21世纪的科学将是复杂网络和复杂系统的科学。复杂网络研究的对象多是人类社会和自然界中的自组织进化型网络，即由大量个体经过自发的相互作用最终形成复杂的网络结构，其中没有使用工程设计的方法。实验证明，像软件这类完全由人工设计和实现的系统，也具有复杂网络的特征。虽然复杂网络在社会学、经济学、生态学及统计学中都应用广泛，但是在软件系统方面的研究还非常少见。随着软件系统的发展，其规模日趋扩大，彼此间的协作也更为紧密，特别是开源软件的发展，更推动这一趋势。国内外的研究学者也开始将复杂网络中的某些理论研究应用到大型的软件系统中，将软件系统网络化。
本课题是基于Centrality的Cluster发现算法设计与实现，针对软件系统这类复杂网络，通过复杂网络中心化来发现网络中的重要节点并通过移除软件数据流动影响强的节点边达到分解复杂软件系统为较为独立的小型软件集群的目的。研究的内容主要分为两个部分：一是设计合适的算法方案；二是实现并测试算法。
详尽的介绍将在第三、四部分加以说明。
1.2 课题研究的意义
本课题将复杂网络的某些理论应用到软件系统中，将软件系统网络化，发现软件的网络拓扑特征，这在分析软件结构方面非常少见。可以认为，软件系统的开发方法和过程会影响软件网络的拓扑特征，反之，利用软件网络的拓扑特征又可以指导软件系统的设计和开发[1]。而通过复杂网络中心化过程发现软件系统中的重要节点，对分析软件系统的结构理解有很重要的意义。找到软件系统中的重要节点，即找到软件系统中的核心代码，对防止软件被破坏或被盗版也有很重要的价值。另外，运用集群思想，将重要节点构成集群，有利于代码的重用，对系统测试保证系统质量有很大的帮助，同时在软件工程的领域给出了新的研究角度和指导方法。
1.3 论文组织结构
绪论部分概要介绍了本毕业设计课题的背景来源以及研究的意义。
第二部分介绍开发本算法所涉及到的基本理论知识。
第三部分是论文的重点之一，根据第二部分介绍的基本理论知识，着重介绍了算法的设计方案以及选用方法的依据。
第四部分是论文的另一重点所在，从第三部分的算法设计方案出发，以第二部分涉及到的基本知识为基础，重点介绍算法的实现方法，并阐述课题的难点、问题所在以及创新思想在本设计中的体现。
第五部分对研究工作进行归纳和总结。
2. 基本理论知识及其应用
2.1 复杂网络
2.1.1 概念
复杂网络简而言之即呈现高度复杂性的网络[2]。其复杂性主要表现在以下几个方面：1）结构复杂，表现在节点数目巨大，网络结构呈现多种不同特征。2）网络进化：表现在节点或连接的产生与消失。例如World-Wide Network，网页或链接随时可能出现或断开，导致网络结构不断发生变化。3）连接多样性：节点之间的连接权重存在差异，且有可能存在方向性。4）动力学复杂性：节点集可能属于非线性动力学系统，例如节点状态随时间发生复杂变化。5）节点多样性：复杂网络中的节点可以代表任何事物，例如，人际关系构成的复杂网络节点代表单独个体，万维网组成的复杂网络节点可以表示不同网页。6）多重复杂性融合：即以上多重复杂性相互影响，导致更为难以预料的结果。例如，设计一个电力供应网络需要考虑此网络的进化过程，其进化过程决定网络的拓扑结构。当两个节点之间频繁进行能量传输时，他们之间的连接权重会随之增加，通过不断的学习与记忆逐步改善网络性能。
近年来，学界关于复杂网络的研究正方兴未艾。特别是，国际上有两项开创性工作掀起了一股不小的研究复杂网络的热潮。一是1998年Watts和Strogatz在Nature杂志上发表文章，引入了小世界(Small-World)网络模型，以描述从完全规则网络到完全随机网络的转变[3,4]。小世界网络既具有与规则网络类似的聚类特性，又具有与随机网络类似的较小的平均路径长度。二是1999年Barabasi和Albert在Science上发表文章指出，许多实际的复杂网络的连接度分布具有幂律形式[5]。由于幂律分布没有明显的特征长度，该类网络又被称为无标度(Scale-Free)网络。而后科学家们又研究了各种复杂网络的各种特性。国内学界也已经注意到了这种趋势，并且也开始展开研究[6]。加入复杂网络研究的学者主要来自图论、统计物理学、计算机网络研究、生态学、社会学以及经济学等领域，研究所涉及的网络主要有：生命科学领域的各种网络（如细胞网络、蛋白质－蛋白质作用网络、蛋白质折叠网络、神经网络、生态网络）、Internet/WWW网络、社会网络，包括流行性疾病的传播网络、科学家合作网络、人类性关系网络、语言学网络等等；所使用的主要方法是数学上的图论、物理学中的统计物理学方法和社会网络分析方法。
抽象地说，元素及其元素之间的关系作为一个整体就是网络。在数学和自然科学领域，网络被抽象成为一些顶点和顶点之间的连线即边。例如在统计物理学和网络分析中，科学家把个体与相互作用直接抽象为顶点与边的系统称为网络。目前已经得到研究的网络在结构上主要包括：规则（regular）网络、随机（random）网络和无标度网络等。在图论中，所谓规则网络如一维链、二维晶格即具有平移对称性的网络。20世纪50年代以后无明确设计原理的、具有随意连接关系的大规模网络，首先被匈牙利数学家Paul Erds和Alfred Renyi描述为随机网络[6]。这是最简单的也是被大多数人认识的复杂网络。在图论中，由N个顶点构成的图中，可以存在条边，从中随机连接M

图2.1 Small-World网络模型（左图为规则网络，右图为随机网络）

图2.2 Small-World网络的几何性质。同时有大集聚程度
而小最短距离Small-World网络的重要特征，而且
此性质在p略大于0到小于1的很大范围内存在

条边所构成的网络就叫随机网络。另一类网络是同时具有高集聚程度、小最短路径的网络，称为小世界网络。Watts和Strogatz发现，对于0<p<1的情况，存在一个很大的p的区域，同时拥有较大的集聚程度和较小的最短距离。一个典型的小世界网络见图2.1中间的示意图，其几何性质如图2.2所示[3,4]。
目前，复杂网络研究的内容主要包括：网络的几何性质，网络的形成机制，网络演化的统计规律，网络上的模型性质，以及网络的结构稳定性，网络的演化动力学机制等问题。其中在自然科学领域，网络研究的基本测度包括：度（degree）及其分布特征，度的相关性，集聚程度及其分布特征，最短距离及其分布特征，介数(betweenness) 及其分布特征，连通集团的规模分布。
通过这些研究，三种概念在当代对复杂网络的思考中占有重要地位。
第一，小世界的概念。它以简单的措辞描述了大多数网络尽管规模很大但是任意两个节（顶）点间却有一条相当短的路径的事实。以日常语言看，它反映的是相互关系的数目可以很小但却能够连接世界的事实，例如，在社会网络中，人与人相互认识的关系很少，但是却可以找到很远的无关系的其他人。正如麦克卢汉所说，地球变得越来越小，变成一个地球村，也就是说，变成一个小世界。
第二，集群即集聚程度(clustering coefficient)的概念。例如，社会网络中总是存在熟人圈或朋友圈，其中每个成员都认识其他成员。集聚程度的意义是网络集团化的程度；这是一种网络的内聚倾向。连通集团概念反映的是一个大网络中各集聚的小网络分布和相互联系的状况。例如，它可以反映这个朋友圈与另一个朋友圈的相互关系。
第三，幂律（power law）的度分布概念。度指的是网络中顶（节）点（相当于一个个体）与顶点关系（用网络中的边表达）的数量；度的相关性指顶点之间关系的联系紧密性；介数是一个重要的全局几何量。顶点u的介数含义为网络中所有的最短路径之中，经过u的数量。它反映了顶点u（即网络中有关联的个体）的影响力。无标度网络的特征主要集中反映了集聚的集中性。
科学家发现绝大多数实际的复杂网络都具有如下几个基本特征[7]：
1）网络行为的统计性：网络节点数可以有成百上千万，甚至更多，从而使得大规模性的网络行为具有统计特性。2）节点动力学行为的复杂性：各个节点本身可以是各非线性系统具有分岔和混沌等非线性动力学行为。3）网络连接的稀疏性：一个N个节点的具有全局耦合结构的网络的连接数目为O()，而实际大型网络的连接数目通常为O(N)。4）连接结构的复杂性：网络连接结构既非完全规则也非完全随机。5）网络的时空演化复杂性：复杂网络具有空间和时间的演化复杂性，展示出丰富的复杂行为，特别是网络节点之间的不同类型的同步化运动（包括出现周期、非周期[混沌]和阵发行为等运动）。
以上5种特征，反映了实际网络的复杂性特征。一方面，它具有无序演化的特征，另一方面，它也具有增加有序程度的演化特征。它具有分形和混沌的特征，具有自组织演化的特征，也具有形成序参量的特征。因此，复杂网络的研究可能会综合以往的各种自组织理论、非线性和复杂性理论研究的成果，从而形成新的复杂性研究机制的理论。
2.1.2 度量参数
图论和统计学为定量研究复杂网络提供了理论基础。图论由瑞典数学家欧拉于18世纪开创。主要研究那些规模小而且结构规则的网络。最近几年，随着计算机处理能力的提高和应用范围的拓展，各个学科领域都收集到了大量真实复杂网络的数据并能够以定量的方式分析这些数据。在复杂网络的研究中，有很多参数可以反映网络的特征，其中最重要的是节点的度分布、平均距离和集聚系数这三个参数。
节点的度（Degree）为其所邻接边的数目，度分布P(k)表示网络中度值为k的节点出现的概率。度分布特性反映了网络拓扑的连接情况。1999年，Barabtsi和Albea指出现实世界中许多复杂网络的度分布具有幂律（Power-Law）形式。由于幂律分布没有标志性的特征长度，因而该类网络称为无尺度网络（Scale-Free Networks）。
网络中两个节点之间的最小连接数为这两个节点间的距离。网络中所有节点间距离的平均值就是网络的平均距离(Average Distance)。它确定了网络中任一对节点间的最有代表性的路径长度，规模大的复杂网络，其平均距离不一定大，相反，现实中多数复杂网络的平均距离都相对较小，这构成了复杂网络的小世界现象，也就是任何两个看似没有联系的节点，可以通过较短的连接把它们关联在一起。实验表明，多数复杂网络的平均距离都比较小。如：WWW网络为3.1，电影演员合作网络3.65。
集聚系数(Clustering Coeffcients)是指若节点i有条边与其它个节点相连，则这个节点之间最多可能有条边相连，令E为这k个节点实际连接的边数，则i节点的集聚系数定义为：。网络的集聚系数为每个节点集聚系数之和的平均。这个参数也是小世界现象的衡量标准之一。它的值可以反映出网络的结构特征：在现实中，复杂网络通常是由不同粒度上联系紧密的社区所组成，这些社区内部联系紧密而且频繁，但是社区之间只有较少的连接数。相对随机网络而言，复杂网络中的集聚系数要高得多，为0.1到0.8之间。
2.1.3 研究意义
复杂网络的研究，提供了一种复杂性研究的新视角、新方法，并且提供了一种比较的视野。可以在复杂网络研究的旗帜下，对各种复杂网络进行比较、研究和综合概括。
首先，网络的现象涵盖极其广泛，因此，对网络的研究极具意义。例如，科学家发现大多数实际的系统都是复杂网络，从细菌、细胞和蛋白质系统，到人类性关系，甚至到科学家之间的合作，论文之间的引证联系，大型的Internet和WWW网络等，它们都构成某种网络系统，也构成某种复杂网络系统。因此，如若发现一种概括它们的共同特性的观点和方法，则能够抓取这类网络的关键，形成深入的认识。而复杂网络研究恰恰在这点上发现了它们同时都具有的3个主要特征：小世界、无标度性和高集团度。
其次，复杂网络的研究，在大量网络现象的基础上抽象出两种复杂网络：一种即小世界网络，另一种即无标度网络。这两种网络都同时具有两个基本特征：高平均集聚程度、小的最短路径，而无标度网络的度分布又具有幂律分布特征。因此无标度网络的复杂性程度还高于小世界网络的复杂性程度。高平均集聚程度反映了事物在小世界的境况下自发走向有序的态势；小的最短路径特征反映了演化速度快的特征。系统的低层次的因素之间的局部交互作用会更密集，作用会更频繁，在系统层次会涌现出更多的性质。Watts和Strogatz文章研究的传染病模型中，其接触传染率为1，感染的顶点（可能是个体的人）在一个单位时间以后退出系统。对于任何网络，这样的传染病都将在整个网络扩散；研究其扩散时间，发现对于从规则网络到随机网络的所有p∈（0，1）网络，其扩散时间刚好与最短路径一致。也就是说，在规则网络上传播所需时间长，但是只要p略大于0，传染病就会得到迅速传播。这很好地说明了最短路径这一几何量的作用（例如，SARS传播的控制就不仅仅是提高治疗的医学问题，而且是一个如何切断网络的问题）[2]。在这个传染病模型上，任何一个顶点都同时向其所有近邻传播，如果集聚程度高，传播会更广泛。科学家发现在小世界网络上同时具有驰豫时间短、共振性好的特征，而这些特征就分别来源于网络的小最短路径和高集聚程度。这都说明高集聚程度和小最短路径是小世界网络上复杂性增加的两个特性。
在复杂网络研究中，科学家所采用的方法是在规则网络的基础上，断开其中某些顶点的链接，然后导入随机链接其中若干顶点的方法，结果构造出来的网络立刻就具有了小世界的特性。在无标度网络的构造中，科学家引入两个规则：其一，节（顶）点按照一定速率增长；其二，新增加的节（顶）点与原来网络节点的连接是按照原来连接概率高的偏好择优连接的方式进行。这两个简单规则立刻就引起了网络的复杂性增长。这种方法的实质涵义实际上是在本体的规则性中引入了随机性和吸引子。构造后出现的复杂性含义是极其丰富的，也许世界的复杂性增长就是通过一定的随机性开始的。随机性是导致无序的观点在这里被颠覆了，小的随机性的渗入就导致了更高的平均集聚程度，导致有序的产生。
在混沌的研究中，可以同样发现，混沌是一种确定性中的类随机性。在规则性中引入随机性，在复杂网络中具有异曲同工之妙。规则的东西看似有序，实际上只是一种平庸的有序。世界需要规则，同样需要随机；世界需要有序，同样需要无序。这种辩证法并不是说说而已的语言游戏，而是真实地在发生作用的演化动力学机制：无序与有序展开的矛盾。
另外，复杂网络的基本测度性概念也反映了网络内某些个体对其他个体的影响，以及其他个体对这些个体的影响，这种双向的影响是网络分析的重点。如一个顶点的度的概念，一个顶点的度是指与此顶点连接的边的数量。边是什么？边是相互作用的数量反映。那么，一个顶点的度就反映了与这个顶点（个体）相互作用的多寡，关注的重心是相互作用。
在复杂网络研究中，不仅研究者非常客观地关注系统内某个体与其他个体之间的相互作用，而且还在整体的角度注视到系统的整体相互作用。表达这种整体相互作用的概念如“介数”这个非常典型的概念，其英文表达为“betweenness”，它是一个重要的全局几何量（统计性质）。它反映了顶点u的影响力。通过复杂网络研究，可以看到关于相互作用的认识已经在一定程度上有了量化研究的成果出现，这反映了在相互作

图2.3 随机网络中5节点(较大)
与其他节点（灰点）联系只占全部节点联系的27%

图2.4 无标度网络中5节点(较大)与
其他节点(灰点)联系占到全部节点联系的60％
用研究上的进步。事实上，在牛顿力学里，第三定律描述了力学的相互作用；万有引力定律描述了引力相互作用；在物理学领域，四种相互作用的认识，让人们认识到了强、弱、电磁和引力相互作用的性质、作用范围等；在化学层次，化学反应也是某种相互作用；生物学层次，捕食者与被捕食者的关系也同样是某种相互作用；这样似乎发现，复杂性层次越高，相互作用越不好描述。把相互作用分解成为A对B的作用和B对A的作用似乎比较平庸，但是，继续分析这种作用的直接性、间接性和作用的程度，分析一对多和多对一的作用，并且进一步把这种作用细致化为集聚程度、最短路径，把作用与历史因素、敏感性条件联系起来，则是自复杂性研究以来的功绩，特别是复杂网络研究的功绩。
2.2 复杂网络中心化
复杂网络的中心化研究起源于社会网络，Freeman等人的工作最具代表性[8]。通过中心化可以量化个人在社会中的地位。除在社会网络中得到成功应用之外，中心化还被应用于许多其它网络系统，如蛋白质网络[9]（用于寻找致命生物蛋白的位置）；通信网络和交通网络[10]（寻找网络的瓶颈、控制网络的拥塞）；城镇网络和社区网络[11,12]（了解人群的生活空间和城市的布局）等。中心化甚至被成功地应用于公共安全和公共健康领域，如针对2001年的恐怖分子网络[13]和2002年的SARS网络所进行的中心化。不同类型的复杂网络通常需要使用不同的中心化指标来进行中心化。典型的中心化指标包括度（degree）指标、紧密度（closeness）指标、介数（betweenness）指标等，这些参数往往结合起来使用，构成多重测试（multiple centrality）。
中心化指标是用来对网络进行中心化的参数，任何网络中的任何节点均可定义中心化指标。合理定义的中心化指标应该满足下列条件[14]：
1) 中心化指标应该是对称的，即若对网络的节点重新编号，中心化指标应该不变。
2) 无论将一个节点看成整个图的节点，还是将其看成一个连通分支的节点，所得到的中心化指标的值应该一致。
3) 孤立节点的中心化指标应该最小。
4) 在具有链式结构（如图2.5a）的网络中，节点的中心化指标应该从边缘向中心递增，即越靠近中心，节点的中心化程度应该越高。
5) 在所有的具有n个节点的连通网络中，链式结构网络的顶端节点的中心化指标

图2.5 链式(a)、星型(b)结构简图
应该最小，而星型结构（如图2.5b）网络的中心节点的中心化指标应该最大。
6) 移去某个节点的某条边，至少不会增加该节点的中心化指标。
下面将分析并比较常用的一些中心化指标[15]。
2.2.1 度指标
度指标(Degree Centrality)是研究无标度网络拓扑结构的基本参数，用于描述在静态网络中节点所产生的直接影响力，其值为与该节点直接相连的节点数。
设网络具有n个节点,则节点x的度指标定义为
(2.1)
其中d(x)表示与节点x直接相连的节点数，称为该节点的度。
为了根据度指标来比较不同规模的网络中的节点的中心化，需要对度指标进行归一化处理。注意到具有n个节点的网络中节点的度不会超过n-1，归一化的度指标定义为
(2.2)
利用节点的度指标进行中心化，是因为节点的度值体现了该节点与其周围节点之间建立直接联系的能力。如图2.6所示，具有n个节点的星型网络（图2.6a）中，中心节点的度指标为n-1，其余节点的度指标均为1；在环形结构（图2.6b）中，任何节点的度指标均为2，在链式结构（图2.6c）中，除了链的顶端节点的度指标等于1外，其余节点的度指标均为2。因此，根据度指标，星型网络的中心节点具有超强的联系能力，环形网络中各个节点同等重要，而链式网络中除端节点外的其余节点均同等重要。

图2.6 三种结构的中心化比较
由上述例子可以看出，度指标基本上可以刻画节点在网络中的中心化程度，唯一的不足是，在链式网络中没有反映出接近中心的节点的中心化程度高于其余节点。事实上，度指标不满足关于中心化指标的条件4)。
2.2.2 紧密度指标
紧密度(Closeness Centrality)指标用于刻画网络中的节点通过网络到达网络中其它节点的难易程度，其值定义为该节点到达所有其它节点的距离之和的倒数。
设网络具有n个节点，则节点x的紧密度指标定义为
(2.3)
注意到具有n个节点的网络中，节点到达所有其它节点的距离之和不会小于n - 1,故归一化的紧密度指标定义为
(2.4)
度指标反映的是一个节点对于网络中其它节点的直接影响力，而紧密度指标则反映的是节点通过网络对其它节点施加影响的能力，因而紧密度指标较之度指标更加能够反映网络全局的结构。应用紧密度指标进行中心化不仅考虑到了节点度值的大小，而且还考虑到了节点在网络中所处位置的中心性，如图2.7，图2.7a是根据度指标测试的结果，而图2.7b则是根据紧密度指标测试的结果。通过对比容易发现，根据紧密度指标进行中心化测试的准确度明显高于根据度指标进行中心化测试的准确度。

图2.7 对同一网络分别用度指标和紧密度指标测试的结果
2.2.3 特征向量指标
一个节点的度指标仅仅描述了该节点对于其它节点的直接影响力，若一个节点与另一个度值很高的节点之间存在连接,则该节点的影响力也应该很大，如：一个学校的学生的知名度往往依赖于他朋友的知名度如何，一个节点的信息占有率还取决于它与什么样的节点在交流。但这种影响力通常很难根据其度指标进行判断，应该引进一种新的中心化指标来分析这种通过具有高度值的相邻节点所获得的间接影响力。这种中心化指标应该具有这样一种特性，即一个节点的中心化指标应该与其相邻节点的中心化指标存在线性关系，它是周围节点的中心性值的线性迭加。特征向量指标(Eigenvector Centrality)就是这样一个中心化指标。设网络具有n个节点，其邻接矩阵记为A，其中aij=1表示i，j之间存在连接，aij=0表示两者不存在连接。λ为A的主特征值，表示一个常量。e=(e1,e2,...,en)为矩阵A对应的λ的特征向量，
即
(2.5)
即
(2.6)
节点i的特征向量指标即定义为公式(2.5)中的ei，记为Ce(i)。
特征向量指标主要应用于传播性网络，如疾病传播，特征向量指标高的节点说明该节点与病源很近，通常是需要重点防范或重点利用的关键节点。
2.2.4 介数指标
介数指标(Betweenness Centrality)刻画了网络中的节点对于信息流动的影响力。设网络具有n个节点，则节点x的介数指标定义为
(2.7)
其中，表示节点j和节点k之间的最短路径数，(x)表示节点j和节点k之间经过节点x的最短路径数。
注意到具有n个节点的网络中，对于给定节点x来说，最为极端的情形是任意两个其它节点之间的最短路径均经过节点x，此时，该节点的介数指标达到最大值(n-1)(n-2)/2。因而，归一化的介数指标可以定义为
(2.8)
介数指标中引进了信息流动的概念，在使用最短路径路由算法的网络中，介数指标刻画了信息流经给定节点的可能性，任一节点的介数指标均会随着经过该节点的信息流

图2.8 介数指标的计算结果
的增加而增大，利用介数指标可以确定信息负载繁重的网络节点，而在几何位置上处于中心地位的节点不一定可以通过介数指标加以确定，如图2.8中的中心节点的介数指标仅为0.028。
2.2.5 流介数指标
介数指标的定义是基于最短路径，对于确定以最短路径进行路由的网络中的高负载节点非常重要，然而并不是每个网络均是以最短路径策略进行路由选择的。
流介数指标(Flow Betweenness Centrality)去除最短路径的概念来定义介数，因而流介数指标能够确定整体上的几何中心节点。流介数指标定义为
(2.9)
其中，表示节点j和节点k之间的所有路径数，(x)表示节点j和节点k之间经过节点x的所有路径数。
利用流介数指标对图2.8中的网络重新进行中心化，得到图图2.9所示的结果，此时几何中心节点的中心化地位得到体现。

图2.9 流介数指标的计算结果
复杂网络的中心化问题不仅仅是发现网络图形的几何中心，更为重要的是发现在人们所关心的几个状态上表现特别的节点，因而常常需要为满足各种不同应用的需要而专门设计的中心化指标，如随机行走介数指标(random-walk betweenness centrality)、图中心指标(graph centrality)等，限于篇幅，本文不再一一介绍。
以上介绍的是几种典型的中心化指标，通常应该根据需要选择其中的一种或几种进行网络的中心化，针对不同类型的网络所选择的中心化指标常常也不相同。基于度指标的中心化方法适用于静态网络分析，基于介数指标的中心化方法适用于网络动力学分析，而流介数指标以及特征向量指标可以用于聚集系数高的网络之中。对于一些特殊的网络，可能还需要引进新的中心化指标。
2.3 软件系统网络化特征
在面向对象的程序设计语言中，类是一种数据类型，它封装了特定的数据和行为并向外界提供交互的接口。作为封装和重用的单元，它隐藏了实现的细节，并向外界提供服务，对象是类在运行时生成的实例。类之间的关系主要有继承关系和聚合关系两种。继承是指可以把一个类作为其他类的子类，从而继承父类的数据和行为；聚合则是在一个类中使用了另一个类的对象。这种类之间的使用，被使用关系或者依赖，被依赖关系可以形成一个网络。
在面向对象的软件系统中，把类、对象看作节点。类、对象之间的关系看作边，可以形成一个复杂网络拓扑。类和对象关系网络可以反映程序内部复杂的交互关系。
Java是一种纯的面向对象编程语言，可以方便地转换为网络拓扑的形式进行分析。基于开源软件DependencyFinde[16]和Jun[17]，通过编程把层次化的软件依赖关系转换成为网络拓扑的形式，并分析了用Java语言编写的四个不同规模的类库压缩包。rt.jar是Java语言中最常用的类库。使用jre1.5.0l_02版本中的程序抽取其关系网络。tools.jar是SUN公司为Java语言本身编写的工具集合。xalan.jar是Apache组织提供的高性能XSL样式单处理器。xml-apis.jar是常用的处理XML的标准APl。四个待分析的类库压缩包的具体统计情况如表2.l所示[1]：
表2.l 待分析的四个Java软件系统
类库
节点数
边数
类库文件大小
xml-apis.jar
257
1096
122KB
xalan.jar
957
8266
1741KB
tools.jar
2338
21225
6654KB
rt.jar
12836
126654
32927KB
这四个类库压缩包都是大型软件组织提供的稳定的Java类库。其中使用了软件工程的方法对代码进行了设计和优化重组，可以认为它们都是组织良好的软件系统。其中xml-ais.jar的软件拓扑如图2.10所示：

图2.10 xml-apis.jar的软件拓扑
从图2.10中可以直观地看出，多数节点的连接数很少，而少