力导向图

力导向图形绘制算法是以美观的方式绘制图形的一类算法。它们的目的是将一个图的节点定位在二维或二维三维空间中，这样所有的边或多或少都是等长的，交叉的边越少越好。方法是根据边和节点的相对位置在边和节点的集合中分配力，然后利用这些力模拟边和节点的运动[2]。

使用力导向图算法的社交网络可视化[1]
使用力导向图算法的维基网页间链接的可视化

虽然图形绘制可能是一个难题，但作为物理模拟的力导向算法通常不需要关于平面性等图论的特殊知识。

力

力导向图绘制算法把把力赋给图形绘制的节点集合与边的集合。通常，基于胡克定律的类似弹簧的吸引力用于相互吸引的图形中边的端点，同时使用基于库仑定律的带电粒子的排斥力来分隔所有节点对。在该力系统的平衡状态下，边的长度往往是一致的（因为弹簧引力），而没有通过边连接的节点往往会被拉开得更远（因为电荷斥力）。可以使用不基于弹簧和粒子的物理行为的函数来定义边引力和顶点斥力；例如，一些力导向系统使用吸引力是对数而不是线性的弹簧。

一个替代模型为每对节点考虑一个类似弹簧的力 ，其中每个弹簧的理想长度 与节点i和j之间的图论距离成正比，无需使用单独的排斥力。极小化节点之间的欧几里德距离和理想距离之间的差异（通常是平方差）相当于一个度量多维标度问题。

力导向图可以涉及机械弹簧和电荷斥力以外的力。可以使用类似于重力的力将顶点拉向绘图空间的固定点；这可用于将断开连接的图的不同连通分量拉到一起，否则这些图会由于斥力而彼此分开，并把具有更大连通分量的节点绘制到图中更中心的位置[3]。它还可能影响单个组件内的顶点间距。类似的，磁场也可用于有向图。排斥力可以放在边缘和节点上，以避免在最终绘图中重叠或近似于重叠。在诸如圆弧或样条曲线之类的边为曲线的图形中，也可以在这些曲线的控制点上施加力，例如提高它们的角分辨率。[4]

方法

一旦定义了图的节点和边上的力，就可以模拟在这些源下整个图的行为，就好像它是一个物理系统一样。在这样的模拟中，力被施加到节点上，将它们拉得更近或推得更远。如此反复迭代，直到系统达到机械平衡状态；即，从当前迭代到下一次迭代，它们的相对位置不再改变。该平衡中节点的位置用于生成图形的绘制。

对于由理想长度与图论距离成正比的弹簧定义的力，应力优化（英语：Stress majorization）提供了一种表现非常好的（即单调收敛）[5]和数学上优雅的方法来极小化这些差异，从而找到对于图形来说一个好的布局。

也可以采用更直接地搜索能量极小值的机制，而不是物理模拟或与物理模拟结合使用。这种机制是一般全局优化（英语：Global optimization）方法的例子，包括模拟退火和遗传算法。

优点

以下是力导向算法最重要的优点：

高质量的结果
至少对于中等大小（最多 50-500 个顶点）的图形，基于以下标准，获得的结果通常具有非常好的结果：均匀的边长、均匀的顶点分布和显示对称性。最后一个标准是最重要的标准之一，任何其他类型的算法都很难实现。
灵活性
力导向算法可以很容易地进行调整和扩展，以满足额外的审美标准。这使它们成为最通用的图形绘制算法类。现有扩展的示例包括有向图、3D图绘制[6]、 集群图绘制、约束图绘制和动态图绘制。
直觉的
由于它们基于常见物体（如弹簧）的物理类比，因此算法的行为相对容易预测和理解。其他类型的图形绘制算法并非如此。
简单
典型的力导向算法很简单，只需几行代码即可实现。其他类别的图形绘制算法，例如用于正交布局的算法，通常涉及更多。
互动性
此类算法的另一个优点是交互性。通过绘制图形的中间阶段，用户可以跟踪图形如何演变，看到它从混乱的混乱状态展开，变成漂亮的配置。在一些交互式图形绘制工具中，用户可以将一个或多个节点从其平衡状态中拉出并观察它们迁移回原位。这使它们成为动态和在线图形绘制系统的首选。
扎实的理论基础
虽然简单的专门的力导向算法经常出现在文献和实践中（因为它们相对容易理解），但更合理的方法开始受到关注。自1930年代以来，统计学家一直在解决多维标度(MDS) 中的类似问题，物理学家在处理相关n体问题方面也有着悠久的历史——因此存在极其成熟的方法。例如，度量 MDS的应力优化（英语：stress majorization）方法可以应用于上述图形绘制。这已被证明是单调收敛的。单调收敛是算法在每次迭代时减少布局的压力或成本的特性，它很重要，因为它保证布局最终会达到局部最小值并停止。阻尼调度会导致算法停止，但不能保证达到真正的局部最小值。

