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

摘要：

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

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

所属期刊栏目：31

分类号：TP391.41(计算技术、计算机技术)

资助基金：国家自然科学基金61521003

在线出版日期：2019-03-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：31-38