logo资料库

图布局算法综述（很详细的）.doc

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.25M 资料格式：doc 举报 版权申诉
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
资料共7页，全文预览结束
    OVERVIEW OF ALGORITHMS FOR GRAPH DRAWING 图布局算法综述 Boštjan Pajntar Department of Knowledge Technologies Jozef Stefan Institute Jamova 39, 1000 Ljubljana, Slovenia（南斯拉夫） Tel: +386 1 4773128 E-mail: bostjan.pajntar@ijs.si 摘要 本文综述若干种图可视化算法，并详细描述了最常用的几个算法。本文的首要目的是帮助读者 选择合适的算法去可视化关系数据。另一方面，也可以当作对图布局算法及其发展的历史回顾 1 概要 从前，信息只是一种 commodity（？商品，不足大量）。然而随着互联网的发展，大规模的数据 变得随处可见。问题从获取信息，变为抽取其中的有用信息。使用统计分析与数据挖掘，我们 能够抽取所需的信息。但是，由于显示是平面的，大部分这些数据挖掘的结果难以为人们所阅 读，由此就产生了对可视化的需求。因为一张图画常常可以蕴含一篇文章（的信息），对任何关 系数据的描绘成为了一种非常常用的表示已获信息的途径。 2 关于图 图论中的定义在不同文献中有所不同。针对我们的需求，图G的一个宽松的定义是一个三元组 （V,E, λ） - 顶点集V - 边集E - 函数λ，映射每条边的端点到一个顶点 一个循环是一条两端指向相同顶点的边。一条多重边表示两个顶点同时关联多条边（图1）。一个没 有循环和多重边的图称为简单图。如果边是有向的，则图为有向图（digraph）。 3 图的大小（size，规模） 关于图的大小并没有专门的术语。图的大小常常被定义为顶点的数目，这并非是一个最好的定义。 由于计算机运行速度日益增长，图的大小会随着时间而改变（译者注：暗示图的大小跟计算机运行 速度应该联系起来）。
    也许一种更好的定义就是将图的大小和计算复杂度（译者注：以下可以理解为单位时间计算机可处 理的顶点数n）联合起来。 我们把图划分为小、中、大(large)、超大(huge)。 - 对于小图，基本上可以使用任何算法。目前这种图的规模为n*10（最大为150个顶点） - 中图可以被多项式时间复杂度的算法所绘制。这种图的规模也是足够小，以被绘制在常用的屏幕 上，其数量为n*100。 - 大图不能被直接地绘制（由于屏幕象素不足）。然而，这种图仍然足以存放在内存中。 - 更大的图就称为超大图（内存都放不下整个图的数据） 同时，我们也按稠密程序把图分为[5]： - 稀疏：|E|<=|V| （译者注：划为理由可能是根据树的性质 |E|=|V|-1 ） - 一般： |V|<|E|<=3|V| - 密集：|E|>3|V| （译者注：划为理由可能是根据平面图的充分条件|E|>=3|V|-6） 这种命名法认为树是稀疏的，而四方体和多面体则为一般图。 4 图的嵌入（Embbeding，译者注：可认为是平面化planarization） 图可视化的质量诚然是一种主观判断。它依赖于图，以及我们希望从中获取的信息。目前，关 于人们如何从图中阅读信息的研究比较少[7]，大多数准则是直观的选择出来的。 首要的指导思想是：用户必须能够从图中获取他所感兴趣的信息，而且越简单越好。 以下是关于好的图绘制的准则： - 顶点必须均匀地分布在屏幕 - 边交叉必须只有少量 - 边长度必须均匀 - 图结构中的对称性必须表现出来 - 图必须被包含在一个画面中（原文为：Graf should be bound inside a frame，译文可能有误 ） 这些准则常常描述了我们的需求。然而，也有例外。 - 平面绘制可能有更好的结果，如果边具有不同的长度（图3，4）。 - 对于大图，顶点必须被聚类；一种可视化的方法是所有同类的顶点被绘制为一点。 - 对于十分稠密的图，对边进行合并具有一定的意义。利用这个方法，可能将非平面图进行平 面绘制。（以下是按次方法对一个96个顶点的完全图的绘制）
    5 算法 可视化图具有许多种方法。常用的对简单无向图的方法是物理类比的（译者注：将图类比为一 定的物理模型，如具有引力斥力的弹簧和粒子）。然而，如果图具有其他的特征，我们可以使用 其他的方法。 5.1 对于具有附加属性的图的算法 5.1.1 正交风格 图可以被绘制在正交栅格上。这种方法常常用于有向图，如我们所见的图表（diagram）。每条 边都可以曲折，但每部分都必须是水平或者垂直。由此每个边交叉都是正交的。这样 有利于对图的阅读。 5.1.2 Sugiyama风格 图布局的一种好方法是层次化布局。对于DAG（有向无循环图），我们可以根据拓扑顺序对图 进行层次化。接着我们就可以得到一个流程图，其所有边都指向同个方向。例如，有一条从A 指向B的边，A就在B的上方或左方。这种方法的一个优点是所有图都可以转换为DAG。Sugiyama 提出了一个很好的算法[11]。另外也见[8]。算法分为三个阶段。 1. 将顶点分布在各层 O（|V|+|E|） 2. 最小化边交叉（NP难，但有好的启发方法） 3. 赋予坐标 O（|E|） 5.1.3 平面嵌入（planar embedding） 平面图是可以被嵌入（译者注：指无交叉地绘制）在平面（或球面）的的图。也就是说，可以 找到一个无交叉的嵌入方法。这类方法具有多种有趣的方法[12]。任何非平面图可以被转换为 平面图（译者注：意思是可以使用平面图算法绘制），先使用这些算法绘制，然后将被删除的边 重插入。 5.2 基于物理类比的绘制方法（Drawing on Physical Analogies），历史回顾 以下是物理类比方法的。对于图的每一个状态（一次布局），我们赋予一个能量值。更小的能力
    代表更好的布局。从这个角度看，搜索一个好的可视化就转换为搜索一个某个函数的全局最小 值。各种算法在能力函数和搜索方法上各有不同。 5.2.1 弹簧嵌入（Spring embedder，中文常常翻译为“弹力模型”）－Eades[4] 图布局最直观的一个方法来自于一个简单的物理模型。每个顶点都看作是一个钢圈（译者注： 平面对其有阻力），顶点间的边看作是它们之间的弹簧。开始时将顶点随机放置，然后让弹力作 用在模型上。固定数量的迭代后算法将停止。这是一个弱点，因为不同的图具有不同的收敛速 度。 与物理定律相比，有两种不同点：1）弹簧力不遵守胡可定律（Hook Law），2）算法中的力改 变速度而不是加速度。这个差异是很重要的，因为stationary stable state is preferred to a moving one（译者注：不明白one是指什么）。 视觉上算法有利于了两各方面：1）边长度均匀；2）图的对称性可被可视化，这是一个nice surprise （意外的惊喜），因为算法本身没有直接针对对称性。 5.2.2 Kamada 和 Kawai（KK）[9] Kamada 和 Kawai改进了弹力模型。算法非常相似，除了一处：每个顶点间都有一定的举例。 顶点间的距离由最短距离获得。 另一个改进是每一次迭代只改变一个顶点。理论上时间复杂度是一样的；但是，收敛速度却有 可观的增加。 5.2.3 Davidson和Harel（DH）[3] 任何能量函数可以被模拟退化算法(simulated annealing，SA)最小化。对模型选择一定的能量函 数，最小化这个能量函数以获得好的布局效果。在当前温度的作用下，模型可以往能量变大的 方向改变。SA往往不能获得全局最小值；但其结果非常接近最小值。这个算法的其中一个准则 是最小值的walleyes和深度同宽（One criterion for this algorithm to work is that walleyes of minima are as wide as deep）。 Davidson和Harel chose neighborhoods of a state to be any state that is the same as initial with one vertex moved inside a ball of radius r。为获得更好的效果，他们令r跟随温度降低而减小。当进入 SA最后阶段的微调，算法不再允许向相反方向移动，而（能量函数）附件两个加数。一个用来 惩罚边交叉，另一个用来惩罚顶点靠近边。 由于使用了SA，这个算法非常耗时。在某些例子中，它可以比其他方法产生更好的效果，比如 更有可能得到平面布局。（图3） 图3 同一个图的FR和DH布局 5.2.4 Fruchteman 和Reingold（FR）[6] Fruchteman 和Reingold仅为图布局制定两天规则： 1. 相连的边必须靠近
    2. 不同的顶点不能靠近 在所有的迭代过程中，我们只需要计算所有相连的顶点间的吸引力，和所有顶点间的斥力。由 于没有边交叉的标量惩罚（系数、因子），这个结果（计算力的结果）是一个向量，它同时指定 了移动的距离和方向。实际移动的距离大小还受到当前温度的制约，温度会随迭代次数而线性 递小。 这个非常简单的算法却产生了很好的结果。其主要的有点在于运行速度和稳定性。今天它仍然 是最常用的图布局算法之一。 由于没有考虑对边交叉的惩罚，它的最终结果常常看起来像是多面体在平面的投影。这可以被 认为是一种特性。 图4 FR和一般的平面布局（plane embedding） 5.2.5 Graph Embedder（GEM）[5] GEM算法改进了FR的计算时间。主要的改进在于为每个顶点赋予局部温度，这是一种防止在最 优值附近盘旋和振荡的方法，并且可以增加正方面的前进距离。其次，该算法使用了重心引力， 它可以令没有连接的顶点靠近在一起，也可以提高收敛性。第三，该算法能够在平均局部温度 较低时（布局较好时）预先停止。 其结果与FR相似，但其计算效率更佳。然而，该算法在稳定性方面不如FR，比如对于某些图， 该算法过快地退出。 5.2.6 LinLog 的顶点和边斥力[10] LinLog模型在GD03和GD05中得到很好的提出和接受。使用有三种不同的能量函数；但是它们 可以统一在同一个模型中。 一个与FR相似；其余的两个已经被用于图的聚类。一个被称为顶点斥力LinLog。其结果见图5。 另一个能量函数，边斥力LinLog，是针对顶点具有较为不同的度的图。具有较大的度的顶点被 较远地隔离（其他顶点）。这对于社会网络是非常有用的，其具有较大的度差异（有些顶点度很 大，有些很小）。除不同的能量函数以外，Barnes和Hut的算法也被用在计算顶点斥力。时间复 杂度从O(|V|2)变为O(|V|log(|V|))。
    图5 带有类内边（intra-cluster edge）概率为0.16和类间边（inter-cluster edge）概率为0.01的伪随 机图； 左LinLog 右FR 5.2.7 多层次算法[13] 如果需要更快的算法，那么我们可以使用从一种算法，它来自与一种直觉，即图必须在所有规 模下都很好地呈现（Graph should look nice on all scales）。首先选择半径r0, r1… rn。对于每个半 径ri，对局部（半径为ri）进行K聚类。K根据当前的半径进行选择。同类的顶点被布局在类的重 心，同时对这个类进行美化。 这个算法非常快；然而，它退化图的直径的问题。 5.2.8 高维嵌入[14] 这个算法更快，具有线性的运行时间！其背后的思想是：一个好的图布局可以轻易地在高维空 间获得。一般地，50维足够。第二步是将图投影到常见的二维或者三维空间。算法非常快，而 且对于常见的某些图，如mash（杂乱的图？），效果非常好；但是对于日常生活中的图，有时许 多顶点会被映射为一个顶。然而，在几秒内对上万个顶点进行布局是不可多得的（nice to have）。 6 结论 算法的选择取决与用户需求。FR算法非常稳定和快速，足以交互式地（实时地）绘制日常遇到 的图。如果要对大规模的图进行交互式绘制，则需要其他方法。另一方面，对于大图，位置布 局并不及对某些我们所关心的属性进行可视化来得重要。如果图具有某些附加的数据，我们常 常能够对它进行利用。 出版权外的图布局应用也有很多。他们常常是用java编写，而且免费在新使用。这些所使用的 算法一般是我们这里所介绍的算法的少量改进。 参考文献 [1] J. Barnes and P. Hut. A Hierarchical O(NlogN) Force Calculation Algorithm. Nature, 1986. [2] Dirk Beyer and Andreas Noack. Clustering software artifacts based on frequent common changes. In IWPC ’05: Proceedings of the 13th International Workshop on Program Comprehension, pages 259–268, Washington, DC, USA, 2005. IEEE Computer Society. [3] Ron Davidson and David Harel. Drawing graphs nicely using simulated annealing. ACM Transactions on Graphics, 15(4):301–331, 1996. [4] Peter Eades. A heuristic for graph drawing. 42:149–160, 1984. [5] Arne Frick, Andreas Ludwig, and Heiko Mehldau. A fast adaptive layout algorithm for undirected graphs. In Roberto Tamassia and Ioannis G. Tollis, editors, Proc. DIMACS Int. Work. Graph Drawing, GD, 1993 894, pages 388–403, Berlin, Germany, 10–12 1994.Springer-Verlag. [6] T. M. J. Fruchterman and E. M. Reingold. Graph drawing by forcedirected placement. Softw. Pract. Exper., 1991.
    [7] Weidong Huang and Peter Eades. How people read graphs. In APVIS, pages 51–58, 2005. [8] Michael J¨unger and Petra Mutzel, editors. Graph Drawing Software. Springer Mathematics and Visualization Series, 2004. [9] T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Inf. Process. Lett., 1989. [10] A. Noack. An energy model for visual graph clustering, 2003. [11] K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. SMC-11(2):109–125, February 1981. [12] W. T. Tutte. How to draw a graph. In Proceedings London Math. Society, pages 743–768, 1963. Graph drawing. [13] D. Harel, Y. Koren. A Fast Multi-Scale Method for Drawing Large Graphs, Journal of Graph Algorithms and Applications, vol. 6, no. 3, pp 179-202, 2002 [14] D. Harel, Y. Koren. Graph Drawing by High- Dimensional Embedding. Graph Drawing: 10t International Symposium, GD2002, Irvine, CA, USA,August 26-28, 2002
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料