缺点

力导向算法的主要缺点包括：

高运行时间
典型的力导向算法通常被认为具有等效于O(n3)的运行时间，其中n是输入图的节点数。只是因为估计需要迭代O(n)，每次迭代需要计算每对节点间的斥力。这与物理学中的N体问题有关。然而，由于排斥力本质上是局部的，因此可以将图划分为仅考虑相邻顶点。确定大图布局的常用技术包括高维嵌入算法、多层绘制和其他与N体模拟相关的方法。例如，基于Barnes–Hut模拟的FADE方法[7][8]可以将每次迭代的运行时间提高到n*log(n)。作为粗略的指导，使用标准的每次迭代n2技术在几秒钟内最多可以绘制1,000个节点，使用每次迭代n*log(n)技术在几秒钟内可绘制100,000个节点。力导向算法与多层次方法相结合时，可以绘制数百万个节点的图形。[8] Force-directed algorithms, when combined with a multilevel approach, can draw graphs of millions of nodes.[9]
局部极小值
很容易看出，力导向算法产生了一个能量极小的图，特别是一个总能量仅为局部极小值的图。在许多情况下，找到的局部极小值可能比全局最小值差很多，这会转化为低质量的绘图。对于许多算法，尤其是那些只允许顶点下坡移动的算法，最终结果会受到在大多数情况下是随机生成的初始布局的强烈影响。随着图的顶点数量的增加，局部最小值差的问题变得更加重要。不同算法的组合应用有助于解决这个问题。[10]例如，使用Kamada-Kawai算法[11]快速生成合理的初始布局，然后使用 Fruchterman-Reingold算法[12]来改进相邻节点的放置。另一种实现全局最小值的技术是使用多级方法。[13]

历史

力导向方法绘制图形可追溯到Tutte (1963)：多面体图形可以在平面上绘制的所有面凸出通过固定的平面的外表面的嵌入图表的入顶点凸位置，在每条边上放置一个类似弹簧的吸引力，让系统达到平衡。[14]由于在这种情况下力的简单性质，系统不会陷入局部最小值，而是收敛到唯一的全局最优配置。由于这项工作，具有凸面的平面图的嵌入有时称为Tutte嵌入。

1984年Eades提出了边表示引力，所有节点对之间为斥力的模型。[15]此外这方面的先锋工作还有1991年Fruchterman Reingold。[12]

在顶点对之间只使用弹簧力，理想弹簧力等于顶点间的图论距离的模型，是Kamada Kawai在1989年提出的。[11]

参见

  • Cytoscape（英语：Cytoscape），用于可视化生物网络的软件。 基础包包括力导向布局作为内置方法之一。
  • Gephi，一个针对各种网络和复杂系统、动态和层次图的交互式可视化和探索平台。
  • Graphviz，实现多级力导向布局算法（以及许多其他算法）的软件，能够处理非常大的图形。
  • Tulip（英语：Tulip (software)），实现大多数力导向布局算法（GEM、LGL、GRIP、FM³）的软件。
  • Prefuse（英语：Prefuse）

延伸阅读

  • di Battista, Giuseppe; Peter Eades; Roberto Tamassia; Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999, ISBN 978-0-13-301615-4 
  • Kaufmann, Michael; Wagner, Dorothea (编), Drawing graphs: methods and models, Lecture Notes in Computer Science 2025 2025, Springer, 2001, ISBN 978-3-540-42062-0, doi:10.1007/3-540-44969-8 

