可视化技术及其在复杂网络上的研究与应用现状.doc

《可视化技术及其在复杂网络上的研究与应用现状.doc》由会员分享，可在线阅读，更多相关《可视化技术及其在复杂网络上的研究与应用现状.doc（7页珍藏版）》请在三一办公上搜索。

1、DOI: 10 3969 / j issn 1001-3824 2012 04 005可视化技术及其在复杂网络上的研究与应用现状耿文静，吴渝( 重庆邮电大学 网络智能研究所，重庆 400065)摘 要: 可视化技术是有效、直观表达数据的重要手段，目前因特网等复杂网络上的数据量逐渐增多，为可视化技术带来了新的挑战。概述了可视化算法的发展历程，从平面图、层次图、有向图、立体图这 4 个图形分类出发，介绍 了各自适用的可视化算法的发展情况。然后，以复杂网络为应用背景，从复杂网络拓扑结构、传播机理、入侵检测 三方面的应用研究进展，说明了可视化技术对复杂网络研究的推动作用。最后，对几种适用于复杂网络的使

2、用较 广泛的可视化工具进行了分析和对比。关键词: 可视化技术; 绘图算法; 复杂网络; 可视化工具中图分类号: TN92文献标识码: A文章编号: 1005-3824( 2012) 04-0027-07可视化是利用计算机图形学和图像处理技术，将0引言数据转换成图形或图像显示并进行交互处理的理论、方法和技术。根据可视化对象的不同，分为信息可视化、科学可视化和知识可视化等。可视化技术涉及计 算机图形学、计算机视觉、图像处理、计算机辅助设计 等多学科，应用领域十分广泛。由于它能够帮助人们 发现隐藏在数据、信息背后的许多重要问题，更好地 利用信息数据，并对其进行更高层次的分析，已经成 为近年来的研究热

3、点和难点。自 1946 年世界上第一台公认的计算机 ENIAC研制成功以来，人们利用计算机进行科学计算和数 据处理已有六十多年的历史。被动等待计算机的 输出数据并对之进行人工处理的方式，不仅不能及 时得到直观、形象的整体概念，更有可能丢失大量 的信息。近年来，随着人类研究领域的不断扩大和 深入，来自医学、卫星遥感、地质勘探、生物学、复杂 网络等领域的数据与日俱增，导致大量数据可视化 ( visualization) 成为迫切需要解决的问题。 计算机 性能的逐步提高以及图形图像处理算法的不断提 出，也使得直观、形象地显示海量数据信息并进行 交互式处理成为现实。以复杂网络领域为例，目前 网络种类越

4、来越多，结构越来越复杂，更多网络节 点以百万、亿万计数的网络不断涌现。Newman 将 复杂网络分为 4 类: 社交网络、信息网络( 如引文 网、万维网) 、科技网络( 如电力网、Internet) 和生物 网络( 如代谢途径、基因控制网络) 1。这些复杂的 网络结构如果仅用表格和文字来表示，只能造成理 解上的困难，而将复杂网络直观、生动、真实还原出 来的最佳方案就是对其进行可视化。1可视化算法的发展概述简单来看，可视化算法就是画图算法，是按照一定规则绘制具有特殊含义图形的特定算法。从目的这一角度，画图算法应该能够生成携带尽可能多数据 量的图形结构，帮助人们快速观察到数据的结构关 系、层次关系

5、和变化规律等内容，以获得尽可能多的 数据量。从美学角度，画图算法应满足对称性和均匀 性，避免过多的重叠和图形堆积。Battista 和 Eades 于1994 年公开发表了相对较完整的画图算法综述，是2可视化算法不断发展非常有价值的参考文献 。该文献中提到的多种画图算法随后被不断改进并提高 性能。其中最经典的算法是 Eades 所提出的力导引 算法( force-directed algorithm，FDA) 3。随后，由 Ka- mada 和 Kawai 提出的无向图和带权图的绘图算法收稿日期: 2012-07-10( KK 算法) 4，Fruchterman 和 Reingoid 改进的弹

