复杂网络可视化研究综述

复杂网络可视化研究综述*

)

王 柏 吴 巍 徐超群 吴 斌

(北京邮电大学计算机科学与技术学院 通信软件工程中心 北京100876)

摘 要 当今万维网、社会关系网等复杂网络的规模迅速发展,一方面导致人们很难用数字和表格来对这些复杂网络进行全局规划和管理,另一方面复杂网络包含了非常丰富的信息资源但都难于被发现。可视化技术提供了有效的方法来理解复杂网络的结构并从中挖掘有效信息。本文全面介绍了复杂网络可视化技术的研究进展,讨论了可视化布点算法和压缩算法,并介绍了若干具有代表性的复杂网络可视化工具、列举了复杂网络可视化技术在相关领域的应用。

关键词 复杂网络,可视化,信息可视化,布点算法

ASurveyonVisualizationofComplexNetwork

WANGBai WUWei XUChao-Qun WUBin

(TelecommunicationSoftwareEngineeringGroup,SchoolofComputerScienceandTechnology,BeijingUniversityofPostsand

Telecommunications,Beijing100876)

Abstract Manyrea-lworlddomainscanberepresentedascomplexnetworks.Visualdepictionsofnetworks,whichex-ploithumanvisualprocessing,aremorepronetocognitionofthestructureofsuchcomplexnetworksthanthecompu-tationalrepresentation.ManycharacteristicsoftheComplexNetworkalgorithmsareanalyzedfirstly.Thenthepaper

brieflyintroducesthegeneralandspecialtoolsfortheVisualization.Thirdly,theapplicationsofvisualizationtechnolo-gyinseveralfieldsarepresented.Finally,thenewproblemsandchallengeswhicharisefromcurrentresearcharedis-cussedandsomesuggestionsforfutureresearchworkareputforward.

Keywords Complexnetwork,Visualization,Informationvisualization,Layoutalgorithm

的信息[4]。作为信息可视化的一个重要分支,复杂网络可视

化的研究从上世纪90年代中期开始,在GraphDrawing,In-foVis(IEEESymposiumonInformationVisualization),IV(In-ternationalConferenceonInformationVisualization)等重要国际会议中都成为一个越来越受关注的议题,引起了各国学者的高度重视。

复杂网络可视化研究涉及复杂系统、图论、统计学、数据挖掘、信息可视化以及人机交互等多个领域。其中受关注程度最多的一个问题是可视化算法,包括布点算法和可视化压缩算法。布点算法中最重要的一个分支是P.Eades提出的力导引(FDA,Force-DirectedAlgorithm)算法[5],而可视化压缩算法的提出和发展则使得可视化技术用于复杂网络成为可能。本文详细地阐述了复杂网络可视化算法的演变历程,以及这些算法是如何优化从而达到美学标准和尽可能展现清晰的结果。此外,各国学者也在不断探索如何搭起网络复杂可视化理论和实际应用的桥梁。目前看来,随着可视化算法的不断发展,各种复杂网络可视化工具和系统也不断涌现出来。无论是编程语言的API、各种通用的可视化工具,还是专注于单一应用领域的可视化系统都层出不穷,这也从侧面反映了复杂网络可视化技术所受到的高度关注和广阔的发展前景。

本文其他部分组织如下:第2节将介绍网络可视化的相关技术,包括可视化算法和可视化工具,算法方面将介绍经典

1 引言

近年来,信息系统如万维网[1]、电信网、移动通讯网络迅猛发展,可获得社会关系网络数据的规模逐渐增大,以致人们无法通过传统的技术和方法来管理和运作这些复杂网络[2]。人们通过对Web网络、社会关系网络、生物网络等的研究,发现了这些网络都具有某些共同的性质,这些性质包括:(1)整体稀疏,局部密集;(2)顶点度数服从幂率分布,也被引申为无尺度特性[2];(3)整体分布具有高聚集度、低平均最短路径(平均最短路径=O(loglogN)),具有小世界特性[3]。具有以上性质的网络被称为复杂网络。

复杂网络的结构非常复杂,如果仅用数据表格或文字的形式来表示网络,理解起来非常困难,导致网络所包含的信息无从体现。将复杂网络方便、直观地表示出来的最好方法是将其进行可视化。科学计算可视化的思想是上个世纪80年代美国科学基金会(NSF)提出的。当时在科学计算中产生了大量数据,人们很难清楚知道这些数据所表示的含义以及数据之间的关系,于是提出了将它们以图形化的方式显示出来的可视化思想。复杂网络研究的兴起进一步促进了网络可视化技术的发展,同时对可视化技术提出了更高的要求。复杂网络可视化一方面可以通过精确的展示帮助人们认识网络的内部结构,另一方面可以帮助挖掘隐藏在网络内部的有价值

*)本课题得到国家自然科学基金(60402011)资助。王 柏 教授,博士生导师,主要研究方向为电信系统软件、分布计算技术;吴 巍 硕士研究生,主要研究方向为数据挖掘、复杂网络;徐超群 硕士研究生,主要研究方向为数据仓库与数据挖掘;吴 斌 副教授,主要研究方向为智能信息处理、数据挖掘、复杂网络。

#17#的布点算法和因复杂网络特殊性发展起来的可视化压缩算法,工具方面将介绍几种具有代表性的复杂网络可视化工具并对其进行对比。第3节将介绍复杂网络可视化技术的应用,分别探讨在信息检索、网络拓扑、社会关系网络以及其他相关领域内的应用。最后一节将总结复杂网络可视化的相关问题并对其未来发展方向进行展望。

遵循了胡克定律的偏微分方程,并以此来优化了顶点的布局。此外,KK算法还加入了非相邻节点间理想距离的概念:两个节点间的理想距离与它们之间的最短路径的长度成正比。在系统的最终稳定状态下,节点间的距离都将接近于它们的理想距离。

