Sampling-based box-covering algorithm for renormalization of networks

Covering a network with minimum number of boxes is critical for using the renormalization technique to explore the network configuration space in a multiscale fashion. Here, we propose a versatile methodology composed of flexible representation and sampling of boxes, which have so far received scant attention, and the strategy of selecting boxes to cover the network. It is exemplified via random box sampling strategies and greedy methods to select boxes. We show that the key to substantially reduce the number of boxes is to give the selection priority to those boxes containing nodes that are not included in boxes bigger than themselves. Our algorithm achieves the improvement of diminishing the number of boxes amounting to nearly 25% compared with these well known algorithms.