6、性模型算法( FR 算法) 5，Chan 和 Chua 提出的基于层布局可视 化幂率网络结构的绘图算法( outdegree layout，ODL) 等均 是对 FDA 算法的改进。王柏和吴巍对以上 3 个算法进 行对比分析，认为 ODL 算法性能较好5。布局的多样性导致可视化算法种类繁多，针对 不同的领域有不同的分类方法。下文分别从平面图、层次图、有向图和立体图这 4 个图形分类出发，介绍各自适用的可视化算法及发展6。1. 1 平面图的可视化算法平面图的画图算法是基本算法，很多非平面图也 会先将之平面化，再使用平面图画图算法。经典平面 图的作图算法有直线作图法( straight-line

7、drawing) 、 正交网络作图法( orthogonal grid drawing) 、多线段作 图法( polyline drawing) 和线性时间作图法( linear time drawing) 这 4 类。悉尼大学的 Hong 和 Eades 在 linear time 算法基础上，提出了一种构建最大化均匀程度线 性平面图的线性时间算法。该算法的时间复杂度为 O( n) ，适用于单连通和双连通的平面图，具有一个输 入和自同构组、嵌入图形 2 个输出。图 1 为其绘制的 一种特殊情况，其中 a 为该算法所构建的 BC 树( 2 可 染色的树，且所有叶子顶点具有相同颜色) ，b 为根

8、据 BC 树所绘制的对称均匀的平面图。和 Horng 等提出了一种改进的动荡粒子群优化算法( modified turbulent particle swarm optimization，MTP- SO) 来解决平面图的着色问题8。图 2 运用 MPSO 算法解决四色问题的实例由于平面图的应用十分广泛，对于平面图的绘 制所提出的技术问题越来越多，如怎样实现在平面 图插入点、平面图的切割问题等。平面图切割技术 是计算机视觉领域所需要用到的平面图绘图技术， 其本质也是采用平面图作图算法，绘制机器所看到 的人物景象。波恩大学的 Schmidt 和 Toppe 等人提 出了一个基于平面图的快速图像切割

9、算法，对于图 像匹配和图像分割都很有帮助。图 3 是使用该算法 进行平面图匹配的一个实例，b 是用 N 个点建模的 形状 c1 和 c2 ，每一次匹配都是从( a，0 ) 到( a + N，N) 的一条路径; c 是对顶点辨识的过程; 符合最小切割的匹配过程是能量泛函的体现。图 3 平面图形匹配的实例1. 2层次图的可视化算法层次图是非传统的图像模型，它的特点是具有 分层结构。关于层次图的绘图算法有很多研究，例 如 Eades 和 Feng 等人提出用直线作图算法绘制层 次图的方法，把层次图分解为若干子图，计算子图图 1 单连通图绘制实例随着人们对视觉效果要求越来越高，加之数据 维度逐渐变大，

10、颜色在带来视觉感的同时还能够携 带一定的信息，所以很多学者对于平面图的着色算 法进行了研究。Cui 和 Qin 等人提出了一种改进的9。的绘制并采取一定绘制方式将它们连接在一起粒子群优化算法 ( modifiedparticle swarm optimiza-tion，Modified PSO ) 来解决平面图的着色问题7。针对原始的 PSO 方法不能直接用于离散问题，CUI 和 QIN 等将其改进成四进制 PSO 方法，把粒子在每 一维度上的运动限制在 0，1，2，3 共 4 个状态空间。 图 2 便是运用改进算法对中国地图进行四色着色的 实例。基于原始 PSO 算法的改进还有很多，如 Hs

11、uAbello 对把层次图和地图结合起来的层次图地图( hierarchical graph maps) 进行了分析，强调层次图 地图背后的主要作用并给出其定义和实例。图 4 是 层次图地图的实例10，a 表明了层次图地图的定 义，叶子节点是原始图形的点集，内部的点代表和 子图的连接关系; b 是美国 50 个州之间聚合的手机流量，使用层次地图方式所绘制，每一个州内包含一个由 50 个线段组成的特殊图形，用长度和颜色来 编码 流 量，长 且 深 的 片 段 表 明 高 流 量。 Alaa 和 Shukla 等提出了一种基于重心算法绘制层次图的有 效算法，该算法既提高了层对层技术( layer

12、by lay- er) 的效率，在减少边交叉方面也有显著成效。Alaa 在论文中专门对动态层次图画法进行了分析，并对 该绘图算法的指标进行了验证，提出了一种生成随 机层次图的方法。图 5 引入二次规划作图算法绘制的图形立体图的可视化算法1. 4目前研究比较广泛的立体图仍然是 3D 图形。Eades 和 Symvonis 等给出了三维正交直线算法13，用正交直线网格的方法绘制度为 6 以下的图形。Giacomo 和 Liotta 等人给出了在线性空间直线 3D 网格绘图法14。Dodo 考虑到力导引算法的简单易用 性，通过优化节点的分布、减少边的交叉，优化原算 法的布局，并将之适用于 3D 图形

