Researches On Fractal Networks:Theory,Algorithm Applications

Complex networks are the abstraction and the important research tool of complex systems. Research on the topological structure of complex networks is one of the most basic and most important aspects. In 2005, Song et al published a paper on the "Nature" magazine, by introducing the renormalization group analysis on complex networks, it reveals many real-world networks have fractality and self-similarity properties. Since then, fractality have become an important research direction of the complex networks. Researcher mainly focuses on the following aspects:origins of fractality, definition of fractality, algorithms for fractality, properties of fractal networks, etc. This paper stud-ies the fractality on complex networks from 3 aspects:the origin of fractality, fractal algorithms and the application of fractal theory. The main content and innovations of this dissertation are shown as follows:(1) We proposed a novel dynamical growth model for fractal networks. The gen-erated networks of this model are the counter-examples of former beliefs of the origin of fractality on complex networks. It is widely believed that fractality of complex net-works originate from hub repulsion behaviours. This hypothesis was demonstrated by a dynamical growth model, which evolves as the inverse renormalization procedure, pro-posed by Song et al. Now we find that the dynamical growth model is based on the assumption that all the cross-box links have the same probability e to link to the most connected nodes inside each box. Therefore, we modify the growth model by adopt-ing the flexible probability e, which makes hubs to have higher probability to connect with hubs than non-Hubs. With this model. we find that some fractal and scale-free networks have hub attraction behaviours (correlation or assortativity). Actually, the real-world collaboration network of movie actors also is fractal and shows assortative mixing. Therefore, we propose the structure equilibrium to explain the emergence of fractality. Furthermore, we deduce the origin of fractality based on the mathematical framework of random networks, we found that it requires the distribution of the shortest distance follows the Frechet distribution.(2) We proposed two novel box-covering algorithms for fractal dimension, which can obtain more precise solutions. Researchers have widely investigated the fractal property of complex networks, in which the fractal dimension is normally evaluated by box-covering method. The crux of box-covering method is to find the solution with minimum number of boxes to tile the whole network. At first, we introduce a differential evolution box-covering algorithm based on greedy graph coloring approach. We apply our algorithm on some benchmark networks with different structures. Experimental results demonstrate that our algorithm can get better results than state of art algorithms in most cases. At second, to reduce the time complexity and search space, we introduce a particle swarm optimization box-covering algorithm based on discrete framework. Experimental results show that our algorithm is effective and promising.(3) We present a multiobjective particle swarm optimization box-covering algo-rithm with the objectives as:minimizing the box number and maximizing the fractal modularity. Based on the scaling theory, researchers analyse the statistical properties of the networks on different length scales by the renormalization group analysis method. Thus, it has been found that the fractal modularity is strongly related to the infor-mation transportation. Thus, maximizing the fractal modularity is important in the box-covering method. However, all the current box-covering algorithms regard the box number minimization as the only objective. We noticed that some part of the objective maximizing the fractal modularity is conflicted with the objective of minimizing the box number. Therefore, to solve the dilemma of minimizing the box number and maximiz-ing the fractal modularity at the same time, we present a multiobjective particle swarm optimization box-covering algorithm. We apply the decomposition approach on the two objectives to approximate the Pareto Front. The experimental results show that our algorithm is better on both objectives compared with the state-of-the-arts algorithms. Besides, the box-covering results we obtain is more similar to the hierarchical structure of the real-world networks than other algorithms.(4) We conducted an empirical study on the social coding network of GitHub. At first, as in the GitHub platform, there are many large projects, where many developers do not have real collaboration activities. We introduce the power of links to remove the weak links in the network. Based on the renormalization group analysis, we found the network transfers from small-world to fractal network when we removed the weak links. Furthermore, by analysing the Pearson correlation coefficient and neighbour con-nectivity, the fractal networks formed by strong links are assortative mixing is found. It enhances our former conclusion on the origin of fractality. At second, we apply the hypernetwork model to investigate the time evolution of the GitHub network. Based on the statistical analysis results, we propose a novel dynamical growth hypernetwork model, which considers the diversity of knowledge, and we apply the combination of hyperdegree base preferential attachment and knowledge stock base preferential attach-ment. Experimental results show that our model has a good simulation of real-networks.