面向强连接网络图的无损压缩算法

• 作者: 刘树新 吉立新 李政廉 黄瑞阳
• 来源期刊: 计算机辅助设计与图形学学报
• 学科: 工学
• 关键词: 网络压缩 幂图 图搜索 模块度 网络可视化
• 年，卷（期）: 2019,（1）
• 所属期刊栏目: 图形与可视化
• 页码范围: 31-38
• 页数: 8页
• 分类号: TP391.41
• 字数: 7781字
• 语种: 中文
• DOI: 10.3724/SP.J.1089.2019.17036

摘要

幂图分析技术将所有具有相同邻居的节点集合汇聚成单个模块以大幅压缩网络图,被广泛地应用于网络图无损压缩与可视化中.然而获取最优的幂图是难点.针对此问题,提出面向强连接网络图的无损压缩算法.首先,证明了含有单个模块的最优幂图问题为NP难问题,进而扩展为一般地最优幂图问题为NP难问题;其次,在梳理现有整数线性规划模型和约束规划模型等问题的基础上,提出基于回溯策略的波束搜索算法,使有限的回溯策略提供启发信息,比已知启发式方法更快速地得到更优的结果.通过生成的随机无标度图,验证了该算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘树新		28	119	6.0	10.0
2	吉立新		32	81	5.0	7.0
3	黄瑞阳		50	146	7.0	8.0
4	李政廉		5	4	1.0	2.0