13、的绘制，图 6 给出 了节点相连的简单图形绘制实例。图 4层次图地图1. 3有向图的可视化算法有向图包括有向无环图( 向上平面化算法、层次算法、优势算法等) 、普通有向图、基于特定领域应用的有向图等类。不同的有向图有其对应的画图算法。Groves 和 Michalewicz 等人在 1990 年提出将遗 传算法应用于有向图的绘制，随后不少学者相继对 其展开研究。高榕和李跃新将遗传算法运用于有 向无环图的绘制11，将画图问题转化为函数优化问 题，用遗传算法求解目标函数最优解，并通过实验 证明该算法具有一系列优点。Dwyer 和 Koren 等人 采用二次规划方法绘制有向图12，在遵循传统无向 图

14、画图算法的基础之上，在布局上引入层布局，在 视觉约定上采取横条纹划分层次等其它约束来绘 制有向图。图 5 是引入二次规划作图算法所绘制的 图形12，a 是一个两层布局的设计，b 是采用六条纹 分割的绘图，c 则是采用该算法绘制的带权有向图， 完整体现整个算法的设计思想。图 6 3D 绘图实例2复杂网络背景下可视化技术的应用现状对复杂网络节点及其关系的可视化，有助于理解网络的结构，寻找关键节点，或发现异常现象。因此，可视化算法经常被运用到复杂网络研究中。从 1998年 Watts 和 Strogatz15引入小世界( small-world) 网络 模型，到 1999 年 Barabsi 和 A

15、lbert16指出许多实际 复杂网络的连接度分布具有幂律形式，对于复杂网络 的研究逐渐深入。我国学者对复杂网络也进行了大量研究，如方锦清和汪小帆等17详细介绍了复杂网络的发展历史、统计学特征和网络模型等。随着网络节点规模的增大，网络的复杂度越来 越高，普通的可视化算法根本无法绘制出清晰表达 复杂网络结构和特性的图形。因此，可视化压缩算 法等适用于复杂网络的可视化算法被不断提出，也 使得可视化技术应用于复杂网络成为现实。下文 从复杂网络拓扑结构、传播机理、入侵检测 3 个方面 说明可视化技术对于复杂网络研究的推动作用。2. 1在网络拓扑结构研究中的应用网络可以被描述为很多点和边的集合，由于结构和

16、功能往往密不可分，如何准确描述点和边之间的关系非常重要。社会网络、生物网络、信息网络等网络 结构的可视化工作十分重要，这主要是因为解释结构 特性是复杂网络所研究的重要任务之一。对网络拓 扑结构可视化使用最早、也最广泛的是 FDA 算法。 随着网络规模的增大，对可视化技术的要求越来越 高。以社会网络为例，吴鹏和李思昆18考虑到 FDA 算法难以满足对社会网络深入分析和显示的需求，提 出了子群分析布局 SAL ( subgroup analysis layout) 算 法，从子群分析过程和算法布局过程 2 方面出发，实 现对社会网络结构分析的关键子群的分析。图7 是该算法绘制的子群18，图 8 是

17、恐怖组织信息平面 可视化结果18，中央位置是以基地组织为首的恐怖 组织子群，其右方是以哈马斯组织为首的恐怖组织子 群，一些小的恐怖组织则分布在四周。这 2 张图形将 恐怖组织的结构清晰表现出来。图 8 恐怖组织信息群2. 2在复杂网络传播机理研究中的应用不同类型网络上传播的信息是不一样的，如传染病病毒、计算机病毒、谣言等，但是对其传播机理的研究方法却是一致的。可视化有助于理解复杂网络上 信息传播过程这类动态特征。Saito 和 Kimura 等人提 出了一种可视化复杂网络信息传播的有效方法，把节 点分为目标节点和非目标节点，重点关注信息传播情 况，而不仅仅像 FDA 算法那样关注节点。国外还有

