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.