Study On Fractal Dimension Of Complex Networks

Complex networks are widely used to describe the structure of many complex systems in nature and society. Fractal theory is applied to model complex systems. Fractal and self-similarity have been found widely exist in nature. Recently, self-similarity of complex networks has attracted much attention since Song et al. found that a variety of real complex networks consist of self-repeating patterns on all length scales. Fractal dimension is regarded as an intrinsic characteristic used to describe the complexity of a fractal object. Fractal dimension of complex network is an open issue. The main work of this paper is shown as follows:1. This paper studies on the fractal dimension of complex network. Different algorithms of how to calculate the fractal dimension are reviewed and compared. Box dimension algo-rithm is to use the minimal number of boxes to cover the fractal objects. Box dimension algorithm is a widely used tool to calculate the fractal dimension. The main idea of box dimension algorithm is to find the minimum number of boxes used to cover the network, then the fractal dimension can be calculated according to the power law relationship between the number of boxes and the box size. There are two types of box dimension algorithms, one is the box-covering algorithm, the other is the ball-growing algorithm. The difference of them is that there is a center node in every box in ball-growing algorithm, while there is no center node in box-covering algorithm.2. There are two main problems in the existing box-covering algorithms to determine the fractal dimensions of complex networks. On the one hand, there exists randomness, such as randomly ranking the nodes in a sequence or randomly selecting the node as the center, which means their results fluctuate randomly. In other words, it is necessary to apply an average process to obtain a reliable result. The averaging process needs a large amount of time consuming. On the other hand, how to cover a network with the fewest possible number of boxes of a given size belongs to a family of NP-hard problems, which means only approximate solution can be found by an algorithm in an acceptable amount of time. In this paper, the covering ability of box is defined and calculated by using the fuzzy theory. The fuzzy fractal dimension of complex network is obtained by fitting the relationship between the covering ability of box and the box size. The fuzzy fractal dimension algorithm obtains only one exact fractal dimension value with avoiding the randomness and NP-hard problems.3. It is observed that hub repulsion plays an important role in fractal topologies. This paper models the repulsion among the nodes in the complex networks in calculation of the fractal dimension of complex networks. Based on the principle of hub repulsion, the metric in complex networks is redefined and a new method to calculate the fractal dimension of complex networks is proposed. In traditional box-covering algorithm, the distance between any two nodes is the number of edges in the shortest path connecting them. In the proposed method, the hub repulsion force is redefined as the metric in complex networks and the largest hub repulsion force between any two nodes in the box is the box size.