School of Computing, University of Kent, Canterbury, Kent, United Kingdom.
Computer Science Department, Gulf University for Science and Technology, Hawally, Kuwait.
PLoS One. 2018 May 10;13(5):e0197103. doi: 10.1371/journal.pone.0197103. eCollection 2018.
Graph drawing, or the automatic layout of graphs, is a challenging problem. There are several search based methods for graph drawing which are based on optimizing an objective function which is formed from a weighted sum of multiple criteria. In this paper, we propose a new neighbourhood search method which uses a tabu search coupled with path relinking to optimize such objective functions for general graph layouts with undirected straight lines. To our knowledge, before our work, neither of these methods have been previously used in general multi-criteria graph drawing. Tabu search uses a memory list to speed up searching by avoiding previously tested solutions, while the path relinking method generates new solutions by exploring paths that connect high quality solutions. We use path relinking periodically within the tabu search procedure to speed up the identification of good solutions. We have evaluated our new method against the commonly used neighbourhood search optimization techniques: hill climbing and simulated annealing. Our evaluation examines the quality of the graph layout (objective function's value) and the speed of layout in terms of the number of evaluated solutions required to draw a graph. We also examine the relative scalability of each method. Our experimental results were applied to both random graphs and a real-world dataset. We show that our method outperforms both hill climbing and simulated annealing by producing a better layout in a lower number of evaluated solutions. In addition, we demonstrate that our method has greater scalability as it can layout larger graphs than the state-of-the-art neighbourhood search methods. Finally, we show that similar results can be produced in a real world setting by testing our method against a standard public graph dataset.
图形绘制，或自动布局图形，是一个具有挑战性的问题。有几种基于搜索的图形绘制方法，这些方法基于优化由多个标准的加权和形成的目标函数。在本文中，我们提出了一种新的邻域搜索方法，该方法使用禁忌搜索和路径重连来优化具有无向直线的一般图形布局的此类目标函数。据我们所知，在我们的工作之前，这些方法都没有以前在一般多标准图形绘制中使用过。禁忌搜索使用一个记忆列表来通过避免已经测试过的解决方案来加速搜索，而路径重连方法通过探索连接高质量解决方案的路径来生成新的解决方案。我们在禁忌搜索过程中定期使用路径重连来加快识别好的解决方案。我们已经将我们的新方法与常用的邻域搜索优化技术（爬山法和模拟退火法）进行了评估。我们的评估从图形布局的质量（目标函数的值）以及绘制图形所需评估的解决方案数量这两个方面来评估布局的速度。我们还检查了每种方法的相对可扩展性。我们的实验结果应用于随机图和真实数据集。我们表明，我们的方法通过在较少的评估解决方案中产生更好的布局，优于爬山法和模拟退火法。此外，我们证明我们的方法具有更大的可扩展性，因为它可以布局比最先进的邻域搜索方法更大的图形。最后，我们通过在标准公共图形数据集上测试我们的方法，证明了在实际环境中也可以产生类似的结果。
