Study On The Deterministic Models In Complex Networks

The research of a large number of small-world and scale-free stochastic models and the corresponding empirical models in complex networks shows that despite the randomness is the main characteristics of most of the networks, but they are difficult to explain the shaping of complex networks and the interaction between nodes in an intuitive way. And the analysis methods of probability generally used for stochastic model are not suitable for communication networks and circuit networks which are with fixed node degee. Therefore, to construct the models, which are in line with the structure characteristics of realistic networks, with deterministic patterns, has not only important theoretical significance, but also the potential applications. To control the dynamic behavior of complex network system on the basis of the deterministic models is a frontier problem of complexity science, and it is also the ultimate goal for the research of complex network systems. The existing exactly controllability theory of complex network systems based on the linear vertices shows that the minimum number of controller required for the complete control of complex network system is determined by the maximum multiplicity number of eigenvalues of the adjacency matrix of the network, because the adjacency matrix of the deterministic models is symmetry and regularity, and all the eigenvalues can be deduced strictly, so that the analytic solutions of controllability of the deterministic models can be obtained, and all the nodes which are used for the control are determined precisely. The main advantage of the deterministic models is that we can derived the analytic solutions of structural characteristics just by theorical manner, thus the study of deterministic models have attracted the attention and interest of researchers. The research on the deterministic model can promote the research of stochastic model and actual network of complex networks, so that this dissertation focused on the research of deterministic models.This dissertation firstly proposes a new deterministic growth model, all the nodes in which are arranged in a line, a new node is inserted between two old nodes, then to connected it to the two end nodes. We obtained the analysis solutions of some structural properties of the network model, the results show that the degree distribution of the network obeys exponential distribution; clustering coefficient is tending to In2; the network degree distribution characteristics and the average path length reveal that the new models are small-world networks.Then, we introduce an informative labelling method for vertices in a family of Farey graphs, and deduce a routing algorithm on all the shortest paths between any two vertices in Farey graphs. The label of a vertex is composed of the precise locating position in graphs and the exact time linking to graphs. All the shortest paths routing between any pair of vertices, which number is exactly the product of two Fibonacci numbers, are determined only by their labels, and the time complexity of the algorithm is O(n). It is the first algorithm to figure out all the shortest paths between any pair of vertices in a deterministic graph.We also focused on the average path length of a family of edge iteration models. The generation method of these models is to add the triangle network modules to the active edges of the network. Different deterministic models can be derived from similar but different generation mechanisms, such as whether it contains the active edge, or the initial super active edges. In this dissertation, we derived analytic solutions of the average path length for those models; the forms of the solutions are complicated but accurate. The conclusion can be applied to a family of deterministic edge iteration networks with the infinite number of nodes.Then, based on the vertex labelling and the shorest path routing algorithm of Farey graphs, we introduced a labelling for every vertices in two edge iteration models, in which the three initial edges are super active edges or all the edges are active edges, then we derived the shortest path routing algorithms for them just on the basis of their vertex labels. Although the two edge iteration models have sophisticated spatial topological structures, the time complexity of the shortest routing algorithm is the same as the shortest routing algorithm of Farey graph and it is also with linear time complexity. The shortest path route of this dissertation is the generalization of the conclusion of related literature. For example, the algorithm of the case of m= l in extended edge iteration model is exactly the case of d=1 in the expanded Apollonian network, and the algorithm of the case of m=1 in edge iteration model, in which all the edges are active edges, is the case of q= 2 in recursive clique tree. It should pointed out that the shortest routing algorithm in the references is able to determined only one of the shortest paths, while the proposed method in this dissertation can be used to determine all the the shortest paths between any pair of nodes.This dissertation also studied the Koch evolution networks which are mapped by the polygon Koch fractal islands and we also give an effective method to label vertex of Koch networks. On the basis of the vertex lablels, we derived the main topological properties of Koch network including the degree distribution, the shortest path routing, average path length, clustering coefficients, the betweenness of.vertex and edge, and so on. The results show that:1) the structure properties of Koch network are determined by the generation method of fractal, which are not determined by the edge number of the polygon.2) Koch network is a scale-free network, the exponential index belongs to (2,3]; the network has small-world property, the average shortest path length is in proportional with network size; the networks have high clustering coefficient; the network diameter is in proportional with network size; the degree correlation function is decreased with the node degree, that is to say, the node with higher degree is tended to link to nodes with smaller degree, i.e. Koch network is inhomogeneous; the betweenness of nodes and edges are exponential with degree.3) The Koch network in some refences is just the special case m= 3 of this dissertation.In the last chapter, we first extended the famous scale-free deterministic model proposed by Barabasi to an general scale-free deterministic model, then analyzed spectra of the adjacency matrix of the extended model, we proved that when the number of the nodes tends to infinity, the needed ratio is (m-1)/(m+1) for exactly controlled the new model, where m is a positive integer. Then, all the eigenvalues of the adjacency matrix of the nearest neighbor connection model are deduced, we proved that the exactly controllability of the model depends on several parameters of the network. The Kronecker model is a kind of deterministic model which is generated by Kronecker product of an initial matrix. We proved its controllability depends only on the initial adjacency matrix, for the eigenvalues of Kronecker product network is polynomial expansion of the eigenvalues of the initial adjacency matrix.