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

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

Lossless Compression Algorithm for the Dense Network Graphs

Power graph analysis technique which draws a graph where sets of nodes with common neighbors are shown clustered into modules to compress network graph drastically,is widely used in network graph lossless compression and visualization.However,it is difficult to calculate the optimal power graph.To solve this problem,we propose lossless compression algorithm for the dense network graphs.Firstly,we prove that the optimal power graph problem with single module is a NP-hard,and then extend this conclusion to the generally optimal power graph decomposition; secondly,upon analyzing the existing approaches such as integer linear programming model and constraint programming model,this paper presents a customized search method - the beam search algorithm.By further introducing the backtracking strategy,the algorithm provides a limited heuristic backtracking strategy,and gets better results much faster than well-known heuristic methods; finally,by generating a random scale-free graph,we verify our proposed algorithm.