| 网络图自动绘制的超松弛加速算法 |
| |
| 引用本文： | 王勇献,王正华.网络图自动绘制的超松弛加速算法[J].中国科学：信息科学,2011(3). |
| |
| 作者姓名： | 王勇献 王正华 |
| |
| 作者单位： | 国防科技大学并行与分布处理国防科技重点实验室; |
| |
| 基金项目： | 国家自然科学基金(批准号:60603054); 湖南省自然科学基金(批准号:08JJ4021); 国家重点基础研究发展计划(批准号:2009CB723803)资助项目 |
| |
| 摘 要： | 大规模网络的自动布局与绘制问题近年来得到了广泛的研究,其中基于力导引优化的迭代算法成为最成功的方法之一.传统力导引算法在理论与实践中存在两个困难,一是迭代序列收敛性判定及收敛速度估计在理论上尚不完备,二是针对大型网络使用迭代算法的运行时间开销巨大从而极大地限制了其实用价值.本文对这两方面难题进行了探索,首先基于非线性迭代理论给出力导引优化迭代过程收敛速度估计的一种理论方法,其次基于超松弛加速原理给出加速力导引迭代收敛过程的一种实用启发式方法.通过对基准测试数据及应用中的图实例数据进行的实验结果表明,与现有方法相比,本文的超松弛加速方法能有效降低运行时间开销,平均加速达1.5倍左右.本文最后对下一步工作进行了总结和展望.
|
| 关 键 词： | 绘图 布局 超松弛 力导引算法 |
A fast successive over-relaxation algorithm for force-directed network graph drawing |
| |
| WANG YongXian & WANG ZhengHua National Key Laboratory for Parallel , Distributed Processing,National University of Defense Technology,Changsha ,China.A fast successive over-relaxation algorithm for force-directed network graph drawing[J].Scientia Sinica Informationis,2011(3). |
| |
| Authors: | WANG YongXian & WANG ZhengHua National Key Laboratory for Parallel Distributed Processing National University of Defense Technology Changsha China |
| |
| Affiliation: | WANG YongXian & WANG ZhengHua National Key Laboratory for Parallel and Distributed Processing,National University of Defense Technology,Changsha 410073,China |
| |
| Abstract: | 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 l... |
| |
| Keywords: | graph drawing graph layout successive over-relaxation force-directed algorithm |
| 本文献已被 CNKI 等数据库收录！ |
