复杂网络拓扑论文范文

本站小编为你精心准备了复杂网络拓扑论文参考范文，愿这些范文能点燃您思维的火花，激发您的写作灵感。欢迎深入阅读并收藏。

复杂网络可视化方案设计的关键在于可视化工具和算法的选择，本文设计的方案中，可视化工具选择基于Python的软件包NetworkX[7]，压缩算法采用提出的一种基于节点和边的关键性压缩网络拓扑的算法（NECB，NodeandEdgeCentralityBasedNetworkCompressingAlgorithm），布点算法则选择基于FDA改进的经典FR算法[8]，整体方案如图2-1所示。原始的网络拓扑数据经过NetworkX作图生成网络拓扑图，而NECB算法和FR算法则利用NetworkX通过Python编程实现。

1NetworkX介绍

NetworkX是一基于Python语言开发的网络可视化工具，集成了众多专门针对复杂网络的分析算法，非常适合复杂网络拓扑的可视化，并能结合其它的Python软件包，比如Numpy、Scipy、Matplotlib、Pygraphviz、Mayavi2等数据分析和可视化工具进行使用。NetworX支持邻接矩阵、边列表、GML、Pajek等多种类型的网络拓扑数据的读写，也可逐个添加或删除单个节点和边，同时还提供了大量直接生成某一类型复杂网络的函数，针对网络拓扑的性能分析，NetworkX也提供了许多算法，对于同类型的网络，还支持并集、交集、差、子图等集合操作。

2NECB压缩算法

基于节点和边的拓扑压缩关键在于压缩标准的制定，如何评判压缩算法的有效性也是重要的方面。

2.1压缩节点的选择NECB压缩算法中的压缩是针对节点进行的，这里仅针对简单无向图进行讨论，对于网络拓扑G=(V，E)中任意节点v，是否删除它的参考标准主要有两点：节点v的度deg(v)和网络拓扑中经过该点最短路径数。节点的度是网络拓扑最重要的属性之一，如果一个节点的度数越大，说明它与很多节点都有关联，那么它在网络拓扑中也就显得很关键[9]。NECB算法采用的计算公式如下。是为了将其值归一化在[0，1]范围内。网络拓扑的平均最短路径长度也是其重要的属性之一，如果网络拓扑中多条最短路径经过某一节点，显然该节点扮演着重要角色[9]，NECB算法采用的计算公式如下。用Wpath(v)的值衡量节点v关于最短路径的关键性，Π(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补充到压缩拓扑中，至少使得由V1∪V2中节点构成的压缩图是连通的，这是一个NP完全问题，NECB采用的是一种叫做KeepOne的策,。V1中节点在G中的任意一条最短路径上的所有节点组成V2，V1∪V2的完全图与原始网络拓扑G的交集即为最终的压缩网络拓扑G’。

作者：张畅谢钧胡谷雨段伟伟单位：解放军理工大学，指挥信息系统学院