18、 针对 Twitter 上新闻转发情况所做的可视化产品，图 9 展示了 Twitter 上纽约时报新闻“Detained health work- ers denounce philippine government”在 2010 年 2 月 7 日 一天的转发情况，中间 12 条竖线是当日热点转播的新 闻，选中其中一条竖线，对其转播的关系就被激活，可 以通过继续推进来观察转播情况。整个可视化效果是 跟随用户的选择而时刻改变的。图 7 恐怖组织信息子群图 9 Twitter 新闻的转发分布图利用可视化技术研究信息传播机制具有一定的难度，这主要是因为信息传播是动态的，而可视 化算法大部分是静态算

19、法。如何动态可视化数据 的变化，也是近年来可视化领域的研究重点。3. 1网络可视化软件包 / 框架Igraph20是用来作图的免费软件包，包括经典作图算法和近几年新的网络可视化算法，可处理无向图和有向图。它由 C 语言编写，可运用到 C / C + + 项目 中，也可支持 R，Python，Ruby 语言。LaNet-vi ( large network visualization) 提供基于 k-core 分解算法的二2. 3在复杂网络入侵检测研究中的应用网络这把双刃剑在为人们的生活带来便利的同时，也给人们带来了计算机病毒、传染病病毒的传播，交通运输网、电力网的瘫痪等负面影响9。除了网络本身

20、稳定性不足之外，很大程度来自于网 络攻击。网络入侵检测的研究能够及时发现危险 行为并采取应对之策，保障复杂网络正常的运转。 Livnat 和 Agutter 等人对网络入侵检测进行了深入 研究，提出一种从不同日志中发现网络攻击的可视 化新 方 法，一 旦 发 现 危 险 便 可 以 发 出 带 有 what， when，where3 个内容的警报，有利于实时监控网络。 图 10 是该算法布局的设计，将 3 个属性用一维图形 描绘，中间是攻击发生地点，极坐标表示时间，圆周 上表示发生了什么。图 11 是一个本地机器被外部 资源攻击的状态。这些方法对实时检测网络是否 被入侵十分有效，适用领域广泛。

21、维图像显示布局，能够对大规模网络进行可视化。Jung 框架21是致力于通用、可扩展的免费开源类库，基于 Java 编写，可扩展性强。Jung 的架构是专 门为实体和它们之间的关系而设计的，适合对复杂 网络 进 行 可 视 化。 Processing22 是 Fry 和 Reas 在2001 年开发，随后经过多人修改。 其中，Pocessing社区所开发的 Processing 可视化工具是免费、开源 的，支持计算机视觉、数据可视化、音乐、网络、电子 工业等多学科可视化，可在 Mac，Windows 和 Linux 平台下运行。目前有很多知名公司、设计师、研究 者都在使用这个工具，如 NYTim

22、es RD 实验室的 Cascade 项目23 就是基于 Processing 开发的。 Net- workX24是基于 Python 的软件包，它是专为复杂网 络而设计的，比较适合稀疏网络，但它使用命令行 操作的方式增加了其使用难度。以上所介绍的软 件包 / 框架，均是开源的，其对比如表 1 所示。表 1 部分可视化软件包 / 框架对比名称网络规模编写语言支持平台Igraph超大规模CWindows，Linux，MacLaNet-vi大规模C + +Linux，WindowsJung大规模Java跨平台Processing大规模Java跨平台NetworkX超大规模python跨平台3. 2

23、网络可视化软件复杂网络可视化的软件有很多，此处仅对部分 得到广泛使用的可视化软件进行介绍。Circos25是 Perl 语言开发的自由可视化软件，由加拿大生物信 息科学家 Martin 等26开发。其主要功能是绘制基 于圆形布局方式的图形，由于它支持关系型数据的 可视化，因此在多个领域得到广泛使用。Pajek 是 Windows 环境下的免费应用软件，是典型的基于力 导引布局算法的绘图方式，对网络拓扑结构的可视 化效果非常好。 AVS / Express ( advanced visual sys- tems / express) 是一个数据可视化开发的集成环境，可 以实现大规模网络可视化，并

