复杂网络仿真软件设计与实现

贺定龙，张功萱，李 晨，岳宝玲

（南京理工大学 计算机科学与工程学院，江苏 南京210094）

0 引 言

随着科研人员对生物网络、Web网络、社会网络的深入研究，发现了它们的一些共同特性［1，2］：整体稀疏，局部密集；整体分布具有低平均最短路径及高聚集度等小世界特性；幂率形式的度分布，也称为无尺度特性。具备上述特性的网络就是复杂网络。

复杂网络由于节点众多，且节点间的关系也相对复杂，故很难用传统的表格及文字进行表示，从而导致网络的一些关键信息被掩盖［3，4］。复杂网络的研究规模也发生了巨大变化，从最初几百个节点的小型网络变成了如今节点数上万甚至千万的大型网络，提供仿真软件对实际观察到的拓扑结构及相关动态行为进行模拟的需求已十分迫切［5］。

目前，NS2、pajek及VxInsight等国外的复杂网络分析软件已在学术界广泛使用。

NS2作为一种开源且免费的模拟软件，获得了许多研究人员的青睐。应用结果表明，网络技术的相关开发可以较容易地通过它实现。NS2的功能模块也在随着技术的变革而发展，几乎涵盖了网络技术的各个方面。

pajek是一款可在windows下运行的应用程序，可以进行复杂网络的分析及可视化。该软件非商业使用是免费的。特点是高性能地分析大型网络，如：有机分子、万维网、蛋白质网络等。

VxInsight是一款可用于获取大规模网络数据关联关系的软件。相对于只能访问单个数据元素并获取表层信息的软件而言，它能够获取更多的深层信息及关系，使研究人员能更容易地获取重要的关联关系及模式，并对相应研究提供较大的帮助或指导。

虽然上述分析软件都在学术界得到了广泛应用，但pajek晦涩难懂的操作界面及对小世界网络和无标度网络的支持不足，造成了部分研究人员很难用其进行相关研究。此外，由于科技竞争的考虑，美国限制VxInsight的出口。matlab虽然在国内仍有部分研究人员使用，但是由于其不是针对复杂网络设计的，故对于某些特殊的研究有很大局限性。

基于上述考虑，本文介绍了一种自主开发的复杂网络仿真软件。该软件是基于igraph创建给定参数的复杂网络，并结合双缓冲技术及布点算法实现了复杂网络的可视化，对复杂网络的相关研究提供了有效支持。

1 复杂网络的统计性质

复杂网络的结构决定了仿真软件的功能设计。早在图论的研究时期，图的统计性质分析就是一种重要的研究方法。复杂网络的研究也有类似的发展时期，网络结构的细微差别都会导致不同的系统功能需求，而网络中节点间的连接性质研究也是复杂网络研究的常用手段，故理解复杂网络的统计性质对仿真软件的功能设计具有重大意义，相关统计性质详述如下［6－8］：

（1）度分布：与节点i连接的边数即网络中节点i的度数，对于有向图而言，节点的度数分为出度及入度。前者是以节点i为弧尾的弧的数目，后者是以节点i为弧头的弧的数目。定义中，p（k）表示度分布，即图中度为k的节点的比例或随机均匀选择的点具有k度的概率。

（2）平均路径长度：连接节点i和j间的最短路径的边数称为两节点间的距离Lij，对所有Lij取平均值即为平均最短路径L，有时也被称为图的直径。网络中节点间的相隔距离可以通过平均路径长度反映，也被称为最大的最短路径长度。对所有节点对间的最短路径长度取平均值即可得平均最短路径长度，如下所示

复杂网络的小世界特性就是通过该性质的研究发现的，即现实中的许多网络的平均最短路径比预测的要小很多。

（3）聚集系数：复杂网络中有大量节点，而它们间的紧密关系则依靠聚集系数反映，有时也被称为传递性。

目前，学术界对于聚集系数有2种定义：第一种如下所示

另一种是由strogatz及watts联合提出的。首先定义0到1间的值为节点的局域聚集系数。对于复杂网络中的任一节点i，其聚集系数如下所示

其中，节点i的连接度为ki，即与i相连的节点数为ki，同时最多只有ki（ki－1）／2条边存在于这些相邻的节点间，邻间的边数则由ni表示，而网络的聚集系数则是对所有节点的局域聚集系数取平均值，如下所示

