Solving the speed and accuracy of box-covering problem in complex networks
Solving the speed and accuracy of box-covering problem in complex networks
复制标题
解决复杂网络中盒子覆盖问题的速度和准确性
DOI：
10.1016/j.physa.2019.04.242
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
Zhou Mingyang
中科院分区：
文献类型：
--
作者：
Liao Hao;Wu Xingtong;Wang Bing-Hong;Wu Xiangyang;Zhou Mingyang
盒子覆盖法是用最少的盒子覆盖网络的一种方法，它对于证明网络分形和复杂网络的再规范化分析至关重要。此外，人们能够通过分析重新规范化流或将网络分类为几个通用类来研究网络结构。许多引人注目的方法由于时间复杂度高或准确度低而不能很好地适应大规模网络。本文介绍了一种基于最大排除质量燃烧法（MEMB）和随机序列法（RS）的高精度、低耗时的混合方法。我们的方法结合了MEMB方法的特点，搜索尽可能少的盒子与RS方法的高效率，通过选择一些不重要的中心节点，特别是对于大规模的网络。我们还优化了该方法的存储机制，使被排除的大量节点可以有效地更新。在不同结构的真实的网络上的实验表明，该方法的改进是显著的。我们的方法减少了超过40%的MEMB方法的时间消耗，只有10%以上的箱比MEMB方法。
The box-covering method that covers a network with a minimum number of boxes is critical to demonstrate network fractals and the re-normalization analysis of complex networks. Moreover, one is able to investigate the network structure by analyzing the re-normalization flow or categorizing networks into several universal classes. A number of compelling methods are not well adapted to the large-scale networks due to high time complexity, or low accuracy. In this paper, we introduce a hybrid method that has high accuracy and low time consumption based the maximum-excluded-mass-burning (MEMB) method and the random sequential (RS) method. Our method combines the characteristics of the MEMB method that search as fewer boxes as possible with the high efficiency of the RS method by selecting a few unimportant central nodes, especially for large-scale networks. We also optimize the storage mechanism of the method so that the excluded mass of nodes can be updated efficiently. Experiments in the real networks with different structures demonstrate that the improvement of our method can be substantial. Our method reduces the time consumption of the MEMB method by more than 40% with only 10% more boxes than the MEMB method.
登录
查看更多内容
DOI：
10.1103/physreve.89.032814
发表时间：
2014-03
期刊：
Physical review. E, Statistical, nonlinear, and soft matter physics
影响因子：
--
作者：
Jin-long Liu;Zuguo Yu;V. Anh
通讯作者：
Jin-long Liu;Zuguo Yu;V. Anh
DOI：
10.1103/physreve.90.022802
发表时间：
2014-07
期刊：
Physical review. E, Statistical, nonlinear, and soft matter physics
影响因子：
--
作者：
Kazuhiro Takemoto
通讯作者：
Kazuhiro Takemoto
DOI：
10.1016/j.cor.2008.11.020
发表时间：
2009-12
期刊：
Comput. Oper. Res.
影响因子：
--
作者：
Thaddeus Sim;T. Lowe;Barrett W. Thomas
通讯作者：
Thaddeus Sim;T. Lowe;Barrett W. Thomas
DOI：
10.1073/pnas.0709247105
发表时间：
2008-04-01
影响因子：
11.1
作者：
Lacasa, Lucas;Luque, Bartolo;Nuno, Juan Carlos
通讯作者：
Nuno, Juan Carlos
影响因子：
2.4
作者：
Kim, J. S.;Goh, K. -I.;Kim, D.
通讯作者：
Kim, D.