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

• 作者: 王勇献 王正华
• 来源期刊: 中国科学（信息科学）
• 关键词: 绘图 布局 超松弛 力导引算法
• 年，卷（期）: 2011,（3）
• 所属期刊栏目: 计算机科学与技术
• 页码范围: 269-282
• 页数: 14页
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王正华	国防科技大学并行与分布处理国防科技重点实验室	72	600	12.0	20.0
2	王勇献	国防科技大学并行与分布处理国防科技重点实验室	26	140	7.0	11.0