基于Centrality的Cluster发现算法设计与实现
以下是资料介绍,如需要完整的请充值下载.
1.无需注册登录,支付后按照提示操作即可获取该资料.
2.资料以网页介绍的为准,下载后不会有水印.资料仅供学习参考之用.
密 惠 保
1.无需注册登录,支付后按照提示操作即可获取该资料.
2.资料以网页介绍的为准,下载后不会有水印.资料仅供学习参考之用.
密 惠 保
资料介绍：
度量参数
图论和统计学为定量研究复杂网络提供了理论基础。图论由瑞典数学家欧拉于18世纪开创。主要研究那些规模小而且结构规则的网络。最近几年，随着计算机处理能力的提高和应用范围的拓展，各个学科领域都收集到了大量真实复杂网络的数据并能够以定量的方式分析这些数据。在复杂网络的研究中，有很多参数可以反映网络的特征，其中最重要的是节点的度分布、平均距离和集聚系数这三个参数。
节点的度（Degree）为其所邻接边的数目，度分布P(k)表示网络中度值为k的节点出现的概率。度分布特性反映了网络拓扑的连接情况。1999年，Barabtsi和Albea指出现实世界中许多复杂网络的度分布具有幂律（Power-Law）形式。由于幂律分布没有标志性的特征长度，因而该类网络称为无尺度网络（Scale-Free Networks）。
网络中两个节点之间的最小连接数为这两个节点间的距离。网络中所有节点间距离的平均值就是网络的平均距离(Average Distance)。它确定了网络中任一对节点间的最有代表性的路径长度，规模大的复杂网络，其平均距离不一定大，相反，现实中多数复杂网络的平均距离都相对较小，这构成了复杂网络的小世界现象，也就是任何两个看似没有联系的节点，可以通过较短的连接把它们关联在一起。实验表明，多数复杂网络的平均距离都比较小。如：WWW网络为3.1，电影演员合作网络3.65。 本文来自think58 [来源：http://www.think58.com]
复杂网络中心化
复杂网络的中心化研究起源于社会网络，Freeman等人的工作最具代表性[8]。通过中心化可以量化个人在社会中的地位。除在社会网络中得到成功应用之外，中心化还被应用于许多其它网络系统，如蛋白质网络[9]（用于寻找致命生物蛋白的位置）；通信网络和交通网络[10]（寻找网络的瓶颈、控制网络的拥塞）；城镇网络和社区网络[11,12]（了解人群的生活空间和城市的布局）等。中心化甚至被成功地应用于公共安全和公共健康领域，如针对2001年的恐怖分子网络[13]和2002年的SARS网络所进行的中心化。不同类型的复杂网络通常需要使用不同的中心化指标来进行中心化。典型的中心化指标包括度（degree）指标、紧密度（closeness）指标、介数（betweenness）指标等，这些参数往往结合起来使用，构成多重测试（multiple centrality）。
中心化指标是用来对网络进行中心化的参数，任何网络中的任何节点均可定义中心化指标。合理定义的中心化指标应该满足下列条件[14]：
1) 中心化指标应该是对称的，即若对网络的节点重新编号，中心化指标应该不变。
2) 无论将一个节点看成整个图的节点，还是将其看成一个连通分支的节点，所得到的中心化指标的值应该一致。
3) 孤立节点的中心化指标应该最小。 think58.com
4) 在具有链式结构（如图2.5a）的网络中，节点的中心化指标应该从边缘向中心递增，即越靠近中心，节点的中心化程度应该越高。
软件系统网络化特征
在面向对象的程序设计语言中，类是一种数据类型，它封装了特定的数据和行为并向外界提供交互的接口。作为封装和重用的单元，它隐藏了实现的细节，并向外界提供服务，对象是类在运行时生成的实例。类之间的关系主要有继承关系和聚合关系两种。继承是指可以把一个类作为其他类的子类，从而继承父类的数据和行为；聚合则是在一个类中使用了另一个类的对象。这种类之间的使用，被使用关系或者依赖，被依赖关系可以形成一个网络。
在面向对象的软件系统中，把类、对象看作节点。类、对象之间的关系看作边，可以形成一个复杂网络拓扑。类和对象关系网络可以反映程序内部复杂的交互关系。
Java是一种纯的面向对象编程语言，可以方便地转换为网络拓扑的形式进行分析。基于开源软件DependencyFinde[16]和Jun[17]，通过编程把层次化的软件依赖关系转换成为网络拓扑的形式，并分析了用Java语言编写的四个不同规模的类库压缩包。rt.jar是Java语言中最常用的类库。使用jre1.5.0l_02版本中的程序抽取其关系网络。
集群分析
人类日常生活中所遭遇到的人、事、物数量非常多，如果每遇到一个人、事物是，都必须重新学习认识及思考对应之策，不仅浪费时间，也容易误事。因此长久依赖，人们便不断尝试将繁多的人事物，按照特性分成数目较少的类别或群体，使每一类别内的事物性质非常类似，可以使用相同的方式对待或处理。譬如生物学家将动物、植物或细胞繁殖予以分类；而在市场行销研究中，则将顾客根据其购买行为和人口统计上的资料予以分类。 think58.com [来源：http://think58.com]
尽管分类的工作已经有很长的一段历史，但是以数量的方法来进行系统化的分类，则是近二十年之事。今天，更借由电脑之助，强大的计算及储存能力，能够迅速处理复杂的计算问题，使得这项数量分类方法，广泛地运用在生物学、心理学、教育学、企业管理等许多不同的领域之中。
集群分析是一种逻辑程序，探讨如何将欲测对象分为类似的群体。其最主要目的，乃是利用客观的与计量的方法，将食物根据某些属性归集在各个群体之中，使得在同一个集群内的事物都具有相同的特性，而在不同的集群之间却有显著的差异。如果用几何图形来说明的话，同一集群内的分子应聚集在一起，而不同集群的分子应彼此远离。
在过去，软件集群主要应用在逆向工程方面[19-21]，这些方法试图利用系统不同部分的依赖信息来识别系统中的集群。另外有些研究方法使用模式匹配技术[22]和概念分析[23]来识别软件集群。现在，在面向对象软件系统中，使用谱图分割技术来发现软件集群。谱图分割主要是以一种带权类依赖图作为面向对象系统的UML类图的抽象表示，其中类依赖图的各边上权值对应于类图中的相应关系[24]。针对带权类依赖图运用代数图论中图的Laplace谱的连通特性以迭代分割的方式对其进行划分，得到所需开发的系统构件。通过实验表明，该方法是一种有效的面向对象软件系统分解方法，并且分解所得到的构件具有较高的内聚性。在本算法设计中，借鉴了这种分割技术，移除承载数据流量较大的边来分割原软件系统发现软件集群的思想。 copyright think58 [资料来源：http://THINK58.com]
图论和统计学为定量研究复杂网络提供了理论基础。图论由瑞典数学家欧拉于18世纪开创。主要研究那些规模小而且结构规则的网络。最近几年，随着计算机处理能力的提高和应用范围的拓展，各个学科领域都收集到了大量真实复杂网络的数据并能够以定量的方式分析这些数据。在复杂网络的研究中，有很多参数可以反映网络的特征，其中最重要的是节点的度分布、平均距离和集聚系数这三个参数。
节点的度（Degree）为其所邻接边的数目，度分布P(k)表示网络中度值为k的节点出现的概率。度分布特性反映了网络拓扑的连接情况。1999年，Barabtsi和Albea指出现实世界中许多复杂网络的度分布具有幂律（Power-Law）形式。由于幂律分布没有标志性的特征长度，因而该类网络称为无尺度网络（Scale-Free Networks）。
网络中两个节点之间的最小连接数为这两个节点间的距离。网络中所有节点间距离的平均值就是网络的平均距离(Average Distance)。它确定了网络中任一对节点间的最有代表性的路径长度，规模大的复杂网络，其平均距离不一定大，相反，现实中多数复杂网络的平均距离都相对较小，这构成了复杂网络的小世界现象，也就是任何两个看似没有联系的节点，可以通过较短的连接把它们关联在一起。实验表明，多数复杂网络的平均距离都比较小。如：WWW网络为3.1，电影演员合作网络3.65。 本文来自think58 [来源：http://www.think58.com]
复杂网络中心化
复杂网络的中心化研究起源于社会网络，Freeman等人的工作最具代表性[8]。通过中心化可以量化个人在社会中的地位。除在社会网络中得到成功应用之外，中心化还被应用于许多其它网络系统，如蛋白质网络[9]（用于寻找致命生物蛋白的位置）；通信网络和交通网络[10]（寻找网络的瓶颈、控制网络的拥塞）；城镇网络和社区网络[11,12]（了解人群的生活空间和城市的布局）等。中心化甚至被成功地应用于公共安全和公共健康领域，如针对2001年的恐怖分子网络[13]和2002年的SARS网络所进行的中心化。不同类型的复杂网络通常需要使用不同的中心化指标来进行中心化。典型的中心化指标包括度（degree）指标、紧密度（closeness）指标、介数（betweenness）指标等，这些参数往往结合起来使用，构成多重测试（multiple centrality）。
中心化指标是用来对网络进行中心化的参数，任何网络中的任何节点均可定义中心化指标。合理定义的中心化指标应该满足下列条件[14]：
1) 中心化指标应该是对称的，即若对网络的节点重新编号，中心化指标应该不变。
2) 无论将一个节点看成整个图的节点，还是将其看成一个连通分支的节点，所得到的中心化指标的值应该一致。
3) 孤立节点的中心化指标应该最小。 think58.com
[来源：http://think58.com]
4) 在具有链式结构（如图2.5a）的网络中，节点的中心化指标应该从边缘向中心递增，即越靠近中心，节点的中心化程度应该越高。
软件系统网络化特征
在面向对象的程序设计语言中，类是一种数据类型，它封装了特定的数据和行为并向外界提供交互的接口。作为封装和重用的单元，它隐藏了实现的细节，并向外界提供服务，对象是类在运行时生成的实例。类之间的关系主要有继承关系和聚合关系两种。继承是指可以把一个类作为其他类的子类，从而继承父类的数据和行为；聚合则是在一个类中使用了另一个类的对象。这种类之间的使用，被使用关系或者依赖，被依赖关系可以形成一个网络。
在面向对象的软件系统中，把类、对象看作节点。类、对象之间的关系看作边，可以形成一个复杂网络拓扑。类和对象关系网络可以反映程序内部复杂的交互关系。
Java是一种纯的面向对象编程语言，可以方便地转换为网络拓扑的形式进行分析。基于开源软件DependencyFinde[16]和Jun[17]，通过编程把层次化的软件依赖关系转换成为网络拓扑的形式，并分析了用Java语言编写的四个不同规模的类库压缩包。rt.jar是Java语言中最常用的类库。使用jre1.5.0l_02版本中的程序抽取其关系网络。
集群分析
人类日常生活中所遭遇到的人、事、物数量非常多，如果每遇到一个人、事物是，都必须重新学习认识及思考对应之策，不仅浪费时间，也容易误事。因此长久依赖，人们便不断尝试将繁多的人事物，按照特性分成数目较少的类别或群体，使每一类别内的事物性质非常类似，可以使用相同的方式对待或处理。譬如生物学家将动物、植物或细胞繁殖予以分类；而在市场行销研究中，则将顾客根据其购买行为和人口统计上的资料予以分类。 think58.com [来源：http://think58.com]
尽管分类的工作已经有很长的一段历史，但是以数量的方法来进行系统化的分类，则是近二十年之事。今天，更借由电脑之助，强大的计算及储存能力，能够迅速处理复杂的计算问题，使得这项数量分类方法，广泛地运用在生物学、心理学、教育学、企业管理等许多不同的领域之中。
集群分析是一种逻辑程序，探讨如何将欲测对象分为类似的群体。其最主要目的，乃是利用客观的与计量的方法，将食物根据某些属性归集在各个群体之中，使得在同一个集群内的事物都具有相同的特性，而在不同的集群之间却有显著的差异。如果用几何图形来说明的话，同一集群内的分子应聚集在一起，而不同集群的分子应彼此远离。
在过去，软件集群主要应用在逆向工程方面[19-21]，这些方法试图利用系统不同部分的依赖信息来识别系统中的集群。另外有些研究方法使用模式匹配技术[22]和概念分析[23]来识别软件集群。现在，在面向对象软件系统中，使用谱图分割技术来发现软件集群。谱图分割主要是以一种带权类依赖图作为面向对象系统的UML类图的抽象表示，其中类依赖图的各边上权值对应于类图中的相应关系[24]。针对带权类依赖图运用代数图论中图的Laplace谱的连通特性以迭代分割的方式对其进行划分，得到所需开发的系统构件。通过实验表明，该方法是一种有效的面向对象软件系统分解方法，并且分解所得到的构件具有较高的内聚性。在本算法设计中，借鉴了这种分割技术，移除承载数据流量较大的边来分割原软件系统发现软件集群的思想。 copyright think58 [资料来源：http://THINK58.com]