集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织

图的绘制 Graph drawing


图1：以图的形式展示万维网的一小部分

图的绘制 Graph drawing是数学和计算机科学的一个交叉领域，它结合了几何图形理论 geometric graph theory和信息可视化 information visualization的方法，可以用于对来自社会网络分析、制图学、语言学和生物信息学等各种应用场景进行二维描述。[1]


图形或网络图 network diagram的绘制是通过从图形抽象出的顶点和边表示的。这里说的图不应与图形本身混淆：毫不相似的图可以对应于同一个图形。[2]抽象地说，重要的是哪一对顶点是由边连在一起。然而，在具体的绘图中，这些顶点和边的排列影响了它的可理解性、可用性、制造成本和美学。[3]如果图形通过添加和删除边缘（动态绘制图形）而随时间变化，并且目的是保存用户的心理映射，那么问题会变得更糟糕。[4]


绘图惯例 Graphical conventions

 
图2：带箭头显示边方向的有向图

图经常绘制成节点链接图，其中顶点可以是为圆框、方框或文本标签，边表示为欧式平面 Euclidean Plane上的线段、折线或曲线。[3]节点链接图可以追溯到13世纪雷蒙·卢尔 Ramon Llull的作品，他为得到完全图，绘制了这种类型的图，以便分析形而上学概念集合之间的所有成对组合。[5]


在有向图中，绘图惯例规定用箭头表示它们的方向；[2] 然而，用户研究表明，其他惯例（例如，渐缩）可以更有效地提供此信息。[6]向上的平面绘图绘图惯例是，每个边都从较低的顶点定向到较高的顶点，因此就不再需要箭头。[7]


节点链接图的替代约定包括：

  • 邻接表示，例如圆堆积 circle packings，其中，顶点由平面中的不相交区域表示，边缘由区域之间的邻接表示；
  • 交点表示，其中顶点由不相交的几何对象表示，而边线由其交点表示；
  • 可见性表示，其中顶点由平面中的区域表示，边缘由彼此无障碍视线的区域表示；
  • 融合图，其中边缘表示为数学火车轨道内的平滑曲线；
  • 织物，其中节点表示为水平线，边缘表示为垂直线；[8]
  • 图表的邻接矩阵的可视化。


质量度量 Quality measures

为了找到客观评价图形美观性和可用性的方法，我们定义了许多不同的图形质量度量方法。[9]除了用于指导对同一图形的不同布局方法之间的选择之外，某些布局方法还尝试直接优化度量方式。

 
图3：没有重叠边的平面图


  • 图的交叉数 Crossing number是相交的成对的边的数目。如果图形是平面的，那么我们通常可以方便地画出没有任何边缘相交的图形;也就是说，在本例中，图形绘制表示图形嵌入 Graph embedding。然而，实际应用中经常出现非平面图，因此图形绘制算法通常必须考虑边缘交叉。[10]
  • 一个图形的面积是它的最小边界盒 bounding box的大小，与任意两个顶点之间的最近距离有关。面积小的图通常比面积大的图更可取，因为它们可以让图画的特征以更大的尺寸显示，从而更醒目。当然，边框的纵横比也很重要。
  • 对称显示的问题是在给定的图形中找到对称组 Symmetry Groups，并找到尽可能多地显示对称的绘图。一些布局方法自动形成对称图形;另外，一些绘图方法从查找输入图形中的对称性开始，并使用它们来构造绘图。[11]
  • 重要的是，边缘的形状要尽可能简单，以便更容易循着它们的轨迹观察。在折线图中，一条边的复杂性可以通过它的弯曲数来衡量，多数方法的目的是提供很少的总弯曲或每条边很少弯曲的图。类似地，对于样条曲线，边的复杂性可以通过边上控制点的数量来度量。
  • 几种常用的质量度量方法与边的长度有关：通常需要最小化边的总长度以及任何边的最大长度。此外，最好使边缘的长度一致而不是差别很大。
  • 角度分辨率 Angular resolution是图形绘制中最小的锐角的度数。如果一个图的顶点高度高，那么它的角分辨率就很小，但是角分辨率也可以由角的函数来限定。[12]
  • 图的斜率 slope number是在具有直线段边(允许交叉)的图中所需的明显边缘斜率的最小值。三次图 Cubic Graphs的斜率最大为4，五次图的斜率数可能是无界的，但四次的图的斜率是否有界仍然有待求证的。[12]


布局方法 Layout methods

 
图4：基于力的网络可视化 [13]
 
图5：弧线图

