计算机辅助设计与图形学学报

作者：李政廉, 吉立新, 黄瑞阳, 刘树新

关键词：网络压缩, 幂图, 图搜索, 模块度, 网络可视化

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

来源：2019年第1期

《计算机辅助设计与图形学学报》期刊编辑部

查看计算机辅助设计与图形学学报杂志2019年第1期