A Study Into Complex Networks Through Sampling

Complex systems in real-world can be described as different kinds of networks. A typical network consists of many nodes and edges, in which the nodes represents real-world entities or objects and the edges denotes the relationships between these entities. Generaly, if any two nodes have a certain relationship between them, then there is an edge between them, otherwise there isn't an edge. Nodes that have edges between them are said to be neighbours mutually. For example, neural system can be viewed as a network in which a lot of neural cells are inter- connected through neural fibre; computer network is such a network that many independent computers are connected through communicational devices such as optical fiber cables, twisted-pairs, coaxial-cables etc. There are many other real-world examples such as power supply network, social network, scentist cooperation network, and transportation network etc. Complex network has received more and more research attention from researchers from scientific and engineering fields, and has become a hot research topic. Currently, methods for complex network research include graph theory, random graph, and mean field etc. Researches on complex networks, e.g, small-world network and BA model etc, are mainly focusing on network topologies, and the problems include: 1) what are the result networks when the generating process, topological charateristics such as degree distributions, cluster coefficient are given? What are the topological transitions of the networks? What are the critical parameters of these transitions? 2) Otherwise, how can we construct a network when some specific characteristics are required in the resulted network? In many real-world applications, complex networks are generally very huge, which result in difficulties in analyzing the complex networks, sometimes even make the analysis tasks infeasible. So, many research literatures are focusing on analyzing a small sub-system of the original large complex network for ease of disscusion. However, sometimes their research results are questionable because the sub-system's features may be quite different from its original one. Thus, people hope to obtain the original complex system's charateristics through analyzing those of the sub-systems. In recent years, researchers begin to analyse how to use sampling techniques on original complex systems in order to compare the differences of charateristics and change trends bewteen the original and the sampled ones. On the one hand, existed literatures are only focusing on the comparison of the differences between the original and sampled complex system. They failed in calculating the complex features of the original system through the sampled sug-system, which can be utilized to improve the feasibility and accuracy when analyse the original complex network. On the other hand, complex networks can be divided into random network, small-world network and scale-free network, and different networks have distinct properties. For example, the degree distribution of random network follows Poison distribution with smaller average path length L ~ lnN/k and cluster coefficient C<<1; and small-world network has very similar degree distribution with random network, but it has larger cluster coefficient and smaller shortest path; and the node degree distribution of scale-free network follows the power-law distribution. So, how to choose different sampling techniques on the complex networks in question, so that features of the sampled sub-network are in accord with those of the original network as closely as possible is an important and interesting research topic.Based on above disscusions, the focuses of this thesis are: first, how to use various sampling techniques to sample large complex network system and how to infer the original system's features (e.g., aveage degree, average length of shortest path, cluster coefficient) through analyzing the sampled one; second, sampling techniques selection according to different features of various complex networks. The works of this thesis are summarized as follows:(1) Sampling Analysis on ER Network: Use random sampling technique on ER network, and analyse the relationship between the sampled and original networks; infer the original network's characteristics through the sampled sub-network;(2) Sampling Analysis on BA Network: Based on BA network's feature (unevenly distributed node degrees), use stratified sampling method on BA network, and compare the influences of different sampling methods on accuracy; derive the confidence intervals for complex measure parameters of the original network through analyzing the sampled network's features;(3) Edge based Sampling Method: Based on the BA network node degree's power-law distribution, propose an edge sampling based method for BA networks; Analyse the potential relationship between the sampled and the original BA networks, and derive the characteristics of the original BA network through analyzing the sampled sub-network. Based on the above mentioned work and detailed experimental analysis, the main contributions of this thesis are summarized as follows:·Propose an algorithm named ABS for sampling ER networks based on simple random sampling technique; Compare the corresponding reliability measures for sample ER network and original ER network, and derive some useful properties;·According to the degree distribution property of BA network, propose 2-8 strategy based stratified sampling method named SSBA, for sampling BA network;·Having derived the relationships of related reliability measures between sample ER network and original ER network, utilize Boostrap method to compute confidence intervals for derived results;...