T.M.J.Fruchterman和E.M.Reingold在文[7]中提出了基于再次改进的弹性模型的FR算法。该算法遵循两个简单的原则:有边连接的节点应该互相靠近;节点间不能离得太近。虽然该算法的原则简单抽象,但得益于出色的模型选择,所以能够画出相当优美的图形。FR算法在Eades的经典算法基础上改进了力导引模型,建立在粒子物理理论的基础上,将无向图中的节点模拟成原子,通过模拟原子间的力场来计算节点间的位置关系。算法通过考虑原子间引力和斥力的互相作用,计算得到节点的速度和加速度,节点的运动规律类似原子或者行星间的运动,系统最终进入一种动态平衡状态。另外值得一提的是,FR算法还采用了网格变量(grid-variant)方法进行了优化:将布点区域分成若干网格,计算斥力时只考虑节点与相邻网格内的节点间的作用。若以k表示节点周围空白区域的理想半径,d表示节点间的距离,则斥力计算公式如下:

fr=

k2

u(2k-d)d

1,

ifx>0

2 复杂网络可视化技术

图的可视化算法研究有着相当长的发展历史,从最初严格遵循输入的布点算法到近年来很多带有压缩功能的复杂网络可视化算法,其间经历了漫长的发展历程,而这整个过程也是在各种实际应用的需求带动下不断进行的。本节将分别探讨忠实地描绘原始图结构的布点算法(也就是一般意义上的作图算法)和为适应大规模网络而诞生的可视化压缩算法,并介绍在这些可视化算法基础上开发出来的各种可视化工具。

2.1 布点算法

长期以来,各国学者已经提出了相当多的作图算法。文[6]是一篇关于作图算法的相当全面的综述。从美学的角度来说,一般认为作图算法应尽量满足以下几个要求:整体布局对称性;避免边的交叉和弯曲;保持边长统一;节点分布均匀[7,8]。各种不同的算法会针对其中的一部分要素进行优化,最终目的是要让人们能够从生成的图形中更容易地发现图的结构特点、更快捷地获得最大的信息量。最著名的一种作图算法是由P.Eades提出的力导引算法(FDA,Force-DirectedAlgorithm)[5]以及发展出的各种改进算法。FDA不但易于理解和实现,而且能画出相当优美的图形布局,并充分展现出图的整体结构及其自同构特征,这些也是FDA被广泛采用的主要原因[9]。但是运算复杂度是FDA基础算法的一个缺点:每次循环都必须计算每对节点间的作用力关系,而总循环次数通常在N数量级,所以总的复杂度是O(N3)。因此许多FDA算法都在努力改善算法性能[10~13],而另一些的FDA算法则致力于通过引入不同的力学模型来使结果更加美观,在此方面有学者提出了将节点集间的连接性映射为它们之间的几何路径的力学模型,这使得高度连接的点集在图中被显示为高密度的区域[14]。下面我们通过重点追踪FDA的进化轨迹来探索作图算法的发展历程。

P.Eades于1984年提出的/弹性模型(Spring-EmbeddedModel)0(由于此模型以物理学中的/弹力0作为关注点,因此也称为力导引模型:Force-DirectedModel)在作图领域具有开创性的意义,并一直被沿用发展至今。其基本思想是将图看成一个顶点为钢环、边为弹簧的物理系统,系统被赋予某个初始状态以后,弹簧弹力的作用会导致钢环的移动,这种运动直到系统总能量减少到最小值时停止。但是,Eades在他的实现算法中并没有遵守弹性力学中的胡克定律,而是采用了自己建立的弹簧受力公式。此外,为了降低算法复杂度,Eades假设引力作用只存在于相邻两个节点间。

此后,T.Kamada和S.Kawai在文[15]中提出的KK算法改进了Eades的弹性模型。通过求系统总能量

n-1n1E=EEkij(|pi-pj|-lij)2

i=1j=i+12的最小值来确定节点位置,其中pi和pj表示节点vi和vj的位置,lij表示vi和vj间弹簧的初始长度,kij表示弹性系数。但不同于Eades的做法,Kamada和Kawai在他们的模型中

其中u(x)=

0,otherwise

随着对于复杂网络的研究日益深入,适用于复杂网络的

可视化算法研究大量开展起来,由D.S.Chan、K.S.Chua、C.Leckie和A.Parhar提出的ODL算法便是专门适用于幂律(power-law)网络的FDA算法[16]。与传统弹性模型算法不同的是,ODL算法采用了分级算法[12]的思想:首先通过划分点的聚类或者挑选重要的点集来生成一张节点较少的图作为初始状态,然后逐步添加其余的点到图中,最终形成完整的结果。只要保证最初第一级节点构成的图能够近似反映图的整体结构,那么后面全部节点的调整过程将会大大缩短。分级算法的模型降低了算法的复杂度,从而提高算法的效率,使其能够适用于大型的复杂网络。在效率比较实验中,ODL的执行速度明显地快于以往的各种弹性模型算法(表1为KK、FR、ODL3种FDA算法的效率对比结果,其中第一列为测试网络的名称,第二、三列分别为网络中节点和边的数量,后3列为各个算法以秒为单位的执行时间),而生成图形的整体美观效果也相当不错(图1)。

表1 几种FDA算法的性能比较

Network13hexBallCuboidGridPattern40StarTriangleHexwrapHeywoodHexTotal

|N|40203072401925332142

|E|523012777456934421358

KK0.660.280.272.691.210.1677.40.050.06204286.8

FR0.100.020.060.320.120.033.740.070.013.708.17

ODL0.060.010.030.160.050.011.480.050.021.483.35

#18#图1 几种FDA算法的结果展示

