面向强连接网络图的无损压缩算法
|
摘要
幂图分析技术将所有具有相同邻居的节点集合汇聚成单个模块以大幅压缩网络图,被广泛地应用于网络图无损压缩与可视化中.然而获取最优的幂图是难点.针对此问题,提出面向强连接网络图的无损压缩算法.首先,证明了含有单个模块的最优幂图问题为NP难问题,进而扩展为一般地最优幂图问题为NP难问题;其次,在梳理现有整数线性规划模型和约束规划模型等问题的基础上,提出基于回溯策略的波束搜索算法,使有限的回溯策略提供启发信息,比已知启发式方法更快速地得到更优的结果.通过生成的随机无标度图,验证了该算法的有效性.
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.
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.
引文
[1]Newman M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2006,103(23):8577-8582
[2]Holten D,van Wijk J J.Force-directed edge bundling for graph visualization[J].Computer Graphics Forum,2009,28(3):983-990
[3]Holten D,Isenberg P,van Wijk J J,et al.An extended evaluation of the readability of tapered,animated,and textured directed-edge representations in node-link graphs[C]//Proceedings of the IEEE Pacific Visualization Symposium.Los Alamitos:IEEE Computer Society Press,2011:195-202
[4]Nguyen Q,Eades P,Hong S H.On the faithfulness of graph visualizations[C]//Proceedings of the 20th International Conference on Graph Drawing.Los Alamitos:IEEE Computer Society Press,2012:566-568
[5]Hou J H,Chau L P,Magnenat-Thalmann N,et al.Sparse low-rank matrix approximation for data compression[J].IEEETransactions on Circuits and Systems for Video Technology,2017,27(5):1043-1054
[6]Li Huijia,Li Aihua,Li Huiying.Fast community detection algorithm via dynamical iteration[J].Chinese Journal of Computers,2017,40(4):970-984(in Chinese)(李慧嘉,李爱华,李慧颖.社团结构迭代快速探测算法[J].计算机学报,2017,40(4):970-984)
[7]Li Huijia,Li Huiying,Li Aihua.Analysis of multi-scale stability in community structure[J].Chinese Journal of Computers,2015,38(2):301-312(in Chinese)(李慧嘉,李慧颖,李爱华.多尺度的社团结构稳定性分析[J].计算机学报,2015,38(2):301-312)
[8]Liu Shichao,Zhu Fuxi,Gan Lin.A label propagation probability based algorithm for overlapping community detection[J].Chinese Journal of Computers,2016,39(4):717-729(in Chinese)(刘世超,朱福喜,甘琳.基于标签传播概率的重叠社区发现算法[J].计算机学报,2016,39(4):717-729)
[9]Qiao Shaojie,Han Nan,Zhang Kaifeng,et al.Algorithm for detecting overlapping communities from complex network big data[J].Journal of Software,2017,28(3):631-647(in Chinese)(乔少杰,韩楠,张凯峰,等.复杂网络大数据中重叠社区检测算法[J].软件学报,2017,28(3):631-647)
[10]Chen Junyu,Zhou Gang,Nan Yu,et al.Semi-supervised local expansion method for overlapping community detection[J].Journal of Computer Research and Development,2016,53(6):1376-1388(in Chinese)(陈俊宇,周刚,南煜,等.一种半监督的局部扩展式重叠社区发现方法[J].计算机研究与发展,2016,53(6):1376-1388)
[11]Chen Yuming,Miao Duoqian.Searching algorithm for attribute redection based on power graph[J].Chinese Journal of Computers,2009,32(8):1486-1492(in Chinese)(陈玉明,苗夺谦.基于幂图的属性约简搜索式算法[J].计算机学报,2009,32(8):1486-1492)
[12]Varlamis I,Tsatsaronis G.Mining potential research synergies from co-authorship graphs using power graph analysis[J].International Journal of Web Engineering and Technology,2012,7(3):250-272
[13]Royer L,Reimann M,Andreopoulos B,et al.Unraveling protein networks with power graph analysis[J].PLoS Computational Biology,2008,4(7):Article No.e1000108
[14]Dwyer T,Riche N H,Marriott K,et al.Edge compression techniques for visualization of dense directed graphs[J].IEEETransactions on Visualization and Computer Graphics,2013,19(12):2596-2605
[15]Garey M R,Johnson D S.Computers and Intractability[M].New York:Freeman Press,2002:146-167
[16]Yannakakis M.Node-deletion problems on bipartite graphs[J].SIAM Journal on Computing,1981,10(2):310-327
[17]Yannakakis M.Node-and edge-deletion NP-complete problems[C]//Proceedings of the 10th Annual ACM Symposium on Theory of Computing.New York:ACM Press,1978:253-264
[18]Peeters R.The maximum edge biclique problem is NP-complete[J].Discrete Applied Mathematics,2003,131(3):651-654
[19]Erd?s P.On a problem in graph theory[J].The Mathematical Gazette,1963,47(361):220-223
[20]Norvig P.Paradigms of artificial intelligence programming:case studies in Common LISP[M].San Francisco:Morgan Kaufmann,1992
[21]Bollobás B,Borgs C,Chayes J,et al.Directed scale-free graphs[C]//Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms.New York:ACM Press,2003:132-139
(1)Gurobi. http://www.gurobi.com/
[2]Holten D,van Wijk J J.Force-directed edge bundling for graph visualization[J].Computer Graphics Forum,2009,28(3):983-990
[3]Holten D,Isenberg P,van Wijk J J,et al.An extended evaluation of the readability of tapered,animated,and textured directed-edge representations in node-link graphs[C]//Proceedings of the IEEE Pacific Visualization Symposium.Los Alamitos:IEEE Computer Society Press,2011:195-202
[4]Nguyen Q,Eades P,Hong S H.On the faithfulness of graph visualizations[C]//Proceedings of the 20th International Conference on Graph Drawing.Los Alamitos:IEEE Computer Society Press,2012:566-568
[5]Hou J H,Chau L P,Magnenat-Thalmann N,et al.Sparse low-rank matrix approximation for data compression[J].IEEETransactions on Circuits and Systems for Video Technology,2017,27(5):1043-1054
[6]Li Huijia,Li Aihua,Li Huiying.Fast community detection algorithm via dynamical iteration[J].Chinese Journal of Computers,2017,40(4):970-984(in Chinese)(李慧嘉,李爱华,李慧颖.社团结构迭代快速探测算法[J].计算机学报,2017,40(4):970-984)
[7]Li Huijia,Li Huiying,Li Aihua.Analysis of multi-scale stability in community structure[J].Chinese Journal of Computers,2015,38(2):301-312(in Chinese)(李慧嘉,李慧颖,李爱华.多尺度的社团结构稳定性分析[J].计算机学报,2015,38(2):301-312)
[8]Liu Shichao,Zhu Fuxi,Gan Lin.A label propagation probability based algorithm for overlapping community detection[J].Chinese Journal of Computers,2016,39(4):717-729(in Chinese)(刘世超,朱福喜,甘琳.基于标签传播概率的重叠社区发现算法[J].计算机学报,2016,39(4):717-729)
[9]Qiao Shaojie,Han Nan,Zhang Kaifeng,et al.Algorithm for detecting overlapping communities from complex network big data[J].Journal of Software,2017,28(3):631-647(in Chinese)(乔少杰,韩楠,张凯峰,等.复杂网络大数据中重叠社区检测算法[J].软件学报,2017,28(3):631-647)
[10]Chen Junyu,Zhou Gang,Nan Yu,et al.Semi-supervised local expansion method for overlapping community detection[J].Journal of Computer Research and Development,2016,53(6):1376-1388(in Chinese)(陈俊宇,周刚,南煜,等.一种半监督的局部扩展式重叠社区发现方法[J].计算机研究与发展,2016,53(6):1376-1388)
[11]Chen Yuming,Miao Duoqian.Searching algorithm for attribute redection based on power graph[J].Chinese Journal of Computers,2009,32(8):1486-1492(in Chinese)(陈玉明,苗夺谦.基于幂图的属性约简搜索式算法[J].计算机学报,2009,32(8):1486-1492)
[12]Varlamis I,Tsatsaronis G.Mining potential research synergies from co-authorship graphs using power graph analysis[J].International Journal of Web Engineering and Technology,2012,7(3):250-272
[13]Royer L,Reimann M,Andreopoulos B,et al.Unraveling protein networks with power graph analysis[J].PLoS Computational Biology,2008,4(7):Article No.e1000108
[14]Dwyer T,Riche N H,Marriott K,et al.Edge compression techniques for visualization of dense directed graphs[J].IEEETransactions on Visualization and Computer Graphics,2013,19(12):2596-2605
[15]Garey M R,Johnson D S.Computers and Intractability[M].New York:Freeman Press,2002:146-167
[16]Yannakakis M.Node-deletion problems on bipartite graphs[J].SIAM Journal on Computing,1981,10(2):310-327
[17]Yannakakis M.Node-and edge-deletion NP-complete problems[C]//Proceedings of the 10th Annual ACM Symposium on Theory of Computing.New York:ACM Press,1978:253-264
[18]Peeters R.The maximum edge biclique problem is NP-complete[J].Discrete Applied Mathematics,2003,131(3):651-654
[19]Erd?s P.On a problem in graph theory[J].The Mathematical Gazette,1963,47(361):220-223
[20]Norvig P.Paradigms of artificial intelligence programming:case studies in Common LISP[M].San Francisco:Morgan Kaufmann,1992
[21]Bollobás B,Borgs C,Chayes J,et al.Directed scale-free graphs[C]//Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms.New York:ACM Press,2003:132-139
(1)Gurobi. http://www.gurobi.com/