Research On The Network Reliabilitybased On Network Entropy

Network has been widely found in our life in the forms of traffic network, communication network, logistics network, WWW network and the like. In recent years, a variety of unexpected events or accidents have occurred frequently and already resulted in huge economic losses and casualties. Thus, a series of severe problems have emerged accordingly. How reliable are these networks? Are minor accidents likely to lead to collapse of the entire network system? Do these networks still function properly under serious natural disasters or sabotage by hostile forces? The problems in question are just involved the study of network reliability, recognized as a significant research domain.The main contents of this paper are arranged as follows:(1) As for the concepts of two-terminal connectivity reliability, K-terminal connectivity reliability, and all-terminal connectivity reliability, they are universally described as the probability of connectivity between "a given sum of nodes”, which does not work in practice for general networks. In addition, the standard network structure entropy has served as one of the index measuring network heterogeneity, but it gives no consideration to the impact of isolated nodes on the network structure. Therefore, based on network structure entropy and standard network structure entropy, the author proposes the concept of network connectivity entropy and further verifies the rationality of applying standard network connectivity entropy to measurement of network connectivity reliability. That is, the smaller the standard network entropy, the weaker the network connectivity reliability, and vice versa. Thus, it becomes possible to compare network connectivity reliability between different networks based on standard network connectivity entropy. Furthermore, the impaired metro network of Nanjing city is exemplified to demonstrate the validity and practicability of network connectivity reliability.(2) Since the standard network connectivity entropy contains log, we have no way but to turn to computers which are utilized to compare reliability of different networks. To overcome this bottleneck, this thesis initiates the concept of network transformation and judgment theorem of network connectivity reliability. According to this proposed theorem, the network connectivity reliability can be compared between different networks quickly. In addition, as for a network with n nodes and k connected sub-graphs, the number of nodes that each connected sub-graph contains is figured out when network connectivity reliability reaches maximum or minimum value, respectively.(3) During the process in which network’s edges and nodes are growing, their growing pattern is traced when network connectivity reliability reaches the maximum value and minimum value separately. In conclusion, as for the edges in growth, the network connectivity reliability reaches the maximum if the 1st and the 2nd connected sub-graphs are connected. On the contrary, it reaches the minimum if the k-th and the k -1-th connected sub-graphs are connected; as for the nodes in growth, the network connectivity reliability reaches the maximum if newly-developed node and the 1st connected sub-graphs are connected and reaches the minimum if the newly-developed node and the k-th connected sub-graphs are connected.(4) In order to estimate the network reliability, the network maximum flow entropy together with the shortest path entropy is put forward by referring to traditionally- defined network entropy. That is, the smaller the network entropy, the stronger the network reliability, and vice versa. Besides, a detailed discussion is followed on how a network’s maximum flow entropy and shortest path entropy will change as its edges grow. As the results show, if the length of network shortest path remains the same before and after these edges grow, the network reliability will become unchanged or stronger; if the length of network shortest path is not the same, the network reliability will become stronger or weaker. It is the same case for maximum flow entropy of the network. Finally, a percentage grading system concerning network reliability is suggested based on network’s maximum flow entropy and shortest path entropy.All in all, this thesis focuses attention on research of network reliability and attempts to provide useful guidance and constructive suggestions both in theory and in practice.