以上介绍的算法均为2D算法。从图1中我们也可以发现,在节点数达到某一数量以后,仅仅采用传统的平面2D图形已经不足以使人们通过肉眼就能认清图的局部细节,这也导致人们无法从复杂的图形中顺利地获得有价值的信息。而如果采用3D布局是否能够帮助人们更好地理解与操作图形呢?关于2D、3D图形采用的方式和场合,一直存在争论。C.Ware认为,从更好地管理和解释网络的角度出发,可以考虑采用2.5D的设计理念[18]:在3D空间选择性地挑选若干平面作为布局平面,节点只存在于这些特定的平面上,同时在这些平面上的布局算法仍然可以采用经典的2D布局算法。经验表明,2.5D的图形表示方法是对于人类视觉系统的有限3D理解能力的最大限度利用。A.Ahmed等人提出了一种适用于无尺度网络的2.5D可视化方法[4],他们通过将各种不同重要级别的节点置于相应的平面,并在各个平面上采用了改进的FastFDA算法[20],实现了一种新颖的可视化方法,并获得了良好的视觉效果。

除了以上介绍的主流FDA系列算法以外,各国学者针对复杂网络可视化的特殊性也提出了一些经过改进的方法[12,21~26],包括快速多级力导引、嵌入、光谱图、几何聚类、伸缩等方法。国内方面,武汉大学的黄竞伟等学者也先后提出了几种布点算法。在文[8]中黄竞伟等人将一般无向图的画图问题转化为函数优化问题,用遗传算法求目标函数的最优解的近似值,从而得到无向图自动画图算法的一个一般框架。该方法的特点是:不同的画图算法的框架都一样,所不同的只是反映无向图画图问题的美观标准的目标函数,其优点在于:算法统一、方法简单、容易实现、便于修改,并且易于并行化,可以直接用来画非连通图。在文[27]中张清国等人提出了一种基于D.M.P.平面性判定算法的新的平面图画图算法,与其它的算法相比,该算法具有方法简单、易于实现的优点。

2.2 可视化压缩算法

随着网络规模的不断增大,特别是具有幂率分布和小世界特性的复杂网络出现以后,单纯地应用以往经典的布点算法来作图,已经无法满足实际应用中可视化展现复杂网络的需要。其遇到的困难主要体现在性能和可阅读性两方面:一方面,大数据量的节点位置调整耗费过多的计算资源;另一方面,将所有节点展现在结果图上,使人根本无法从中获得任何有效的知识。图2左侧是一张3076个节点组成的未经压缩的INET[17]网络结构图。

为了更好地帮助人们理解复杂网络的整体拓扑结构,可视化压缩算法应运而生。Feder和Motwani在将大规模图形转化为小规模图形的过程中,保留了原始图形的一些关键属性(如连接性等)。以这种方式压缩的图形适合用来更高效地

图2 压缩前后的INET网络结构

同样来自AT&TResearch的另一个由Koren等人组成的团队开发了一个大型网络可视化工具TopFish[31]。TopFish的布点算法由外部提供,因而不依赖于特定算法。当载入布局以后,TopFish能够按用户设置的焦点对其周围的局部进行放大,进而观察焦点周围的细节。TopFish同时能够生成经过压缩的整体结构图,其压缩方式包括根据拓扑距离或几何距离合并节点以及合并聚类等。而观察TopFish生成结果的焦点位置和焦距也都是可变的,同时TopFish还具有运算迅速的特点,使之非常适合用于大规模网络的交互式访问。图3为TopFish生成的Internet路由结构,左侧为整个Internet的路由结构,右侧为改变焦距后观察到的Inter-net路由细节。

计算一些图形变量,如两点间的最短路径[29]。Adler和Mitzenmacher等人也为搜索引擎的存储和访问实现了WebGraph的一种无损压缩[30]。AT&TResearch的Gilbert和Levchenko也提出了他们的可视化压缩算法[28],分别根据节点的重要程序和相似性定义了他们的压缩算法,这些算法作为开源的图形可视化项目Graphviz的一部分,为后者的成功作出了很大贡献。图2右侧是经过这些算法压缩后的INET网络结构。

图3 TopFish展示的Internet路由结构

2.3 可视化工具

网络可视化工具种类、数量繁多,我们按照通用性将其分为3类(按通用性从高到低),分别是:网络可视化的框架以及类库、通用的网络可视化工具、专用的网络可视化工具。本节

#19#接下来将介绍前两类工具,而专用的网络可视化工具将在第3节相关应用中陆续提及。

网络可视化的框架及类库通用性最高,使用者能够根据自己的需求,灵活地利用它们来生成所需要的图形,或基于这些框架及类库来编写含有更多定制功能的作图软件。这里介绍两个网络可视化框架及类库:AGD1和JUNG2。AGD是一个基于C++作图算法类库,它支持几乎所有现有的二维作图算法,同时集成了实现新算法的工具。AGD具有面向对象、模块化、可扩展性强等特点,它基于LEDA和Abacus。JUNG是一个基于Java的免费开源类库,它提供了一种通用的、可扩展的方式来处理、分析以及展现网络结构的数据。与其他第三方Java类库一样,基于JUNG的程序能够以JavaAPI的形式来方便地使用它提供的功能。但是,因为Java语言在内存使用效率上的先天不足,JUNG对于主机内存的要求相当高。

表2 AGD与JUNG的对比

AGD

语言支持图形种类

效率免费开源提供框架支持图的输入方式支持的算法数量支持算法扩展

C

直线图、直角边图、折线图、曲线图等

高

是否否编程、GraphML

少是

++

和操作对象。当前,Piccolo包括Piccolo.Java、Piccolo.NET

和PocketPiccolo.NET3个版本,分别基于Java.NETFrame-work和.NETCompactFramework编写。

