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

论文：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. 图数据应用广泛，需求多样，难以适应

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

贡献

1. 改进模型：改进 stress majorization 模型，将其重新构造成一个可自定义约束的通用可视化框架
2. 使用方法：给出结合三类约束优化布局的方法
3. 相关系统：支持 GPU 加速，可交互探索 10K 节点，90K 边的图形布局

相关工作

1. Stress model [Kamada 1989]：

1. 约束图布局：

2. 交互探索（Focus+context）：

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

方法：

1. 核心方法：

2. 展开并写成矩阵形式：
   

3. 无约束例子
   

4. 迭代过程：

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

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

6. 三种约束：

   • 直接约束

     

   • 度量约束

     

   • 形状约束

     

评估：

1. 对比方法：
   • 增量添加约束的 IPSep
   • 可拓展多功能的 SV
   • 本方法（不同用户约束权重）
2. 对比属性：
   • Stress Error (SE)
   • Vertical Edge (VE)
   • The number of edge crossings (#EC)
3. 结果：效果远优于其他方法。在处理大量数据时速度有优势。

总结：

1. 未来工作：

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

2. 优点

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

---

Questions & Discussion： ✉️ wangxumeng@zju.edu.cn

---