Graph layout (图布局质量)

之前IEEE VIS投稿做了一个和降维相关的图布局项目,虽然最后没中,但是投稿过程中收获很多。这次是在可视化暑期学校时候听了中科院软件所时磊老师的报告,觉得挺有趣的就简单做了一个整理。

图布局质量判定规则

首先是关于图布局的美学评判指标,大多数时候看图都是以主观的形式进行判断,但是怎样才能有一个可以量化的评价指标呢。下面就有两个规则可以作为参考。

  • 首要规则:最小化边交叉数目
    因为当图中出现很多边交叉时,会导致用户可视化理解图数据能力显著下降
  • 次要规则:最小化边曲折度
    图中有较多的曲折边,会导致用户可视化理解图数据能力一定程度地下降,可以想象尤其当图中出现非常多的曲折边时,那将是一种灾难。

图布局算法

经典的图布局算法有很多,下面挑几个报告中出现的图布局算法。

Force-directed 基于力引导的图布局算法

力引导布局 (Force-directed graph layout)[1] 由悉尼大学的Peter Eades教授,在1984的论文中[1]首次提出了力导向算法的原型。力引导布局可以用于描述关系图的结点之间的关系,把结点分布到画布上合理的位置,比如描述企业之间的关系,社交网络中的人际关系等。

力导向的图布局是一种物理模拟方法,我们假设每个节点是一个粒子,任意两个粒子之间存在斥力,节点与节点之间的边相当于弹簧,存在弹力。

一旦定义了图的节点和边上的力,就可以模拟这些条件下的图的行为,图就像是物理系统一样。在这样的模拟中,力被施加到节点,将它们拉近或将它们进一步推开。不断迭代地重复这一过程,直至整个系统达到机械平衡态;即它们的相对位置相比于上一次迭代,不再改变。

这个过程中除了物理模拟或与物理模拟结合的方法,还可以采用更直接的能量最小化的机制,这些机制是一般都是基于全局优化,包括模拟退火和遗传算法等。

Tutte 基于重心的图布局算法

Tutte’s barycenter algorithm
一个简单的三个顶点连接平面图的Tutte[2] 嵌入或重心嵌入是一个无交叉的直线嵌入,具有外面是凸多边形的特性,并且每个内部顶点处于平均(或重心)邻居的位置。

Input:

- A graph G = (V, E) with node set V and edge set E

Output:

- A straight-line drawing p of G
  • Step 1. Choose a subset A of V
  • Step 2. Choose a location for each vertex $a$ $\epsilon$ $A$
  • Step 3. For all $u$ $\epsilon$ $V - A$, choose $p(u)$ bywhere the sum is over all neighbors $v$ of $u$.

基于Planarity的图布局算法

Planar graph是可以在平面展示但是没有交叉边的图(其中边与边可以在端点相交)。

A planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.

其它定制化图布局方法

  • 层次图布局

  • 正交图布局

  • 辐射状图布局

最后今年组内一位师兄做的大图可视化的工作被VIS接收,工作也很棒,强烈推荐,大家有兴趣可以去看看论文呀[3]。

Reference

[1]. A heuristics for graph drawing. Congr. Peter Eades. Numer. 42 (1984) 149-160.
[2]. How to draw a graph, Tutte, W. T. Proceedings of the London Mathematical Society, 13: 743–767, 1963.
[3]. Structure-Based Suggestive Exploration: A New Approach for Effective Exploration of Large Networks. Wei Chen, Fangzhou Guo, Dongming Han, Jiacheng Pan, Xiaotao Nie, Jiazhi Xia, Xiaolong Zhang. IEEE Transactions on Visualization and Computer Graphics (Special issue on IEEE VAST 2018), 2019.