论文：HOLA: Human-like Orthogonal Network Layout

作者：Steve Kieffer, Tim Dwyer, Kim Marriott, and Michael Wybrow

发表会议：TVCG 2015

这篇文章设计了一种计算正交网络布局的自动化算法。重点在于，使用这种算法得到的布局能与用户手工绘制得到的结果在结构、布局上保持相似，使其更贴近用户的审美、认知观念。

img

img

文章主要按算法设计过程的先后顺序分为三个部分介绍：

  1. 用户调查

此步骤为算法设计的构成性步骤。在此阶段，需要被试手工改进若干幅正交网络图的布局。通过这些结果，总结出贴近用户的 9 条设计原则，并将这 9 条原则运用到下一步的算法设计当中。

  1. 算法设计

根据上一步的到的 9 条设计原则对算法进行设计。整个算法共分为四步：

    - 图拓扑结构的分解：将图结构分解为外围的多个树结构与中间的唯一核心结构
    - 核心结构布局：将中间的核心结构进行正交化布局
    - 外围的树结构布局：将所有分解下来的树结构进行正交化布局，并将其重新插入核心中
    - 最终调整：对图中不合理的位置进行最终优化
  1. 最终评估

此步骤为算法设计的总结性步骤。此步骤将 HOLA 算法得出的结果与人工绘制结果、另一个 yFiles 自动化布局算法结果进行对比，让被试做一系列评估测试。最终得到结论，HOLA 算法得到的结果无论在美观、实用性上都明显优于 yFiles 算法结果，并且其布局质量能与手工结果的质量不相上下。

与此同时，可以看到，作者采用的整个算法设计方法也是前所未有的创新。在进行算法设计前后分别进行一次用户调查：一次为构成性的用户调查，为算法设计过程提供输入；一次为总结性的用户调查，对算法最终得到的结果进行评估。可以说，整个设计方法是以用户为中心的，充分体现了用户在这个过程中的重要性。

综上，本文的主要贡献主要可以分为三点：

  1. 提出了 9 条贴近用户审美、认知的正交网络布局原则

  2. 设计了一个显著有效的正交网络布局自动化算法

  3. 运用了以用户为中心的设计方法进行算法设计


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