24、且支持多维数据、海量 数据和交互问题，提供了图形、图像、数据可视化、数3适用于复杂网络的可视化工具目前有很多网络可视化工具，可分为网络可视化软件包 / 框架、可用的网络可视化软件 2 类。据库接口、注释和硬拷贝输出等方面的许多先进技术。该平台并非针对于复杂网络，而是具有广泛性的 集成开发环境，但是在复杂网络可视化方面功能强 大。Graphviz( graph visualization software) 是一个开源 的图形可视化软件，它将结构信息抽象为图形和网 络，可应用在网络、生物信息学、软件工程、数据库、 web 设计、机器学习等其他技术领域。上述可视化软 件的属性对比如表 2 所示。表

25、 2 部分可视化工具对比and Experience，1991，21( 11) : 1129-1164王柏，吴巍，徐超群，等 复杂网络可视化研究综述J 计算机科学，2007，34( 4) : 17-23CUI G Z，QIN L，LIU S，et al Modified PSO algorithm for solving planar graph coloring problemJ Progress in Natural Science，2008，18( 3) : 353-357HSU L Y，HORNG S J，FAN P，et al MTPSO algorithm for solving

26、planar graph coloring problemJ Expert Sys- tems with Applications，2011，38( 5) : 5525-5531 EADES P，FENG Q W Straight-line drawing algorithms for hierarchical graphs and clustered graphsJ Comput- er Science，1997( 1190) : 113-1286789名称可视化规模主要绘图方式支持平台Circos基于圆形布局 Windows，Linux，Mac大规模数据集10 ABELLO J Hiera

27、rchical graph mapsJ Computers Graphics，2004，3( 28) : 345-35911 高榕，李跃新 基于遗传算法的有向无环图画图算法PajekWindows大型网络 基于力导引布局AVS / Express海量数据集 多种布局，可交互跨平台J计算机应用研究，2007，24( 12) : 63-65Graphviz适中数据集 多种布局方式跨平台12 DWYER T，KOREN Y Drawing directed graphs usingquadratic programmingJ IEEE Transactions on Visual- ization

28、and Computer Graphics，2006，12( 4) : 536-54813 EADES P，SYMVONIS A，SYMVONIS S Three-dimen- sional orthogonal graph drawing algorithmsJ Discrete Applied Mathematics，2000，103: 55-8714 GIACOMO E D，LIOTTA G，MEIJER H Computing straight-line 3D grid drawings of graphs in linear volumeJ Computational Geometr

29、y，2005( 32) : 26-5815 WATTS D J，STROGATZ S H Collective dynamics of small-world networksJ Nature，1998( 393) : 440-44216 BARABSI A，ALBERT R Emergence of scaling in ran- dom networksJ Science，1999，286( 5439) : 509-51217 方锦清，汪小帆，郑志刚，等 一门崭新的交叉科学:网络科学( 上) J 物理学进展，2007，27( 3) : 239-34318 吴鹏，李思昆 适于社会网络结构分析

30、与可视化的布局算法J 软件学报，2011，22( 10) : 2467-247519 eetCatcha: visualizing tweets of NYTimes news articlesEB / OL ( 2010-02-16) 2012-06-26 http: infos- thetics com / archives /2010 /02 / tweetcatcha _ visualizing _tweets_of_nytimes_news_articles html20 The igraph project The igraph library v0. 6EB / OL ( 201

31、2-07-17) 2012-06-26 http: igraph sourceforge net / 21 JungEB / OL ( 2010-1-24) 2012-06-26 http: jung sourceforge net / 22 A short introduction to the processing software and projects from the communityEB / OL ( 2010-01-24) 2012-06-4结语和展望本文回顾了可视化算法近年来的发展，结合复杂网络背景，探讨了可视化技术的应用，表明可视化技术对于复杂网络研究有推动作用。但是，在

32、可 视化技术的发展上，仍然面临很多问题。例如，动 态可视化技术仍不成熟，有待继续研究和改进。如 何将当前大部分适用于静态可视化的算法推广到 动态可视化之上，或者寻找适用于网络动态可视化 的更好算法，是今后的一个研究方向; 其次，国内无 法获取部分国外发达国家的先进工具和可视化关 键技术，这在一定程度上阻碍了国内的研究进展， 迫切需要国内学者攻克技术难关，研发以复杂网络 为应用背景的可视化工具。参考文献:1NEWMAN M E J The structure and function of complexnetworksJ SIAM Review，2003，45( 167) : 1-58 BAT

