基于拉普拉斯的动态图布局方法

---

在这个工作中，我们提出了一个基于拉普拉斯变换的图布局保持算法来保持动态图布局的稳定性，维持用户的思维导图。我们的布局策略包括两个步骤。首先，先用静态图布局算法计算出每个时间步图的布局，确定顶点的位置。这时候，图的布局具有较好的美观性。紧接着，调整图结构。通过运用基于拉普拉斯的距离内嵌子图保持算法（Laplacian constrained distance embedding algorithm, 即LCDE），我们改善图的初始布局，移动顶点来保持与上一时间步相同的子图的形状不变。为此，如果两个相邻时间步之间存在相同的子图，用户就可以快速的建立相应的连接。

与已存在的动态图布局算法相比，我们的策略有两个明显的优势。一是LCDE算法应用在后处理方面。所以，我们的布局策略可以充分利用静态图的布局算法，来获得美观性和稳定性兼得的图布局；同时，我们的策略是保持相同子图的形状、结构，而不是完全限制顶点的移动。在这个策略中，顶点具有更大的自我调整空间，形成的布局具有更好的美感。并且，用户仍可以在相邻时间步之间建立相应的连接。

下面，我们将通过一个例子来展示我们算法的有效性。

这个例子的数据，描述的是大学生之间朋友关系随时间的变化[1]。上图展示了我们的方法获取的布局（上列）和Frishman等人的的算法[2]得到的布局（下列）的比较。从这个图中，可以发现，我们的图布局比Frishman等人的更稳定。例如，在整个序列中，在我们的布局中，绿色子图的布局比较稳定，尽管不断有新的边加入，旧的边消失。然而，在Frishman等人的布局中，这部分子图的结构变化巨大。同时，对于橙色子图，观察上图T3时刻的图，我们发现，此刻是该子图发生结构式变化的转折点。但是，在我们的布局中，这部分子图轮廓的变化是平滑地进行的；相反的，在Frishman等人的布局中，这部分子图结构的变化很突兀，用户难以进行相应的追踪。

参考文献:

[1]T. M. Newcomb. The acquaintance process. In Holt, Rinehart and Winston, 1961

[2]Y. Frishman and A. Tal. Online dynamic graph drawing. IEEE Transactions on Visualization and Computer Graphics, pages 727–740, 2008.

文章

引用

Limei Che, Jie Liang, Xiaoru Yuan, Jianping Shen, Jinquan Xu, and Yong Li. Laplacian-based Dynamic Graph Visualization. Proceedings of IEEE Pacific Visualization Symposium (PacificVis 2015), pages 69-73, (Notes), Hangzhou, China, Apr. 14-17, 2015.