《复杂网络拓扑论文（精品）.docx》由会员分享，可在线阅读，更多相关《复杂网络拓扑论文（精品）.docx（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、复杂网络拓扑论文复杂网络可视化方案设计的关键在于可视化工具和算法的选择，本文设计的方案中，可视化工具选择基于Python的软件包NetworkX7，压缩算法采用提出的一种基于节点和边的关键性压缩网络拓扑的算法NECB，NodeandEdgeCentralityBasedNetworkCompressingAlgorithm，布点算法则选择基于FDA改良的经典FR算法8，整体方案如图2-1所示。原始的网络拓扑数据经过NetworkX作图生成网络拓扑图，而NECB算法和FR算法则利用NetworkX通过Python编程实现。1NetworkX介绍NetworkX是一基于Python语言开发的网络可
2、视化工具，集成了诸多专门针对复杂网络的分析算法，非常合适复杂网络拓扑的可视化，并能结合其它的Python软件包，比方Numpy、Scipy、Matplotlib、Pygraphviz、Mayavi2等数据分析和可视化工具进行使用。NetworX支持邻接矩阵、边列表、GML、Pajek等多种类型的网络拓扑数据的读写，可以逐个添加或删除单个节点和边，同时还提供了大量直接生成某一类型复杂网络的函数，针对网络拓扑的性能分析，NetworkX也提供了很多算法，对于同类型的网络，还支持并集、交集、差、子图等集合操作。2NECB压缩算法基于节点和边的拓扑压缩关键在于压缩标准的制定，怎样评判压缩算法的有效性也
3、是重要的方面。2.1压缩节点的选择NECB压缩算法中的压缩是针对节点进行的，这里仅针对简单无向图进行讨论，对于网络拓扑G=(V，E)中任意节点v，能否删除它的参考标准主要有两点：节点v的度deg(v)和网络拓扑中经过该点最短途径数。节点的度是网络拓扑最重要的属性之一，假如一个节点的度数越大，讲明它与很多节点都有关联，那么它在网络拓扑中也就显得很关键9。NECB算法采用的计算公式如下。是为了将其值归一化在0，1范围内。网络拓扑的平均最短途径长度也是其重要的属性之一，假如网络拓扑中多条最短途径经过某一节点，显然该节点扮演着重要角色9，NECB算法采用的计算公式如下。用Wpath(v)的值衡量节点v
4、关于最短途径的关键性，(s，t)表示网络拓扑中所有最短途径的集合，表示经过节点v的最短途径，(V-1)(V-2)/2是经过节点v的最短途径数最大可能值，乘以2/(V-1)(V-2)能够将其值归一化在0，1范围内。2.2压缩算法流程NECB算法中的压缩本质上就是删除节点，这里对删除进行一下讲明：对于网络拓扑G=(V，E)，删除节点v是指从E中删除所有包含v的边，然后从V中删除v生成新的网络G，NECB算法流程如图2-2所示。首先计算网络拓扑中各个节点的度和所有节点之间的最短途径，然后根据公式和分别计算Wdeg(v)和Wpath(v)，删除值相对较小的次要节点，保留值相对较大的重要节点，再将得到的两个节点集合并。假设合并后的节点集合为V1，对于复杂网络，通常情况下，节点集合V1构成的压缩图是连通的，若不连通，则需要对压缩拓扑进行补充，选择一个最小的节点集合V2补充到压缩拓扑中，至少使得由V1V2中节点构成的压缩图是连通的，这是一个NP完全问题，NECB采用的是一种叫做KeepOne的策,。V1中节点在G中的任意一条最短途径上的所有节点组成V2，V1V2的完全图与原始网络拓扑G的交集即为最终的压缩网络拓扑G。