（4）介数：边或节点的负载就是介数，二者的定义十分相似。经过节点i的最短路径的数量即节点介数。

比如在万维网中，某站点k具有非常丰富的资源，其包含很多其他网页的链接，那么用户在网页间浏览时，会有极高的概率浏览该网页，则其作用非常大，若删除该网页会带来很多不便。

2 软件功能设计与实现

本文提出的复杂网络仿真软件适用于复杂网络的创建、编辑及可视化，并能为复杂网络的相关研究提供有效支持。该软件的体系结构如图1所示。

2.1 基于igraph的复杂网络创建及编辑

igraph是一款由c编写的开源软件包，并且是免费的，主要用于创建及编辑网络，网络类型包括有向图及无向图。很多图论问题都可以通过它解决，如：网络流及最小生成树等，并且还提供了最新的一些网络分析算法，如：社区结构搜索等。igraph定义了许多数据结构，如：队列、栈等，研究人员可以基于它们进行有效的上层开发，同时这些经典图算法的实现及基础的自定义数据结构也构成了igraph的主体。

鉴于igraph强大的网络创建及编辑能力，本文所设计的复杂网络仿真软件以igraph的c库为基础实现了给定参数及类型的复杂网络创建及编辑，如：ER网络、小世界网络、BA网络等。在可创建的众多复杂网络类型中，BA网络最具代表性，因为小世界网络虽然较好地反映了真实网络的小世界特性及聚集特性，但其度分布为指数形式，而由大量研究可知，幂率分布才是许多大规模真实网络的度分布，而这正是BA网络所具有的特性［9］。

图2 展示了该软件创建的BA网络示例，相关创建参数见表1。图2左半部分为网络显示区域，右半部分为概要信息区域及度分布图区域，其中概要信息区域主要涉及节点数，边数，连通性等基本信息，而度分布图区域是以节点度为横坐标，节点度的概率为纵坐标，并且图2中的度分布图也很好地验证了BA网络的度分布为幂率分布的特性。此外，还可以通过该软件工具栏中的添删节点及边等功能实现对复杂网络的后续编辑。

表1 BA网络创建参数

2.2 基于双缓冲技术及布点算法的复杂网络可视化

如2.1所述，该软件基于igraph的c库创建并编辑复杂网络的逻辑结构，而复杂网络的可视化则是由MFC双缓冲技术及布点算法实现。

（1）双缓冲技术

对于windows而言，每一个设备都有一个内存中的设备描述表与之对应，而设备表述表的实质就是一个内存缓冲区。如果用传统的方式进行绘图，系统会先将图形绘制在设备描述表所对应的缓冲区中，随后由gdi自动将前述缓冲区的图像复制到显存中进行显示。由于复杂网络具有大量的节点及边，如果采用传统的绘图方式绘制复杂网络，则会产生屏幕闪烁的问题，究其原因是windows在绘制每帧图像时会先将绘制区域变白，从而导致相邻的两帧图像间产生巨大差异。

双缓冲绘图方式则是屏幕闪烁问题的一个良好的解决方案，相对于传统绘图而言，其需要建立2个缓冲区，一个是设备描述表的，另一个是与设备描述表相兼容的后备缓冲区。绘图步骤为：首先将图像绘制在后备缓冲区中，然后再将后备缓冲区中的图像复制到设备描述表中，最后由gdi自动地将设备描述表中的图像复制到显存中进行显示［10］。

（2）布点算法

此外，如果随机绘制复杂网络的大量节点会导致其许多关键信息被掩盖，如：关键节点等，同时也导致复杂网络的显示不具美感。

在各国学者已经提出的众多绘图算法中［11，12］，最著名的是 P.Eades提出的力导引算法 （FDA，Force－Directed Algorithm）以及由其发展而来的各种改进算法。如2.1所述，igraph是一款功能十分强大的软件包，其中也包含了KK及FR布点算法的API，但是由其API所得节点坐标是一个相对值，故该软件依据当前网络显示区域大小进行坐标换算，然后再绘制复杂网络。图3展示该软件创建的一个节点数为300的复杂网络在随机绘制 （左）、KK布点算法绘制 （中）及FR布点算法绘制 （右）时的情况。从中可以明显看出KK及FR布点算法绘制的复杂网络更具美感。