UCINET6是一款功能全面的复杂网络分析工具,主要用以分析社群网络,它包含了相当丰富的网络分析工具,是社群网络分析领域最著名同时也最为常用的一款网络分析软件包。相对于易用性来说,UCINET更注重的是速度(builtforspeed,notforcomfort)。UCINET支持多种数据输入输出方式,而与其他可视化工具(Pajek、Mage、NetDraw等)的集成也是它的一大特点。

VxInsight是适用于大型数据库的关联性可视化挖掘工具。与其他数据分析和挖掘工具只能通过访问的数据元素得到关于数据库的浅层信息不同,VxInsight能够发现数据间的隐藏信息和关系,能够帮助或指导人们发现海量数据中的处于战略性地位的重要关联关系和模式,使其成为一款重要的可视化知识管理工具。

其他比较著名的作图工具还包括GDToolkit7,InfoVis

JUNGJava直线图低是是是

编程、Pajek文件、

GraphML

多否

Toolkit8等。每种可视化工具根据其不同的目标相应具有一些自身的特点,这些特点主要包括:(1)交互性:用户能够利用工具提供的丰富的交互式功能对可视化结果进行访问,增加了可视化结果所携带的信息量。(2)性:能够对可视化结果中的元素对应的对象或事件的多个维度的属性进行访问,同时可以按其每一维的标准,将其分类、排序、组合和显示。(3)可变焦性:许多工具都具有过滤、变焦等功能,能够方便地查看网络的整体结构,也能对局部细节进行探索。

值得一提的是,尽管已存在许多相关的可视化工具,然而出于种种原因,其中许多工具属于美国出口软件,尚不让我国进口(如VxInsight9)。这从一个侧面反映复杂网络可视化技术的重要性。同时我们也应该认识到,开展我们自己的可视化算法和工具研究是必需的。

网络可视化工具中数量最多的一类是通用的网络可视化工具,它们的特点是:功能丰富、适用性强、并不局限于特定的

使用目的。这里介绍其中比较著名的几款工具。

Graphviz3是一款来自AT&TResearch的开源作图工具,它支持多种作图算法,并同时支持Web界面和交互式图形界面,它还拥有一系列的辅助工具和类库。Graphviz利用一种简单的文本语言来描述图形结构,并能够将生成的图形保存成各种格式,例如:网页中的普通格式或SVG格式图片、PDF中的Postscript,也可以显示在交互式图形浏览器中。Graphviz还支持一种表示图的XML语言)))GXL。由GlenLow开发的MacOSX版Graphviz获得了2004苹果设计大奖(AppleDesignAwards)。

Pajek4(斯洛文尼亚语中/蜘蛛0之意)是一款免费的大型网络分析工具。为了克服一般网络分析工具只能分析中等网络的瓶颈,Pajek具有以下特点:支持将大型网络递归分解成经典算法能够适用的小型网络;提供强大的可视化工具;实现一系列高性能的大型网络分析算法。

来自Maryland大学的作图工具Piccolo5带有特殊的可缩放用户界面(ZUI,ZoomableUserInterface),用户通过ZUI能够自由地对图形进行缩放,以便观察细节或者浏览全局。Piccolo采用了类似3D环境的/scene-graph0模型来层次化地组织对象和视图,使得开发者能够通过更有效的方式来管理

1

3 在相关领域的应用

3.1 可视化信息检索

传统的平板式目录搜索已经越来越无法满足人们从日益增长的庞大网络中挖掘知识的需要,已有不少学者开始尝试将可视化技术融入信息检索过程中。可视化搜索作为一个近年来备受关注的突破点,极有可能为信息检索领域带来一次深刻的变革。

TGGB10(TouchGraphGoogleBrowser)是一个新的可视化搜索工具,从名字可以看出它是基于Google搜索引擎来实现的。TGGB能够根据用户输入的任何一个URL地址进行Google搜索,并将搜索结果以图的形式可视化地展现给用户。这种搜索方式是对Google常规目录形式搜索的一种改进,用户从结果图中可以看到与输入URL相关的一些网站,而这些网站间原本隐藏的相互关系也被一目了然地展现出来,从结果图的整体布局也能够了解到某个网站在整个互联网中所处的地位。应该说,可视化搜索是搜索领域在近几年一个值得关注的发展点,随着微机性能的进一步提升,可视化搜索的全新体验并不再是遥不可及的。

http://www.ads.tuwien.ac.at/AGD/;2http://jung.sourceforge.net/;3http://www.graphviz.org/;4http://vlado.fmf.un-ilj.si/pub/net-works/pajek/;5http://www.cs.umd.edu/hcil/piccolo/;6http://www.analytictech.com/ucinet.htm;7http://www.dia.uniroma3.it/~gdt/;8http://ivtk.sourceforge.net/;9http://www.cs.sandia.gov/projects/VxInsight.html;10http://www.touchgraph.com/

#20#WhatsOnWeb11是一个互联网元搜索聚类引擎,它将用户的查询请求发送给若干个互联网搜索引擎(如Google、Yahoo等),在返回的URL结果集中选择具有代表性子集并将它们分成聚类,最终以分层次的可视化目录模型展现给用户。它使用户不但能够体验到可视化搜索带来的便利,同时能让用户从不同的层次去把握网站间的联系。

图4是北京邮电大学研究小组正在探索开发的一种基于科研合作网分析的可视化搜索工具,应用于国内大型文献内容提供企业。工具目的是在目前目录式检索前端增加可视化的图形检索界面,使用户对检索领域从研究群体、研究动态等方面有一个更直观清晰的整体了解,在此基础上进入更详细的文献检索;例如通过研究方向的复杂网络演化过程展示,能够了解前沿技术研究热点及演进过程和未来的研究方向。

