Revisiting Stress Majorization as a Unified Framework for Interactive Constrained Graph Visualization

作者：Yunhai Wang, Yanyan Wang, Yinqi Sun, Lifeng Zhu, Kecheng Lu, Chi-Wing Fu, Michael Sedlmair, Oliver Deussen, and Baoquan Chen

发表：2017 TVCG (InfoVis)

1、动机：

1）图数据应用广泛，需求多样，难以适应

2）没有方法既美观又易读，还能适用于大规模数据

2、贡献：

1） 改进模型：改进stress majorization模型，将其重新构造成一个可自定义约束的通用可视化框架

2）使用方法：给出结合三类约束优化布局的方法

3）相关系统：支持GPU加速，可交互探索10K节点，90K边的图形布局

3、相关工作：

1）Stress model [Kamada 1989]：

2）约束图布局：

3）交互探索（Focus+context）：

- 力引导图直接放大
- 细节图加约束
- 考虑DOI (degree of interest)
- 用鱼眼

4、方法：
1）核心方法：
2）展开并写成矩阵形式：

3）无约束例子：

4）迭代过程：

- 优化方向（D-step）：基于原有方向和新计算的d计算矩阵D
- 计算坐标（P-step）：基于LX=JD计算矩阵X

5）考虑用户定义约束（如集合分离、突出结构等）：

6）三种约束：

- 直接约束

- 度量约束

- 形状约束

</p》

5、评估：

1）对比方法：

- 增量添加约束的IPSep
- 可拓展多功能的SV
- 本方法（不同用户约束权重）

2）对比属性：

- Stress Error (SE)
- Vertical Edge (VE)
- The number of edge crossings (#EC)

3）结果：
效果远优于其他方法。在处理大量数据时速度有优势。

6、总结：

1）未来工作：

- 探究更多的基于形状的约束
- 自动生成权重
- 提高性能，适应大图

2）优点

- 老问题，新思路
- 从模型到方法到系统一条龙
- 方法通用，评估全面