33、TISTA G D， EADES P Algorithms for drawing graphs: an annotated bibliographyJ Computational Ge- ometry: Theory and Applications，1994，4( 5) : 235-282 EADES P A heuristic for graph drawingJ Congressus Nutnerantiunt，1984( 42) : 149-160KAMADA T，KAWAI S An algorithm for drawing gener- al undirected graphs

34、J Information Processing Letters，1989( 31) : 7-15FRUCHTERMAN T M J，REINGOID E M Graph draw- ing by force-directed placement J Software-Practice23426 http: processing org / about / 23 Creative applications network EB / OL ( 2011-04-22 )52012-06-28http: wwwcreativeapplications net / pro-cessing / casc

35、ades-processing / 24 HAGBERG A，SCHULT D，SWART P NetworkX EB / OL( 2012-01-01) 2012-06-29 http: networkx lanl gov / 25 Guides to Circos EB / OL ( 2012-01-04) 2012-06-30 http: www circos ca / guide / 26 KRZYWINSKI M I，SCHEIN J E，BIROL I，et al Cir-cos: an information aesthetic for comparative genomicsJ

36、 Advance，2009，6: 1639-1645作者简介:耿文静( 1988-) ，女，北京人，硕士研究生，主要从事复杂 网络可视化技术等方面的研究; 吴渝( 1970-) ，女，重庆人，博 士，主要从事网络智能和数字媒体技术等方面的研究。Survey on visualization technology and its applications on complex networkGENG Wenjing，WU Yu( Institute of Network Intelligence，Chongqing University of Posts and Telecommunicatio

37、ns，Chongqing，400065)Abstract: The visualization technology is an important means of effective data explaining In recent years，the increasing dataon Internet present new challenges to this technology Firstly，the development of visualization algorithms is summarized from four catalogs，including planar

38、 graph，hierarchy graph，directed graph and space graph Then with complex network as the applied background，the application developments of visualization technology in topology complex network，propagation mech- anism and intrusion detection are introduced，which show the promoting role of visualization

39、 technology in the research of complex network Finally，several visualization tools suitable for complex network are analyzed and comparedKey words: visualization technology，graph algorithms，complex network，visualization tools( 责任编辑: 张 诚)( 上接第 20 页)作者简介:于南翔( 1980-) ，男，黑龙江大庆市人，研究生，讲师，主 要研究方向为可穿戴计算、身体传

40、感网络、AAL 健康辅助 等，E-mail: yunx cqupt edu cn; 陈东义( 1956-) 男，山东人， 教授，电子科技大学博士生导师，CCF 高级会员，现任电子科 技大学 MCC 移动计算中心主任，目前主要研究方向为可穿 戴计算、移动计算、人机交互、增强现实、感知计算与物联网 等，近年来承担与可穿戴计算相关的省部级和特殊单位课题项目 10 余项，( 其中，国家高技术研究发展 863 计划项目 2项，国家自然科学基金 2 项，中国与加拿大政府间科技合作项 目 1 项，中德科学基金项目( 会议) 两项) ; 在国内外学术期刊 及会议上发表学术论文 40 余篇，E-mail: dy

41、chen uestc educn; 夏侯士戟( 1977-) ，男，四川眉山人，电子科技大学副教授，CCF 会员，主要研究方向为可穿戴计算、感知计算、形式化方法等，E-mail: xiahousj uestc edu cnWearable computing technology and its new applicationYU Nanxiang，CHEN Dongyi，HIAHOU Shiji( Mobile Computing Center，University of Electronic Science and Technology，Chengdu，611731; Mathematic

42、s and Physics College，Chongqing University of Posts and Telecommunications，Chongqing，400065)Abstract: Wearable computing technology is a new technology developing with computer，microelectronics and telecommuni-cations technologies，and it has its wide applications in improving peoples standard of liv

43、ing This paper discusses the advan- tages of wearable computing technology over traditional computing and its academic and applicable values in medicine，mili- tary，education，sports and entertainment，etc Its function to push modern information and computing technology forward is also great And its in

44、dustrialization is introduced，showing that modern science and technology and the application need make wearable computing technology develop quickly，with the characteristic of mixing with many other disciplinesKey words: wearable computing; human computer interaction; on-site task assistant; wearable properties( 责任编辑: 张 诚)