COAST: A Convex Optimization Approach to Stress-Based Embedding
COAST: A Convex Optimization Approach to Stress-Based Embedding
复制标题
COAST：基于应力嵌入的凸优化方法
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Shankar Krishnan
中科院分区：
文献类型：
--
作者：
E. Gansner;Yifan Hu;Shankar Krishnan
使用虚拟物理模型可视化图形可能是实践中最常用的绘制图形的技术。有许多高效且可生成高质量布局的算法。然而，如果要求布局也遵循一组给定的非均匀边缘长度，则基于力的方法就会出现问题，而基于能量的布局就会变得棘手。在本文中，我们提出将应力函数重新表述为两部分凸目标函数，我们可以对其应用半定规划 SDP。我们通过使用图拉普拉斯算子的特征向量对目标函数进行新颖、紧凑的重新参数化，避免了与 SDP 相关的高计算成本。这种稀疏表示使我们的方法具有可扩展性。我们提供的实验结果表明，该方法可以很好地扩展并在处理边缘长度约束的同时产生合理的布局。
Visualizing graphs using virtual physical models is probably the most heavily used technique for drawing graphs in practice. There are many algorithms that are efficient and produce high-quality layouts. If one requires that the layout also respect a given set of non-uniform edge lengths, however, force-based approaches become problematic while energy-based layouts become intractable. In this paper, we propose a reformulation of the stress function into a two-part convex objective function to which we can apply semi-definite programming SDP. We avoid the high computational cost associated with SDP by a novel, compact re-parameterization of the objective function using the eigenvectors of the graph Laplacian. This sparse representation makes our approach scalable. We provide experimental results to show that this method scales well and produces reasonable layouts while dealing with the edge length constraints.