搜索
复杂网络仿真平台摘要复杂网络的概念已经在计算机、生物、物理以及社会科学等各个领域中得到广泛的应用。尽管复杂网络的类型举不胜举，但是所有的复杂网络都可以用共同的模型——图来描述。Pajek以网络图的模型为基础，以六种数据类型为形式，以其快速有效性和人性化的特点，为复杂网络的分析提供了一个仿真平台。它集成了一系列快速有效的算法用于分析复杂网络的拓扑结构，包括从局部的角度分析网络节点和边的性质、利用抽象化的手段分析网络的全局结构、实现各种类型网络图之间的相互转换以及随即图的生成等。Pajek利用一个三维的可视化界面，为用户提供了一系列可视化工具。允许用户通过手动或者自动的调节节点位置、旋转网络图等方法，从视觉的角度直观地分析网络模型。此外，Pajek中的宏文件允许用户将一系列常用的操作保存为一个文件，从而能够有效地满足各种类型用户的不同需求。本文将结合具体的实例，分章节讨论Pajek在分析复杂网络拓扑结构中的应用。关键词：复杂网络，可视化，抽象化，有向图，无向图，权值EMULATOROFCOMPLEXNETWORKABSTRACTTheideaofcomplexnetwork,withthousandsofverticesandlines,havebeenwidelyappliedinmanydifferentareas,includingcomputer,biology,physicsandsocialscience,tonamebutafew.Althoughthetypesofcomplexnetworksareinnumerable,allofthemcanbedescribedbyacommonmodel,whichisknownasgraph.Basedongraphsandusingsixdatastructures,Pajek,whichisveryefficientandhumanized,isaprogramdesignedfortheemulationofcomplexnetwork.Thebasicsetofefficientalgorithmsareimplementedinittoanalyzethetopologyofcomplexnetworks,includinganalysisofthelocalnatureofverticesandlines,abstractiontogetaglobalviewofnetwork,transformationbetweendifferenttypesofnetworks,generatingrandomnetworksandsoon.Pajekprovidetheuserwithsomepowerfulvisualizationtoolsonathree-dimensionedreferenceframe.Theusercanfurtherimprovethepicturemanuallyorautomaticallybymovingverticesorspin.Moreover,wecandefineanoftenusedsequenceofelementaryoperationsasamacroandrunitasasinglecommand.Usingsystemsofmacros,Pajekisadaptedtospecialgroupsofusers.Inthisarticle,withsometypicalexamples,themainapplicationsofPajekarediscussedtoanalysisthetopologyofcomplexnetworks.Keywords:complexnetwork,visualization,abstraction,directednetwork,undirectednetwork,weight目录1引言11.1复杂网络的基本概念以及研究历史11.2Pajek的产生背景22Pajek的主要特点32.1计算的快速性32.2可视化42.3抽象化43Pajek的数据结构63.1Network（网络）63.2Partition（分类）93.3Permutation（排序）93.4Cluster（类）103.5Hierarchy（层次）103.6Vector（向量）104利用Pajek分析复杂网络基本性质124.1度的计算124.2两点间的距离134.2.1两点间的最短路径134.2.2复杂网络的直径154.2.3K步之内的路径154.2.4复杂网络的测地矩阵（GeometricMatrices）154.3k近邻（k-neighbors）164.4聚类系数174.4.11---聚类系数17CC4.4.2---2近邻聚类系数192CC5利用Pajek分析复杂网络结构205.1复杂网络图的遍历205.1.1深度优先搜索遍历205.1.2广度优先搜索遍历215.2复杂网络图的核心(Core)215.3复杂网络图的连通分量(components)235.4复杂网络的关键路径246利用Pajek转换复杂网络266.1无向边与有向边的转换266.1.1有向边转换为无向边266.1.2无向边转换为有向边266.2改变复杂网络图的结构266.2.1添加节点266.2.2添加兄弟边（siblingedges）276.2.3删除边276.3复杂网络图的缩减276.42-模到1-模网络图的转换286.4.11-模与2-模复杂网络的概念286.4.2利用Pajek实现2-模到1-模复杂网络的转换306.4.3其他附属选项317利用Pajek生成复杂网络347.1生成复杂网络347.2生成ER随机网络357.3生成无尺度（scale-free）复杂网络358Pajek的可视化378.1复杂网络图的绘制378.1.1绘制复杂网络图378.1.2绘制不同类节点的复杂网络图378.1.3绘制不同大小节点的复杂网络图388.1.4绘制不同权值的边的复杂网络图388.2调整复杂网络图的布局388.3复杂网络图的旋转419Pajek中的宏429.1宏的作用429.2宏的定义429.3宏的使用429.4宏的应用实例4210结论441引言1.1复杂网络的基本概念以及研究历史近几年来，复杂网络的研究正处于蓬勃发展的阶段[1，2]，其思想已经充斥到科学和社会的每一个角落。复杂网络可以用来描述人与人之间的社会关系[3]，物种之间的捕食关系[4]，计算机之间的网络联接[5]，词与词之间的语义联系[6]，科学家之间的合作关系[7]，蛋白质之间的相互作用[8]，科研文章之间的引用关系[9]以及网页的链接结构[9]等等。总之，从因特网到万维网，从生物体的结构网络到动物之间的食物链，从人体的神经网络到社会关系网络等等，可以说，复杂网络，无处不在。复杂网络的研究正渗透到物理、生物甚至社会学科等各个领域，因而，复杂网络的定性和定量研究已经成为当今科学的一大主题。每一个系统中的复杂网络都有其自身的特殊性质，有其紧密联系在一起的独特现象，有其自身的演化机制，但是不同的复杂网络在其结构特征上都呈现出一定的共性[10]。研究复杂网络的共性，首先需要一种描述这种不同类型复杂网络的共同数学模型。复杂网络模型的研究，昀早可以追溯到十八世纪，由伟大的数学家欧拉建立。欧拉所研究的问题，就是起源于当时俄国的一个小镇，这个小镇中有一些河流，在此镇中一共建了7座桥，小镇的人希望找到一条行走路线，能够通过所有的桥，并且每座桥只能经过一次。当时人们反复尝试也没有找到这样的路线，昀后欧拉发现这样的路径是不存在的。他分析这个问题基本的手段，就是把这个问题用一个抽象的图来表示。具体做法即把这些河流分割开的四个陆地区域，每一个区域用一个结点来表示，而把桥梁当成连接这些结点的连线。这样一种图的表示方法，就演变成为表述复杂网络一种共同的模型。比如对Internet而言，每一个结点表示一个路由器，如果两个路由器之间直接通过光纤连接，则这两个节点就通过一条边相连。以人类社会关系网络而言，每一个人就可以看成一个结点，两个人如果是朋友关系，那么这两个人之间就有一条边直接相连。因此，尽管复杂网络的类型是千差万别的，但是它们都可以用共同的模型——图描述出来[11]。一般来说，图的分类有两种方法。根据图中的边是否具有方向性，可以将图分为有向图和无向图两种。实际上，当我们忽略边的方向的时候，或者反过来看认为任何一条边都是双向的时候，有向图就成为无向图。因此，关于无向图的所有性质都可以在有向图中研究。另外，根据图中是否考虑各条边的权重，可以将它分为有权图和无权图。同样地，如果将有权图的各边权值都设为1，有权图就称为无权图。因此，关于无权图的所有性质也可以在有权1图中研究。利用图对复杂网络建模后，可以看到其结构具有很多相同的共性。例如关于顶点度值、聚类系数、平均路径长度[12]的分析方法以及大量不同复杂网络中存在的相同的统计特征，再如随机去点与选择性攻击对复杂网络结构的影响及其分析方法[10]。研究复杂网络的几何性质，复杂网络的形成机制，复杂网络演化的统计规律，复杂网络上的模型性质，以及复杂网络的结构稳定性，并把它与具体系统结合起来就是复杂网络研究的中心内容。1.2Pajek的产生背景与一般计算机图的结构相比，复杂网络的复杂性昀主要表现在节点数目庞大，通常达到几千甚至几万个。比如，一个大型的家谱图，它的节点数（即人数）可以达到一万个。另外，一个高分子的结构图中，通常也包含几千个原子。因此，复杂网络的结构比一般的计算机图的结构要复杂得多。目前，虽然已经存在不少算法来对复杂网络的这种拓扑结构进行分析，但它们通常都是基于复杂网络的矩阵表达形式，因而非常耗时耗空间，它们仅仅适用于中等规模（即节点数为几百）的网络。因此，当务之急就是需要一种快速有效的软件来分析和仿真复杂网络。Pajek就是这样一种软件[13]。Pajek在斯拉夫语中表示的意思是“蜘蛛”。众所周知，蜘蛛是生物中的织网高手，它编织网络的能力令人叹为观止。而Pajek这个软件不仅为用户提供了一整套快速有效的用来分析复杂网络的算法，而且还提供了一个可视化的界面。让用户可以从视觉的角度更加直观地了解复杂网络的结构特性。接下来的几个章节，第二章简单介绍了Pajek功能的三个主要特点；第三章中初步介绍了Pajek的六种数据类型；第四章到第七章将结合复杂网络的拓扑结构特点详细分析Pajek的功能，并且给出具体的应用实例；第八章讨论了Pajek的可视化特点，从视觉的角度分析复杂网络图的结构；第九章介绍了Pajek中宏文件的应用。22Pajek的主要特点简单的说，Pajek的特点主要表现在三个方面。在本章的三小节中将一一简单介绍。2.1计算的快速性Pajek为用户提供了一整套快速有效的算法，可用于分析大型的（节点书数以万计的）复杂网络。众所周知，一个算法的复杂度主要表现时间复杂度和存储空间复杂度两个方面。随着存储技术的快速发展，空间复杂度已经不是非常重要的问题。相反地，当复杂网络的节点数目非常庞大时，计算机运算速度的快慢对于解决问题的时间来说已经无足轻重。此时，算法的时间复杂度就起着至关重要的作用。从表2_1[13]我们可以很直观地看出算法的时间复杂度对于计算速度的重要性。表2_1.算法的时间复杂度比较（Pentium/64M/90MHz）)(nT1,00010,000100,0001000,000ShuffleO)(n0.00s0.00s0.17s2.22sQuickSorO)log(nn0.00s0.015s0.40s5.14sHeapSort)log(nnO0.00s0.06s0.98s14.35sInsertionSortO)(2n0.07s7.50s12.5min20.83hoursXY)(3nO0.10s1.67min1.16day3.17years表1中列出的是5种不同算法的时间复杂度，及其在不同节点数时运算耗时的多少。由表中可见，当节点数只有1000