A Max–Min ant colony algorithm for fractal dimension of complex networks. Issue 10 (3rd October 2018)

• Record Type: Journal Article
• Authors: Li, Dongyan; Wang, Xingyuan; Huang, Penghe
• Is Part Of: International journal of computer mathematics. Volume 95:Issue 10(2018)
• Page Start: 1927
• Page End: 1936
• Publication Date: 2018-10-03
• Subjects: Fractal feature -- self-similar complex networks -- Max–Min ant colony algorithm -- heuristic rules -- box-covering; 28A80 -- 68T20; Computers -- Periodicals; Numerical analysis -- Periodicals; Automation -- Periodicals; 004.0151
• DOI: 10.1080/00207160.2017.1364370
• Languages: English
• ISSNs: 0020-7160

Abstract

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.