A Max–Min ant colony algorithm for fractal dimension of complex networks

ABSTRACT

The fractal is an important feature of many real complex networks. According to the definition of the Hausdorff dimension, the minimum number of boxes that can be used to cover complex networks is an important factor for revealing the fractal feature of self-similar complex networks. The calculation of the minimum number of boxes is an NP (Non-deterministic Polynomial)-hard problem. In this paper, a heuristic algorithm, named the Max–Min ant colony algorithm, is introduced to approximate the minimum number of boxes. The pheromone-updating rules and heuristic rules are redefined to improve the performance of the algorithm. The experimental results show that, for Escherichia coli networks, the number of boxes was significantly decreased compared to the box-covering greedy algorithm, especially when the box size is small.

KEYWORDS:

• Fractal feature
• self-similar complex networks
• Max–Min ant colony algorithm
• heuristic rules
• box-covering

2010 AMS SUBJECT CLASSIFICATIONS:

• 28A80
• 68T20

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was supported by the National Natural Science Foundation of China [grant numbers 61672124, 61370145, 61173183, 61771087, 51605068 and U1433124]   and the Password Theory Project of the 13th Five-Year Plan National Cryptography Development Fund [grant number MMJJ20170203].