络[37]。可视化工具Vizster[38]是一款专门用来实现社会关系网络可视化的工具,它通过对著名的朋友关系网络Friend-ster12进行可视化实现了朋友关系的在线探索。同时它能给终端用户提供一个清晰的网络结构图。借助可视化图形,可以推断出社会网络成员在不远将来的联系情况[39]。实验证明,通过网络可视化得出来的结果和实际情况相差无几。同样,可视化科研合作网可使用户根据搜索到的科研合作情况来了解和掌握各个国家和地区的科研重点和趋势。此外,根据网上社区的个体关系,即时通讯群体之间的通讯情况,博客群体间的链接结构,电子邮件之间的接受、发送次数等各个复杂网络可视化图,我们可以从中了解到个体的生活、行为、心理、消费状况等等。通过对电话用户呼叫图的可视化,可以直观地分析用户的通话模式,获得客户深层次的使用信息,结合客户基本属性分析,可以掌握客户更全面的信息,用于指导电信客户市场营销和决策,如依据挖掘得到的具有商业决策价值的用户行为模式,制定合理的资费方式,甚至发现和分析欺诈行为。打击犯罪是可视化技术的另一重要应用,通过可视化社会关系网络,能够分析出犯罪模式和帮派活动,并通过对犯罪活动的分布和频率信息的分析,主动地抑制与打击犯罪活动[40]。

3.4 在其他领域的应用

在生物学里,利用复杂网络可视化技术来分析蛋白质之间的交互网络、基因网络已经成为一种重要的研究方法[41]。在可视化图形中,用各种颜色的不同大小的圆表示基因,边则表示基因之间的关系,研究人员可以从中识别出具有生物学

图4 科研合作网的可视化搜索

3.2 网络拓扑可视化

Internet作为当今人类社会信息化的标志,其规模正以指数速度高速地增长。Internet的安全性、健壮性成了一个关键问题[46]。因特网上面有成千上万台服务器,服务器之间又可能存在众多路径。尽管对特定的任务而言,通过观查表格和统计数字,有可能了解网络流量模式、使用量高峰和低峰以及节点之间的备用路径,但使用视觉表示法却可以大大简化这项复杂工作。可视化技术与数据挖掘技术相结合[32],研究人员只要比较不同时间段的视图,就很容易知道流量增长趋势和模式,查出网络中表明流量变化异常的环节,来更好地对网络进行管理[33]。如美国摩根大学开发的可视化工具NI-VA用来实时发现网络故障。

无线通信已经在全球范围得到了迅猛发展,采用无线手段提供数据业务的应用成为新的通信热点。无线网络给用户随时随地访问网络提供了可能,这就决定了用户对无线网络的访问是间断、零星的,从而导致了无信号或者受到其他设备的干扰的可能情况。通过可视化无线网络,网络管理员可以清楚地掌握无线网络的覆盖率,用来预测网络的流量和信号的强弱,并且用来克服环境、高价和低流量等所带来的影响[35],能够使用户尽可能地正常使用网络。根据可视化的电话网话务量特性,还可以分析网络结构对话务量的影响。此外,IDS(入侵检测系统)能够帮助网络系统快速发现攻击的发生,它提升了系统管理员的安全管理能力[36]。

3.3 社会关系网络可视化

复杂网络可视化技术也常被应用于分析社会关系网

11

[34]

意义的行为模式,找出相关的数据群。通过蛋白质之间的可视化交互网络,可以找到由多基因所致疾病的候选基因,可以提取出群体组织,预测蛋白质合成中DNA的绑定等等[42],如以色列特拉维夫大学(Te-lAvivUniversity)等开发出EX-PANDER(EXPressionANalyzerandDisplayER)[43]。在生物工艺学,可视化网络技术作为一个重要的技术用于发现、分析

由基因所致的新陈代谢中出现的症状,然后用基因疗法医治。在交通网络中,司机可以实时地根据可视化的交通网来来选择通路,交通管理也可以通过可视化交通旅游网、交通网来进行管理,并且加强网络瓶颈区域的防护。

结论和展望 在本文中,我们力图详尽地回顾了复杂网络可视化技术的发展历程及其相关的研究与应用。我们认为,可视化技术在复杂网络的研究过程中起到了巨大的推动作用,并使复杂网络的分析方式更加灵活和多样化。但是,在这一领域仍然存在许多有待解决的问题。下面我们将针对一些在该领域中值得关注的问题和发展趋势进行讨论。(1)布点算法效率的提升。这仍然是最受关注的一个问题,每年都有大量来自GD、InfoVis等各大会议的相关论文对此进行讨论。如何改进经典的布点算法使之适用于大规模网络是当前研究的一个重点。在传统FDA算法的O(N3)复杂度基础上,Barnes和Hut对其进行了优化,得到了O(N2logN)的结果[44,45]。此外,可视化算法经常用到的聚类计算的复杂度也从O(N2logN)提升到了O(N2)[46]。

(2)算法结果美观性的改善。正如文[47]中所指出的,人们在何时以及如何采用一个合适的能够改善客户端性能的算法方面缺乏经验。文[48]中做了一个有趣的实验,详细考察了当前被普遍认可的若干布局结果的美观性准则,结论是针

http://whatsonweb.diei.unipg.it/;12http://www.friendster.com/

#21#对某些准则的相关参数进行优化并没有对结果的美观性带来实质性的改变。因此,仍然需要寻找和定义更有效的美观性准则的相关参数。

(3)空间算法的提出与改进。虽然对于2D和3D布局算法的优劣仍存在争论,但是我们认为,突破传统平面算法的2.5D或3D算法对于复杂网络的可视化有着一些2D算法无可比拟的优势,特别是在多网络综合显示以及网络演化过程展示等场景的应用中[4]。因此我们有理由相信,立体化的空间布局算法在未来一段时间内将得到更大程度的发展。

(4)可视化压缩算法的发展。除了经典的布点算法以外,可视化压缩算法的相关研究已经开展起来。虽然文[28]已经给出了效果相当出色的可视化压缩算法,但是仍然留下一些问题有待解决:首先是寻找新的衡量标准来指导压缩过程,其次是算法复杂度过高导致的性能问题。此外,如何在压缩过程中保留最大的信息量与指导人们更有效地进行信息探索是一个在应用领域非常值得关注的问题。

