Research On Topological Properties And Construction Method Of Complex Network Based On Algebraic Graph Theory

Complex networks are widespread in nature and human society, which is a complexabstraction of complex systems science. Since the small-world networks and scale-freenetwork models have been proposed, the study of complex networks has become the forefrontof today’s scientific research and hotspots. From mathematics, physics, life sciences, socialsciences to engineering technology, many scholars from different fields began to carry outresearch of complex networks and many aspects of complex network have achieved importantresults, including the complexity and nature of the network topology, network model, networksynchronization, search and other dynamic behavior and network applications. These resultsdeepened people’s understanding of complex networks, revealing hidden in the real worldsome of the universal law. However, compared to the complexity of the network itself, whichis still very limited understanding, a lot of mysteries of complex networks yet wait to berevealed, more empirical analysis and theoretical research work is urgent to be completed, andthe actual field of application is also urgent for mining and exploration.The main work is the research on the nature of complex networks, evolutionary modelsexpand the theoretical study using Cayley graphs and algebraic graph theory, also carried outsome exploration of applications. The main achievements and innovations are as follows:1. Cayley graph is a graph theory model of constructing high symmetry network using afinite group, which has has important applications in interconnection network design. XiaoWenjun and Parhami in2006first proposed Cayley graph and used it as deterministic smallworld network model. Based on the work, this paper carried out formal description andintroduces the minimal Cayley graph as the as the basis of construct small-world networks.By describing the relationship between the minimality of Cayley graphs and small-world, adeterministic small world network approach is proposed based on the expansion of minimalCayley graph structure. The model constructs a kind of small-world networks with highsymmetry. Different with the existing models, this model can construct constant degree ornon-constant degrees networks according to demand and generate network which not only hasa high clustering coefficient and low network diameter, bus also is symmetrical, which has important applications in communication network, P2P overlay networks design topologyfield.2. Currently, many real-world networks has power exponent with2to3, and a lot of studieshave directly assumed to power exponent be greater than2, but this assumption is not entirelyin line with the fact that because there are a lot of network of which power exponent is notgreater than2. Is the network belongs to a class of of special networks, in other words, willthe exponent make different networks show different nature, this problem does not get theattention it deserves. In this paper, we discuss the relationship between the power exponent ofscale-free networks and the network topology in-depth. We set2as a critical point, comparedwith the scale-free network with different exponent about the minimum degree and theaverage degree, and get some new meaningful conclusion.3. Although many studies have concentrated on the nature of scale-free networks, but thedegree sequence length is seldom analyzed and discussed. This thesis discusses the generalscale-free networks characteristics, pointing out, the minimum degree of nodes can be theleast common multiple divisible ofk γ,kγ12,...,kγl, and the sequence length of network hasorder log N, where the network size is N. We calculated the degree of sequence length in alot of real network and validate the conclusions. The property can be further applied to thesearch for scale-free network by improving the maximum degree search algorithm.4. Based on the degree distribution of scale-free networks, utilizing the property of thedegree sequence lenghth. A new scale-free network model is proposed based on the growingof degree sequence. Compared with existing evolution models based on BA, the size ofnetwork is not simply growing, but in accordance with a predetermined degree distribution.This paper describes the two specific growing network models, the scale-free networks modelwith prime numbers and the model with geometric sequence. This approach to modelingnetwork provides a new way of thinking, through some initial parameter settings, you cangenerate a class of scale-free networks with specific degree distribution and adjustable powerexponent.5. Finally, we introuduce the application of cayley small-world model. By appropriatelyextending minimal Cayley graph-butterfly diagram, we propose a new P2P overlay network GBFnet (Generalized ButterFly Network). The network has both symmetry and small world.The nodes and data entry in P2P maps to the identifier space of extended butterfly diagram.To some extent, the model simulates the human social networks and supports the structure ofthe grouping. Theoretical analysis and experimental results show that the network can obtainbetter query performance, also has excellent fault tolerance and robustness.