网络图自动绘制的超松弛加速算法

A fast successive over-relaxation algorithm for force-directed network graph drawing

大规模网络的自动布局与绘制问题近年来得到了广泛的研究,其中基于力导引优化的迭代算法成为最成功的方法之一.传统力导引算法在理论与实践中存在两个困难,一是迭代序列收敛性判定及收敛速度估计在理论上尚不完备,二是针对大型网络使用迭代算法的运行时间开销巨大从而极大地限制了其实用价值.本文对这两方面难题进行了探索,首先基于非线性迭代理论给出力导引优化迭代过程收敛速度估计的一种理论方法,其次基于超松弛加速原理给出加速力导引迭代收敛过程的一种实用启发式方法.通过对基准测试数据及应用中的图实例数据进行的实验结果表明,与现有方法相比,本文的超松弛加速方法能有效降低运行时间开销,平均加速达1.5倍左右.本文最后对下一步工作进行了总结和展望.

Force-directed approach is one of the most widely used methods in graph drawing research.There are two main problems with the traditional force-directed algorithms.First,there is no mature theory to ensure the convergence of iteration sequence used in the algorithm and further,it is hard to estimate the rate of convergence even if the convergence is satisfied.Second,the running time cost is increased intolerablely in drawing largescale graphs,and therefore the advantages of the force-directed approach are limited in practice.This paper is focused on these problems and presents a sufficient condition for ensuring the convergence of iterations.We then develop a practical heuristic algorithm for speeding up the iteration in force-directed approach using a successive over-relaxation（SOR） strategy.The results of computational tests on the several benchmark graph datasets used widely in graph drawing research show that our algorithm can dramatically improve the performance of force-directed approach by decreasing both the number of iterations and running time,and is 1.5 times faster than the latter on average.