(5)标准化。虽然图论作为一门学科已经经历了长时间的发展,经典的图结构也得到了广泛的认可和应用,但是计算机对于图的描述方式仍然没有统一的标准,各种工具一般仍然采用私有的或者小范围内共享的文件格式,这种情况使得在使用不同工具的过程中很难实现重用或者互操作,因此出台一种统一的图结构文件格式标准是非常有必要的。同时可以考虑将文件格式定义为标准XML结构的扩展语言,以实现最大的可复用性和性。GraphML[49]是在此方面上的一项非常有意义的工作,我们也十分期待GraphML能得到越来越多的工具的支持,并成为真正的事实标准。

(6)动态网络的展示。已有的可视化算法和工具大多用于显示已存在的静态网络结构,但静态网络结构无法确切描述现实中持续演变的真实网络,怎样实现网络动态演变过程的可视化也是一个非常值得关注的领域。动态网络可视化技术这一难题如果得到解决,对于展现网络的演化过程将具有重要意义,基于此技术能够帮助人们更有效地进行时变网络的特征分析和知识挖掘。

(7)资源占用问题。大量的资源占用仍然是阻碍复杂网络可视化工具大规模推广应用的一个重要原因,即使是基于现今流行的C/S或者B/S模型的应用,只要客户端存在交互式的需求,就仍然对客户端的硬件运算能力存在很大程度的依赖,如何能够更好地控制资源占用量是一个急需解决的问题。一方面,我们可以通过致力于改进现有的算法效率来提升可视化软件整体性能[20]。另一方面,我们可以在可视化过程中更多地引入层次化的概念[12],将网络的规模和运算的压力分担到不同的层面上,实现单一复杂问题/分而治之0的解决方案。而如何分层也是一个值得研究的问题,如是基于网络的静态几何量(如节点度数、边权值、节点中介度等)进行分层[28,50],还是结合数据挖掘领域的相关技术通过基于对网络结构特征的分析来进行层次划分(如基于频繁模式挖掘的分层[19])等。最后,我们也可以通过设计良好的可视化软件体系架构,来将更多的运算压力移至服务器端,从而达到改善客户端性能的目的。毕竟服务器的性能通过一些手段可以很容易地得到提升,而在Internet遍布世界各个角落的今天,我们很难提升所有客户端计算机的运算能力。相信一旦性能问题得到解决,大量基于复杂网络的可视化应用(如TGGB、WhatsOnWeb等可视化搜索)将在短期内大规模发展起来。

[18]

参考文献

1234

王晓宇,周傲英.万维网的链接结构分析及其应用综述.软件学报,2003,14(10):1768~1780BarabasiAL,BonabeauE.Scale-freenetworks.ScientificAmer-ican,2003,288:60~69

WattsDJ,StrogatzSH.Collectivedynamicsof.smallworld.networks.Nature,1998,393:440~442AhmedA,DywerT,HongSeok-Hee,etal.VisualisationandAnalysisofLargeandComplexScale-freeNetworks.In:EURO-GRAPHICS-IEEEVGTCSymposiumonVisualization,2005.1~8

EadesP.Aheuristicforgraphdrawing.CongressusNutnerant-i

unt,1984,42:149~160

BattistaGD,EadesP,TamassiaR,etal.AlgorithmsforDraw-ingGraphs:anAnnotatedBibliography.ComputationalGeome-try:TheoryandApplications,1994,4(5):235~282

FruchtermanTMJ,ReingoldEM.GraphDrawingbyForce-D-irectedPlacement.Software-PracticeandExperience,1991,21(11):1129~11

黄竞伟,康立山,陈毓屏.一个新的无向图画图算法.软件学报,2000,11(1):138~142

vanHamF,vanWijkJJ.InteractiveVisualizationofSmallWorldGraphs.In:ProceedingsoftheIEEESymposiumonInfor-mationVisualization(INFOVIS.04),Vol00,2004.199~206HarelD,KorenY.Afastmult-iscalemethodfordrawinglarge

graphs.In:GraphDrawing:8thInternationalSymposium(GD.00),2000.183~196

QuigleyA,EadesP.Graphdrawing,clustering,andvisualab-straction.In:JoeMarksJ,ed.Proc.8thIntSympGraphDraw-ing,SpringerLNCS1984,2000.197~210WalshawC.Amultilevelalgorithmforforce-directedgraphdraw-thing.In:MarksJ,ed.Proc.8IntSympGraphDrawing,Spring-er-Verlag,2000.171~182

GajerP,GoodrichM,KobourovS.Amult-idimensionalap-proachtoforce-directedlayoutsoflargegraphs.In:MarksJ,ed.

Proc.8thIntSymponGraphDrawing,Springer-Verlag,2000.211~221

NoackA.Anenergymodelforvisualgraphclustering.In:Proc.11thIntSymponGraphDrawing,Springer-Verlag,2003.425~436

KamadaT,KawaiS.AnAlgorithmforDrawingGeneralUnd-i

rectedGraphs.InformationProcessingLetters,19,31:7~15ChanD,ChuaK,LeckieC,etal.VisualisationofPower-LawNetworkTopologies.In:ProceedingsoftheEleventhIEEEIn-ternationalConferenceonNetworks(ICON2003),28September-1October2003,Sydney,Australia,2003.69~74WinickJ,JaminS.Inet-3.0:Internettopologygenerator:[TechnicalReport].CSE-TR-456-02.UniversityofMichigan,2002

WareC.Designingwitha21/2dattitude.InformationDesignJournal,2001,10(3):171~182