外部链接

参考文献

  1. ^ Grandjean, Martin, Introduction à la visualisation de données, l'analyse de réseau en histoire, Geschichte und Informatik 18/19 (PDF): 109–128, 2015 [2021-08-12], （原始内容 (PDF)存档于2021-05-06） 
  2. ^ Chernobelskiy, R.; Cunningham, K.; Goodrich, M. T.; Kobourov, S. G.; Trott, L., Force-directed Lombardi-style graph drawing, Proc. 19th Symposium on Graph Drawing (PDF): 78–90, 2011 [2021-08-12], （原始内容 (PDF)存档于2021-08-12） .
  3. ^ Bannister, M. J.; Eppstein, D.; Goodrich, M. T.; Trott, L., Force-directed graph drawing using social gravity and scaling, Proc. 20th Int. Symp. Graph Drawing, 2012, Bibcode:2012arXiv1209.0748B, arXiv:1209.0748   .
  4. ^ Chernobelskiy, R.; Cunningham, K.; Goodrich, M. T.; Kobourov, S. G.; Trott, L., Force-directed Lombardi-style graph drawing, Proc. 19th Symposium on Graph Drawing (PDF): 78–90, 2011 [2021-08-12], （原始内容 (PDF)存档于2021-08-12） .
  5. ^ de Leeuw, Jan, Convergence of the majorization method for multidimensional scaling, Journal of Classification (Springer), 1988, 5 (2): 163–180, doi:10.1007/BF01897162 .
  6. ^ Vose, Aaron. 3D Phylogenetic Tree Viewer. [3 June 2012]. [失效链接]
  7. ^ Harel, David; Koren, Yehuda, Graph drawing by high-dimensional embedding, Proceedings of the 9th International Symposium on Graph Drawing: 207–219, 2002, CiteSeerX 10.1.1.20.5390  , ISBN 3-540-00158-1 
  8. ^ 8.0 8.1 Quigley, Aaron; Eades, Peter, FADE: Graph Drawing, Clustering, and Visual Abstraction, Proceedings of the 8th International Symposium on Graph Drawing (PDF): 197–210, 2001 [2021-08-12], ISBN 3-540-41554-8, （原始内容存档 (PDF)于2021-08-12） .
  9. ^ A Gallery of Large Graphs. [22 Oct 2017]. （原始内容存档于2021-05-25）. 
  10. ^ Collberg, Christian; Kobourov, Stephen; Nagra, Jasvir; Pitts, Jacob; Wampler, Kevin, A System for Graph-based Visualization of the Evolution of Software, Proceedings of the 2003 ACM Symposium on Software Visualization (SoftVis '03), New York, NY, USA: ACM: 77–86; figures on p. 212, 2003, ISBN 1-58113-642-0, doi:10.1145/774833.774844, To achieve an aesthetically pleasing layout of the graph it is also necessary to employ modified Fruchterman–Reingold forces, as the Kamada–Kawai method does not achieve satisfactory methods by itself but rather creates a good approximate layout so that the Fruchterman-Reingold calculations can quickly "tidy up" the layout. 
  11. ^ 11.0 11.1 Kamada, Tomihisa; Kawai, Satoru, An algorithm for drawing general undirected graphs, Information Processing Letters (Elsevier), 1989, 31 (1): 7–15, doi:10.1016/0020-0190(89)90102-6 .
  12. ^ 12.0 12.1 Fruchterman, Thomas M. J.; Reingold, Edward M., Graph Drawing by Force-Directed Placement, Software – Practice & Experience (Wiley), 1991, 21 (11): 1129–1164, doi:10.1002/spe.4380211102 .
  13. ^ http://jgaa.info/accepted/2003/Walshaw2003.7.3.pdf （页面存档备份，存于互联网档案馆） A Multilevel Algorithm for Force-Directed Graph-Drawing
  14. ^ Tutte, W. T., How to draw a graph, Proceedings of the London Mathematical Society, 1963, 13 (52): 743–768, doi:10.1112/plms/s3-13.1.743 .
  15. ^ Eades, Peter, A Heuristic for Graph Drawing, Congressus Numerantium, 1984, 42 (11): 149–160 .