Research On Scale-Free Networks And Their Applications

With the rapid development of the Internet and the WWW in the past decade, the aspects of information transmission and communication in the modern society are changed, and people's daily work and lives are influenced deeply. Hence, the human society has entered the era of information network. Nevertheless, we know less about the structure and hierarchical organization of the Internet and WWW, such as their global topology, their local properties, and various dynamic behaviors occurring within them. Numerous real network models, such as the Internet, WWW, scientific collaboration network, citation network of scientific papers, national power network, public relation network, ecological web, exhibit the characteristic of complex networks. The complexities of complex networks embody three aspects: complex structure, complex vertices and interactions and influences of various complex properties.The proposition and research of some important complex network models, such as the random graph model, the small-world network and the scale-free network, have arisen the interests of the researchers in the field of physics, mathematics, biology, sociology, engineering, and so on. In the random graph model, the probability connecting each pair of vertices is a constant in the range of O to 1. Many important properties of the model are suddenly emerged. The average shortest path length of the small-world network is the same order of the logarithm of the network size, and the model has a higher clustering coefficient. The network with power-law degree distribution is a scale-free network, and two essential evolving mechanisms of the network are growth and preferential attachment.It is very necessary to study the scale-free network since a lot of real networks have the scale-free property. On the basis of the analysis to the evolving mechanisms of the scale-free network, the accelerated evolving networks based on the Barabási and Albert (BA) network model, Ad hoe network model and the weighted network model are focused on. Then, two effective macro-control methods according to its macro-control principles are put forward and discussed in detail. Finally, the three applications of the scale-free network, which are the community finding of the scale-free network, the optimal cost model of M/Heavytailed/K queue systems, and the data mining system of virtual user network in the Internet, are studied.The main contributions of the dissertation are summarized as follows.(1) The research contents of the scale-free networks are analyzed and summed up to three aspects. The topology structure and evolution of the networks are in the basic level, and its applications are in the top level. The macro-control of the scale-free networks links up its topology structure and its applications and stands in the middle level.(2) The characteristics of evolving rules of the complex networks are discussed. The mode of accelerated attachment by the evolving period is firstly proposed. There are two main classes of accelerated networks, one is the accelerated network by the size of network, and the other is that by the evolving period.(3) A new evolving network based on the scale-free network of BA is studied, and the two accelerated attachments of new edges are presented in its evolving process. The model has both the scale-free characteristic and the small-world property. According to theoretical analysis and numerical simulation, the three reasons of neglecting the accelerated attachment by the evolving period in most of evolving networks are also summarized.(4) A complex Ad hoe network model with accelerated attachment is proposed. The addition probability and the deletion probability are introduced at each time step in the evolving process. Using the continuous approach, it is proved theoretically and numerically that the model follows the scale-free degree distribution and generates both the BA model and the SR (Sarshar and Roychowdhury) model. In addition, the appropriate numerical range of the addition probability, the deletion probability and the coefficient of accelerated attachment are given.(5) There are two fundamental methods constructing the weighted networks, static and dynamic methods. The topology comparison of the static and dynamic weighted networks is given, and the accelerated evolving model of the dynamic weighted networks is emphasized. It implies for the dynamic fashion that, as long as the preferential strength mechanism is adopted in the evolving process, the degree distributions of the weighted networks always follow the power-law distribution and it is not correlative with the original weight definitions.(6) An effective macro-control methods according to its macro-control prin- ciples are proposed. By means of adjusting the ratio between the number of nodes obtained the global information of the network to the sum number of nodes, it is effectively to control the varied scope of the power-law exponent of the network.(7) The algorithms of community finding of the scale-free networks are pre- sented. The selective method of the threshold of Euclidean distance for the spec- trum decomposition of the Laplace matrix is obtained. According to the scale-free property of the virtual user networks in the Internet, the relation between the exponent of power-law degree distribution and the number of communities is pre- sented, and a straightforward and effective criterion evaluating the correctness to detect the community structure has been established.(8) As the important application aspects of scale-free networks, the heavy- tailed distribution is studied. With the cost objective function, the optimal num- ber of servers for the M/Heavy-Tailed/K queue systems is presented with three heavy tailed distributions. The number of servers is optimal to that of system with the average response time as its objective function.