AgrawalR,ImielinskiT,SwamiA.Miningassociationrulesbe-tweensetsofitemsinlargedatabases(C).In:BunemanP,Jajo-diaS,eds.ProcoftheACMSIGMODConfonManagementofData(SIGMOD.93).NewYork:ACMPress,1993.207~216QuigleyA,EadesP.Fade:Graphdrawing,clustering,andvisu-alabstraction.In:ProceedingsofInternationalSymposiumonGraphDrawing(GD2000).vol1984.Springer,2000.197~210GajerP,GoodrichM,KobourovS.Amult-idimensionalap-proachtoforce-directeddrawingsoflargegraphs.In:Proceedings

ofInternationalSymposiumonGraphDrawing(GD2000).vol1984.Springer,2000.211~221

HarelD,KorenY.Graphdrawingbyhigh-dimensionalembed-ding.In:ProceedingsofInternationalSymposiumonGraphDrawing(GD2002).vol2528.Springer,2002.207~2191

KorenY,CarmelL,HarelD.Ace:Afastmultiscaleeigenvec-torscomputationfordrawinghugegraphs.In:ProceedingsoftheIEEESymposiumonInformationVisualisation,2002.137~144WilliamsM,MunznerT.Steerable,progressivemultidimension-alscaling.In:ProceedingsoftheIEEESymposiumonInforma-tionVisualisation,2004.57~

DukeD.Visualwebmining.In:Proceedingsofthe13thInterna-tionalWorldWideWebConfereneceonAlternateTrackPapers&Posters,2004.394~395

MorrisonA,ChalmersM.Improvinghybridmdswithpivot-basedsearching.In:ProceedingsoftheIEEESymposiumonIn-formationVisualisation,2003.85~90

张清国,黄竞伟.一个无向平面图的画图算法.小型微型计算机系统,2003,24(6):972~975

56710111213

141516

171819

2021

222324252627

#22#28GilbertAC,LevchenkoK.Compressingnetworkgraphs.

LINKKDD,2004

29FederT,MotwaniR.Cliquepartitions,graphcompressionand

speeding-upalgorithms.JournalofComputerAndSystemSc-iences,1995,51:261~272

30AdlerM,MitzenmacherM.Towardscompressingwebgraphs.

In:ProceedingsoftheIEEEDataCompressionConference,2001.203~212

31GansnerE,KorenY,NorthS.TopologicalFisheyeViewsfor

VisualizingLargeGraphs.IEEETransactionsonVisualizationandComputerGraphics,2005,11(4):457~46832TeohSoonTee,ZhangKe,TsengShih-Ming,etal.Combining

VisualandAutomatedDataMiningforNear-Rea-lTimeAnomalyDetectionandAnalysisinBGP.VizSEC/DMSEC.04,October29,2004

33ErbacherRF,WalkerKL,FinckeDA.IntrusionandmisuseDe-tectioninLarge-ScaleSystem.IEEEComputerGraphicsandAp-plications,2002,22(1):38~48

34NyarkoK,CapersT,ScottC,etal.NetworkIntrusionVisual-izationwithNIVA,anIntrusionDetectionVisualAnalyzerwith

HapticIntegration.In:Proceedingofthe10thSymp,(HAP-TICS.02),2002

35IshmaelJ,RaceNJP.Visawin:VisualizingaWirelessNetwork.

0-7803-8255-2/04IEEE,2004

36ErbacherRF,ChristensenK,SundbergA.DesigningVisualiza-tionCapabilitiesforIDSChallenges

37FreemanL.VisualizingSocialNetworks.JournalofSocialStruc-ture,2000(1)

38HeerJ,BoydD.Vizster:VisualiziingOnlineSocialNetworks,

200539Liben-NowellD,KleinbergJ.TheLinkPredictionProblemfor

SocialNetworks.In:ProceedingsoftheTwelfthAnnualACMInternationalConferenceonInformationandKnowledgeManage-ment(CIKM.03),November2003.556~559

40ChenHsinchun,AtabakhshH,TsengChunju,etal.Visualiza-tioninLawEnforcenment.CHI,Apr.2001eNetViz-GeneNetworkVisualization.http://genetviz.source-forge.net/,2005

42AhmadS,GromihaMM.PredictionofDNABindinginProteins

fromComposition,SequenceandStructure.GenomeInformatics,2002,13:308~30943SharanR,Maron-KatzA,ShamirR.CLICKandEXPANDER:a

systemforclusteringandvisualizinggeneexpressiondata.Bioin-formatics,2003,19(14)

44BarnesJE,HutP.Ahierarchicalo(nlogn)forcecalculational-gorithm.Nature,1986,324(4):446~449

45QuigleyA,EadesP.Graphdrawing,clustering,andvisualab-straction.In:MarksJ,ed.Proc.8thIntSympGraphDrawing,

SpringerLNCS1984,2000.197~210

46NewmanMEJ.Fastalgorithmfordetectingcommunitystruc-tureinnetworks.PhysRevE,2004(inpress)

47GhoniemM,FeketeJD,CastagliolaP.Acomparisonofthe

readabilityofgraphsusingnode-linkandmatrix-basedrepresenta-tions.In:INFOVIS.04:ProceedingsoftheIEEESymposiumonInformationVisualization(INFOVIS.04)(Washington,DC,USA),IEEEComputerSociety,2004.17~24

48PurchaseHC,CohenRF,JamesMI.Anexperimentalstudyof

thebasisforgraphdrawingalgorithms.JExpAlgorithmics,1997,2(4)

49BrandesU,EiglspergerM,HermanI,etal.GraphMLProgress

Report:StructuralLayerProposal.In:Proc.9thIntlSympGraphDrawing(GD.01),LNCS2265,Springer-Verlag,2002.501~512