（3）复杂网络缩放显示

虽然KK和FR等布点算法可以较好地展示复杂网络的拓扑结构，但是随着网络节点数量的激增，还是会导致如图4左半部分所示的节点过于集中，不易观察复杂网络的情况。对此，该软件设计了网络缩放功能以展示节点过于密集的复杂网络的局部细节，如图4右半部分即放大8倍后的局部细节。反之，也可以缩小网络便于整体观察。

2.3 复杂网络相关统计参数计算

如前所述，复杂网络的统计性质对于仿真软件的功能设计至关重要，并且很多文献都对其给出了详细的解释及求解方法。该软件在综合考虑时空复杂度后，基于igraph实现了各种统计性质的求解API，表2列出了典型统计性质对应的API。

表2 统计参数API

求解复杂网络直径的示例代码如下：

＃include＜igraph.h＞

int main （void）

｛

igraph＿real＿t d；／／diameter

igraph＿t g；／／graph

igraph＿erdos＿renyi＿game （ ＆ g，IGRAPH ＿ERDOS＿RENYI＿GNP，500，6.0／500，IGRAPH ＿UNDIRECTED，IGRAPH＿NO＿LOOPS）；

diameter（g， ＆ d）；

printf（"Diameter of a random graph with average degree 6：%f＼n"，（double）d）；

igraph＿destroy （ ＆ g）；

return 0；

｝

2.4 复杂网络文件读写

为了便于利用已有的复杂网络数据，并保存研究中的复杂网络数据，该软件实现了多种复杂网络文件的读写，如：graphML、GML及pajek，研究人员可依据使用习惯进行选择。该软件提供了readFile（graph，format）及writeFile（graph，format）2个方法分别进行文件的读取及写入，其中format用于指示使用哪种格式进行文件读写。

graphML相对于另外2种格式而言，具有独特的优势。首先，它是一种综合的且简单易用的图的文件格式。其次，它包含一种用于描述图的各种结构属性的核心语言以及一种用于添加应用特定数据的扩展机制。此外，graphML没有使用自定义的语法，而是基于XML，故很适用于图的许多服务，如：创建，保存及处理等。

graphML的其他特性如下：

支持有向、无向及混合图；

轻量级的解析器及应用特定的属性数据；

对拓展数据的引用；

数据结构层次分明。

为了直观展示graphML的文件结构及易用性，本文以一个11节点，12条边的无向图为例，最终显示效果如图5所示。

图5 graphML格式示例

graphML文件代码如下：

＜？xml version＝"1.0"encoding＝"UTF－8"？＞

＜graphml xmlns＝"http：／／graphml.graphdrawing.o rg／xmlns" xmlns：xsi＝"http：／／www.w3.org／2001／XMLSchema－instance"

xsi：schemaLocation＝"http：／／graphml.graphdrawin g.org／xmlns

http：／／graphml.graphdrawing.org／xmlns／1.0／graph ml.xsd"＞

＜graph id＝"G"edgedefault＝"undirected"＞

＜node id＝"n0"／＞

＜node id＝"n1"／＞

＜node id＝"n2"／＞

＜node id＝"n3"／＞

＜node id＝"n4"／＞

＜node id＝"n5"／＞

＜node id＝"n6"／＞

＜node id＝"n7"／＞

＜node id＝"n8"／＞

＜node id＝"n9"／＞

＜node id＝"n10"／＞

＜edge source＝"n0"target＝"n2"／＞

＜edge source＝"n1"target＝"n2"／＞

＜edge source＝"n2"target＝"n3"／＞

＜edge source＝"n3"target＝"n5"／＞

＜edge source＝"n3"target＝"n4"／＞

＜edge source＝"n4"target＝"n6"／＞

＜edge source＝"n6"target＝"n5"／＞

＜edge source＝"n5"target＝"n7"／＞

＜edge source＝"n6"target＝"n8"／＞

＜edge source＝"n8"target＝"n7"／＞

＜edge source＝"n8"target＝"n9"／＞

＜edge source＝"n8"target＝"n10"／＞

＜／graph＞

＜／graphml＞

3 结束语

