Solving the speed and accuracy of box-covering problem in complex networks

Hao Liao, Xingtong Wu, Bing-Hong Wang, Xiangyang Wu and Mingyang Zhou

Physica A: Statistical Mechanics and its Applications, 2019, vol. 523, issue C, 954-963

Abstract: 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.

Keywords: Box covering method; Renormalization; Fractal dimension; Statistical properties (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437119306156
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:523:y:2019:i:c:p:954-963

DOI: 10.1016/j.physa.2019.04.242

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().