Research And Applications Of Some Characteristics In Complex Networks

Since the discovery of small-world phenomenon of real networks by Watts and Strogatz, Complex Networks have absorbed some related theories and achievements in the graph theory, engineering mathematics, computer science and social science, and have become an independent discipline. After more than ten years of research, scientists have found a series of typical Complex Networks model such as the Small-world Networks, Scale-free Networks, and Deterministic Small-world Networks and so on. At the same time, scientists also have found many characteristics of those networks. From the small-world phenomena perspectives, the thesis focused on those typical networks characteristics and their applications, which included length of vertex degree sequence and resistance distance. As those networks based on Cayley Graph of Algebraic Graph Theory have the small-world characteristics by added randomly edges. The thesis analyzed the requirements of wireless sensor networks and data center networks, and proposed two Cayley graph models based on Algebraic Graph Theory, and which are characterized by small-world characteristics. The main four contributions of the thesis are as follows:First, Xiao et al. have found a new characteristic of vertex-degree sequence length in Complex Networks; it is that vertex-degree sequence length l is the same order of log₂N, the thesis proved the characteristic in Complex Networks followed the extended power-law distribution, Poisson distribution and exponential distribution. After conducting a lot of experiments, we have found that typical Complex Networks are characterized by the new characteristic. The conclusion can explain that why the diameter of real networks is small, which can be the main characteristic of Complex Networks. Moreover, the thesis proposed the Complex Networks model based on the degree sequence length. Based on our analysis on the search in Complex Networks, the thesis proposed the search algorithm based on the maximum degree, and then finished a lot of the simulate experiments, the result shows that the search algorithm based on the maximum degree is more effective than the search algorithm based on the shortest path.Second, the thesis proposed the community detection algorithm based on the vertex-centrality with the resistance distance after analyzed resistance distance of typical Complex Networks and it’s applications in the community detection, we conduction experiments to validate our detection algorithm on simulate network P, Zachary network and dolphins network with vertex-centrality features including the vertex-degree centrality, proximity, eigenvector, clustering coefficient and the shortest path. Moreover, the thesis analyzed the Fast Newman（FN） algorithm and Kernighan-Lin（KL） algorithm with the resistance distance, all results show that the algorithm based on vertex-degree centrality and resistance distance, the KL algorithm based on resistance distance are perfectly work. However, community detection about those three networks is not correct by the other algorithms.Third, inspired by the small-world characteristic of the Complex Networks, the thesis aim to shed some theoretical light on the Cayley graph of algebraic graph theory and Complex Networks theory. For the requirements of the virtual route protocol in the wireless sensor networks, the thesis proposed a new CayleyDHT model of the wireless sensor networks based on Cayley graphs theory and Complex Networks, the CayleyDHT model is characterized by small-network characteristic.Moreover, the thesis also proposed the CayleyDHTVCP routing protocol. The simulate experiments show that the protocol is more effective and robust than VCP routing protocol.Finally, now data center networks are constructed by some inexpensive hardware. Based on our analysis on the advantages and disadvantages of the current construction of data center networks, we proposed the new data center network model that is called C³ Cube model, which based on Cayley graph of algebraic graph theory and Complex Networks theory, and then presented the routing protocol and fault-tolerant protocol based on C³ Cube model. The simulate experiments show the validity of the protocol and indicated that we can construct data center networks using some inexpensive equipments.