本文介绍了一种复杂网络仿真软件。该软件基于igraph以多种形式创建给定类型和参数的复杂网络，利用经典算法计算复杂网络的重要统计参数，并结合双缓冲技术及布点算法实现了复杂网络的可视化。目前，该软件已经运用于复杂网络的相关研究，如：基于中介中心性的网络负载均衡等。此外，文献 ［13］也利用该软件进行了加权复杂网络的聚类研究。实验结果表明，该软件可以很好地为复杂网络的相关研究提供有效支持。

［1］Borgatti，Stephen P.Network analysis in the social sciences［J］.Science，2009，323 （5916）：892－895.

［2］YANG Jianmei.Comparison of complex network and social network paradigm ［J］.System Engineering Theory and Practice，2010，30 （11）：2046－2055 （in Chinese）.［杨建梅.复杂网络与社会网络研究范式的比较 ［J］.系统工程理论与实践，2010，30 （11）：2046－2055.］

［3］HE Yu，ZHAO Hongli，YANG Haitao，et al.A survey of complex network evolution ［J］.Journal of Equipment Command and Technology，2011，22 （1）：120－125 （in Chinese）.［何宇，赵洪利，杨海涛，等.复杂网络演化研究综述 ［J］.装备指挥技术学院学报，2011，22 （1）：120－125.］

［4］LV Linyuan，LU Jun’an，ZHANG Zike，et al.Observation of complex network ［J］.Complex Systems and Complexity Science，2010，7 （2－3）：173－186 （in Chinese）.［吕琳媛，陆君安，张子柯，等.复杂网络观察 ［J］.复杂系统与复杂性科学，2010，7 （2－3）：173－186.］

［5］Wang Anjing.Network virtualization：Technologies，perspectives and frontiers ［J］.Journal of Lightwave Technology，2013，31 （4）：523－537.

［6］TIAN Liang.Statistical properties of complex networks and the dynamic analysis ［D］.Nanjing：Nanjing University of Aeronautics and Astronautics，2012 （in Chinese）.［田亮.复杂网络的统计性质及其上动力学分析 ［D］.南京航空航天大学，2012.］

［7］XIE WH.The study on degree distribution property of complex network based on cooperative communication ［J］.Journal of Electronics （China），2010，27 （2）：224－229.

［8］HUANG Biao.Complex network theory and its application［D］.Hefei：Anhui Agricultural University，2011 （in Chinese）.［黄标.复杂网络理论研究及其应用 ［D］.合肥：安徽农业大学，2011.］

［9］Barabási，Albert－László.Scale－free networks：A decade and beyond ［J］.Science，2009，325 （5939）：412－413.

［10］JIANG Jianguo，WEN Shaoying，ZHANG Ruinan.Flicker free drawing based on the GDI and double buffering ［J］.Computer Application，2012，32 （A2）：136－139 （in Chinese）.［江建国，温少营，张瑞楠.基于双缓冲技术的GDI＋无 闪 烁 绘 图 ［J］.计 算 机 应 用，2012，32 （A2）：136－139.］

［11］ZHOU Yan，LIU Yabing，WANG Xiaofan.A complex network visualization platform based on hierarchical structure of community ［J］.Journal of Shanghai Jiaotong University，2010，44 （3）：332－335 （in Chinese）.［周炎，刘亚冰，汪小帆.一种基于层次化社团结构的复杂网络可视化平台 ［J］.上海交通大学学报，2010，44 （3）：332－335.］

［12］ZHU Zhiliang，LIN Sen，CUI Kun，et al.Network topology layout algorithm based on community detection of complex networks［J］.Journal of Computer Aided Design and Computer Graphics，2011，23 （11）：1808－1815 （in Chinese）.［朱志良，林森，崔坤，等.基于复杂网络社区划分的网络拓扑结构可视化布局算法 ［J］.计算机辅助设计与图形学学报，2011，23 （11）：1808－1815.］

［13］GUO Tao，ZHANG Kun，GUO Wenjun，et al.Improved method of weighted complex network clustering ［J］.Computer Science，2012，39 （6A）：99－102 （in Chinese）.［郭陶，张琨，郭文娟，等.一种改进的加权复杂网络聚类方法［J］.计算机科学，2012，39 （6A）：99－102.］