50WuAY,MichaelG,HanJiawei.Miningscale-freenetworksu-singgeodesicclustering.KDD,2004.719~72429TremblayM,etal.TheMAJCArchitecture:AsynthesisofPar-allelismandScalability.IEEEMicro,2000,20(6):12~2530TremblayM,etal.MAJC-5200:AVLIWConvergentMPSOC.

In:MictoprocessorForum1999,1999

31KapilS.UltraSPARCGemini:DualCPUProcessor.inHot

Chips15.http://www.hotchips.org/archive/,2003

32JacobsonQ.UltraSPARCIVProcessors.In:MicroprocessorFo-rum2003,200333WongWA,BaerJ-L.ModifiedLRUPoliciesforImprovingSec-ondlevelcacheBehavior.In:6thInternationalSymposiumon

High-PerformanceComputerArchitecture,January2000.49~6034SrinivasanV.Hardwaresolutionstoreduceeffectivememoryac-cesstime:[PhDthesis].DepartmentofComputerScienceand

Engineering,UniversityofMichigan,200135WongWA,BaerJean-Loup,TheImpactofTimelinessforHard-ware-basedPrefetchingfromMainMemory:[TechnicalReport].

DepartmentofComputerScienceandEngineering,UniversityofWashington,2002

36MartyMR,BinghamJD,HillMD,etal.Improvingmultiple-CMPsystemsusingtokencoherence.High-PerformanceComput-erArchitecture,2005.HPCA-11.In:11thInternationalSympo-siumon,Feb.2005.328~339

37HennessyJL,PattersonDA.ComputerArchitecture:AQuan-titativeApproach.3nd.SanMateo:MorganKaufmannPublish-ers,2002

38HaoE,ChangP-Y,PattYN.TheEffectofSpeculativelyUpda-tingBranchHistoryonBranchPredictionAccuracy.In:Proc.

27thInt.lSymponMicroarchitecture(MICRO-27),Nov.199439HammondL,NayfehB,OlukotunK.Asingle-ChipMultipro-cessor.IEEEComputer,September1997,30(9):79~85

40HaungsM,SalleeP,FarrensM.Branchtransitionrate:Anew

metricforimprovedbranchclassificationanalysis.In:Proc.HP-CA,2000.241~25041HeL-iQiang,LiuZh-iYong.AnEffectiveInstructionFetchPol-i

cyforSimultaneousMultithreadedProcessors.In:Proceedingsofthe17thInternationalConferenceonHighPerformanceCompu-tingandGridinAsiaPacificRegion(HPCAsia.04),2004

42HennessyJL,PattersonDA.ComputerArchitecture-aQuant-i

tativeApproach.secondedition.MorganKaufmannPublishersInc,1996

43HeilT,SmithJ.SelectiveDualPathExecution:[TechnicalRe-port].ECEDepartment,UniversityofWiscosin-Madison.No-vember1996

44HammondBA,HubbertM,SiuMK,etal.TheStanfordHy-draCMP.IEEEMicro,2000,20(2):71~84

(上接第16页)

13KumarR,TullsenDM,RanganathanP,etal.Single-ISAHet-erogeneousMult-iCoreArchitecturesforMultithreadedWorkload

Performance.In:31stInternationalSymposiumonComputerAr-chitecture,June2004

14KumarR,FarkasK,JouppiNP,etal.Single-ISAHeterogene-ousMult-iCoreArchitectures:ThePotentialforProcessorPower

Reduction.In:36thInternationalSymposiumonMicroarchitec-ture,December2003

15ChandraD,GuoFei,KimS,etal.Predictinginter-threadcache

contentiononachipmult-iprocessorarchitecture.High-Perform-anceComputerArchitecture,2005.HPCA-11.In:11thInterna-tionalSymposiumon,Feb.2005.340~351

16AamodtTM,ChowP,HammarlundP,etal.HardwareSup-portforPrescientInstructionPrefetch.In:ProceedingsHigh

PerformanceComputerArchitecture,2004.HPCA-10.10thIn-ternationalSymposiumon,Feb.2004.84~84

18HilyS,SeznecA.Branchpredictionandsimultaneousmul-tithreading.In:ProceedingsofParallelArchitecturesandCompil-ationTechniques(PACT.96),Boston,October1996

19MatsuzakiT,TomiyasuH,AmamiyaM.BasicMechanismsof

ThreadControlforOn-Chip-MemoryMult-ithreadingProcessor.In:ProceedingsofWorkshoponMultithreadedExecution,Arch-i

tectureandCompilation,Austin,Texas,December2001

20黄光奇,周兴铭.单芯片多处理器的性能优势.计算机工程与科

学,2001,23(1):35~38

21袁俊立,高原,陈新,等.一种新的多线程实现技术.小型微型计算

机系统,1998,19(11):7~11

22赵荣彩,唐志敏.低功耗SMT体系结构研究.计算机工程与设计,

2002,23(8):7~12

23赵荣彩,唐志敏,张兆庆,等.编译指导的多线程低功耗技术研究.

计算机研究与发展,2002,39(12):1572~1579

24李瑛.同时多线程结构指令流特性及取指技术研究:[博士论文].

西北工业大学,2004

25胡伟武,唐志敏.龙芯1号处理器结构设计.计算机学报,2003,26

(4):385~396

26PeirJK,LaiSC,luSL.BloomFilteringcacheMissesforAccu-rateDataSpeculationandPrefetching.ICS.02,June22-26,2002,

NewYork,USA.ACM.1-58113-483-5,2002

27LiYingmin,BrooksD,HuZhigang,etal.Performance,Ener-gy,andThermalConsiderationsforSMTandCMPArchitec-tures.In:Proceedingsofthe11thInt.lSymposiumonHigh-Per-formanceComputerArchitecture,2005

28KallaR,SinharoyB,TendlerJ.IBMPOWER5chip:adua-lcore

multithreadedprocessor.IEEEMicro,2004,24(2):40~47

#23#