Two Classes Of Scale-free Networks With Fractal Structure

In this dissertation, we are concerned about two classes of scale-free networks with the fractal structure which means that the corresponding embedded sets are fractal. Two ways of embedding the networks into the plane are defined, moreover, we obtain the Hausdorff dimension of the embedded sets which are recurrent sets or sofic sets. At the mean time, for the first class of networks, we consider the asymptotic property of the mean first passage time. For the second class of networks, Cheeger constant under two different conditions are estimated, when the base graphs are complete, we give the sufficient and necessary condition which ensures that the Laplacian spectral gap is positive.In detail, these two classes of scale-free networks are both generated recurrently by the base graphs according to some rules. Throughout the dissertation, let vertex set of all the base graph be E:={0,1,..., N-1}, the letter set∑are partitioned into two subsets without intersection:letters of type1and type2respectively. Following from this, we can define the word of pure type1and pure type2. Every vertex in n generation network is a word of length n. For the embedding, one way is embedding the total edges into the plane, denoted total-edge embedding; the other is embedding the incremental edges into the plane, denoted incremental-edge embedding.In Chapter3, we introduce a class of hierarchical networks, their base graph is single and complete. In the generation n, the vertex set is all the word in En. As long as the edge set of n-generation network is well defined, the edge set of (n+1)-generation network is defined as follows:copy the n-generation network N times and relabeled the vertices, then link all the words of pure type1and all the vertices of pure type2to each others. We prove the scale-free and small-world property of this hierarchical networks. Also we obtain the Hausdorff dimension of the corresponding embedded recurrent sets by the total-edge embedding method. Then, we consider the estimation of mean first passage time fixed the traps on the words of pure type1or pure type2.In Chapter4, based on the idea of the subshift dynamic system of finite type, we construct another kind of networks, all the base graphs are bipartite, and they own the identical vertex set but maybe not the same edge set. Given a admissible matrix for all the words, in the generating n, the vertex set is all the admissible words of length n. Once the n-generation network is well defined,(n+1)-generation network can be defined as follows:copy the n-generation network N times and relabeled the vertices,remove all the forbidden words, link the words of pure type1and the words of pure type2to each others according to the rules from the base graphs. We prove the scale-free properties under two assumptions. We obtain the Hausdorff dimension of the corresponding embedded sofic sets by the incremental-edge embedding method. Then, we consider the asymptotic properties of Cheeger constant, when all the base bipartite graph are complete, we give a necessary and sufficient condition to make sure this class of networks own the strictly positive Laplacian spectral gap.At last, in Chapter5, we summarize all the conclusions about these two classes of scale-free networks, and raise some unsolved questions for further research.