有许多不同的图形布局方法，如下：

  • 在基于力的布局系统 Force-Based Layout中，图形绘制软件根据基于弹簧系统或分子力学的物理隐含的力系统，不断移动顶点来修改初始顶点的位置。通常，这些系统将相邻顶点之间的吸引力与所有对顶点之间的排斥力结合起来，以寻求一种边长较小而顶点分离良好的布局。这些系统可以执行梯度下降 gradient descent最小化的能量函数，或可以把力直接转化为节点的速度或加速度。[14]
  • 频谱布局法 Spectral layout，以从图的邻接矩阵派生的矩阵（例如Laplacian）的特征向量 Eigenvector作为坐标。[15]
  • 正交布局法 Orthogonal layout methods，允许图形的边缘水平或垂直运行，平行于布局的坐标轴。这些方法最初是为超大规模集成电路和PCB布局问题而设计的，但它们也适用于图形绘制。它们通常涉及到一种多阶段的方法，通过用顶点替换交叉点来平面化输入图，找到一个平面化图的拓扑嵌入，选择边的方向来最小化弯曲，顶点的放置始终与这些方向一致，最后一个布局压缩阶段减少图形面积。[16]
  • 树形布局算法显示了一种类似树的根状结构，适合树。通常，在一种称为气球布局的技术中，树形图每个节点的子节点被画在围绕该节点的圆上，这些圆的半径在树的较低层次上递减，因此这些圆不会重叠。[17]
  • 分层图绘制方法 Layered graph drawing（通常称为杉山式图 Sugiyama-style drawing）最适合于有向无环图 directed acyclic graphs或接近无环的图，例如软件系统中模块或函数之间的依赖关系图。在这些方法中，图的节点使用Coffman Graham算法等方法被安排到水平层中，以这样的方式，大多数边从一层向下到下一层;在这一步之后，将每一层内的节点进行排列，使交叉最少。[18]
  • 弧线图 Arc Diagram，这种布局风格可以追溯到20世纪60年代，[19]{将顶点放在一条直线上;边缘可以画成在直线上方或下方的半圆，也可以画成由多个半圆连接在一起的光滑曲线。
  • 圆形布局法 Circular Layout将图形的顶点放置在一个圆上，仔细选择圆周上顶点的顺序，以减少交叉，并将相邻的顶点放置在彼此接近的位置。边可以画成圆的弦，也可以画成圆内外的弧线。在某些情况下，可以使用多个圆。[20]
  • 优势图 Dominance drawing当且仅当一个顶点可以从另一个顶点到达时，画顶点的最优方式是：一个顶点向上，或向右，或两个顶点同时向上。这样，布局风格使得图的可达性关系在视觉上变得明显。[21]


专用图

在其他应用领域出现的图和图绘制包括：

  • 社会图 Sociogram，社会网络图，通常由社会网络分析软件提供；[22]
  • 哈塞图 Hasse diagram，一种专门用于部分顺序的图形绘制[23]
  • Dessin d'enfants，代数几何中使用的一种图形画法；[24]
  • 状态图 State diagram，有限状态机的图形表示；[25]
  • 计算机网络图 Computer network diagram，描述计算机网络中的节点和连接；[26]
  • 流程图 Flowchart和drakon 图，其中节点表示算法的步骤，边表示步骤之间的控制流的绘图；
  • 数据流程图 Data-Flow Diagram，其中节点表示信息系统的组件，边缘表示信息从一个组件到另一个组件的移动；
  • 生物信息学包括系统发育树，蛋白质，蛋白质相互作用网络，和代谢途径。[27]


此外，电子设计自动化 electronic design automation（EDA）的布局和布线步骤在很多方面与图形绘制相似，而在分布式计算 distributed computing中贪婪嵌入 Greedy embedding的问题也是如此，并且图形绘制文献包括从EDA文献中借来的一些结果。然而，这些问题也在几个重要方面有所不同：例如，在 EDA，面积最小化和信号长度比美观更重要，EDA中的路由问题可能每个网有两个以上的终端，而图绘制中的类似问题通常只涉及每条边的顶点对。

软件

 
图6：Gephi 0.9.1界面

软件、系统和绘制图形系统的提供者包括:

  • BioFabric：开源软件，用于将节点绘制为水平线来可视化大型网络。
  • Cytoscape：可视化分子相互作用网络的开源软件
  • Gephi：开源网络分析和可视化软件
  • Graph-Tool：一个免费/免费的Python库，用于分析图形
  • Graphviz：来自美国电话电报公司的开放源码绘图系统[28]
  • Linkurious：图形数据库的商业网络分析和可视化软件
  • Mathematica：一个通用的计算工具，包括2D和3D图形可视化和图形分析工具。[29][30]
  • Microsoft Automatic Graph Layout：用于图表布局的开放源码net库（以前称为GLEE）[31]
  • NetworkX：用于研究图和网络的Python库
  • Tom Sawyer Perspectives：[32]是一款基于图形的软件，用于构建企业级图形和数据可视化和分析应用程序。它是一个软件开发工具包（SDK），具有基于图形的设计和预览环境
  • Tulip：[33] 开源数据可视化工具
  • yEd： 具有图形布局功能的图形编辑器[34]
  • PGF/TikZ： 带graphdrawing软件包的3.0（需要LuaTeX）[35]
  • LaNet-vi：开源大型网络可视化软件
  • Edraw Max：2D商业技术制图软件

参考文献

  1. ↑ Di Battista et al. (1994), pp. vii–viii; Herman, Melançon & Marshall (2000), Section 1.1, "Typical Application Areas".
  2. ↑ 2.0 2.1 Di Battista et al. (1994), p. 6.
  3. ↑ 3.0 3.1 Di Battista et al. (1994), p. viii.
  4. ↑ Di Battista et al. (1994), p. viii.
  5. ↑ Knuth, Donald E. (2013), "Two thousand years of combinatorics", in Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37.
  6. ↑ Holten & van Wijk (2009); Holten et al. (2011).
  7. ↑ Garg & Tamassia (1995).
  8. ↑ Longabaugh (2012).
  9. ↑ Di Battista et al. (1994), Section 2.1.2, Aesthetics, pp. 14–16; Purchase, Cohen & James (1997).
  10. ↑ Di Battista et al. (1994), p 14.
  11. ↑ Di Battista et al. (1994),p. 16.
  12. ↑ 12.0 12.1 Pach & Sharir (2009).
  13. ↑ Grandjean, Martin (2014). "La connaissance est un réseau". Les Cahiers du Numérique. 10 (3): 37–54. doi:10.3166/lcn.10.3.37-54. Retrieved 2014-10-15.
  14. ↑ Di Battista et al. (1994), Section 2.7, "The Force-Directed Approach", pp. 29–30, and Chapter 10, "Force-Directed Methods", pp. 303–326.
  15. ↑ Beckman (1994); Koren (2005).
  16. ↑ Di Battista et al. (1994), Chapter 5, "Flow and Orthogonal Drawings", pp. 137–170; (Eiglsperger, Fekete & Klau 2001).
  17. ↑ Herman, Melançon & Marshall (2000), Section 2.2, "Traditional Layout – An Overview".
  18. ↑ Sugiyama, Tagawa & Toda (1981); Bastert & Matuszewski (2001); Di Battista et al. (1994), Chapter 9, "Layered Drawings of Digraphs", pp. 265–302.
  19. ↑ Saaty (1964).
  20. ↑ Doğrusöz, Madden & Madden (1997).
  21. ↑ Di Battista et al. (1994), Section 4.7, "Dominance Drawings", pp. 112–127.
  22. ↑ Scott (2000); Brandes, Freeman & Wagner (2014).
  23. ↑ Di Battista et al. (1994), pp. 15–16, and Chapter 6, "Flow and Upward Planarity", pp. 171–214; Freese (2004).
  24. ↑ Zapponi (2003).
  25. ↑ Anderson & Head (2006).
  26. ↑ Di Battista & Rimondini (2014).
  27. ↑ Bachmaier, Brandes & Schreiber (2014).
  28. ↑ "Graphviz and Dynagraph – Static and Dynamic Graph Drawing Tools", by John Ellson, Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Gordon Woodhull, in Jünger & Mutzel (2004).
  29. ↑ GraphPlot Mathematica documentation
  30. ↑ Graph drawing tutorial
  31. ↑ Nachmanson, Robertson & Lee (2008).
  32. ↑ Madden et al. (1996).
  33. ↑ "Tulip – A Huge Graph Visualization Framework", by David Auber, in Jünger & Mutzel (2004).
  34. ↑ "yFiles – Visualization and Automatic Layout of Graphs", by Roland Wiese, Markus Eiglsperger, and Michael Kaufmann, in Jünger & Mutzel (2004).
  35. ↑ Tantau (2013); 详见GD 2012 presentation


一般参考资料

专门的子主题

其他链接

  • GraphX library for .NET: open-source WPF library for graph calculation and visualization. Supports many layout and edge routing algorithms.


编者推荐

集智相关文章

搭建图与网络之间的桥梁：网络科学的下一个突破在哪里？

网络是认识世界的强力手段，图论则是网络科学的数学基础，但两个领域近年来的结合并不密切。来自中欧大学的网络科学研究者，在Nature子刊Communications Physics上发表文章 Bridging the gap between graphs and networks，讨论如何将网络科学解决现实问题的经验引入图论运营，同时将图论中的前沿数学成果带入网络科学。在数据驱动下，架起图与网络之间的桥梁，网络科学将有机会迎来更大的突破。


集智课程

图网络解决优化问题——图网络读书会

图神经网络是深度学习领域的前沿热点议题，尤其是图网络（GraphNetworks）提出以来，深度学习有了实现因果推理的潜力。为了持续追踪相关领域的前沿进展，集智俱乐部联合北师大系统科学学院张江课题组，组织了以图网络为主题的线上读书会，研讨最新论文，孕育研究思路。本系列课程为图网络论文解读活动“图网络解决优化问题”篇。



本中文词条Ryan翻译，由CecileLi审校，薄荷编辑欢迎在讨论页面留言。

本词条内容翻译自 wikipedia.org，遵守 CC3.0协议。

取自“https://wiki.swarma.org/index.php?title=图的绘制_Graph_drawing&oldid=20627”