Research On The Resistivity Measurement Of Plane Network Based On Complex Network Theory

With the rapid development of information technologies, we are surrounded by various complex networks today, such as social networks, traffic networks, power networks, technological networks, communication networks, etc.Facing with the great varieties of complex networks, a central issue lies in front of us:How dependable is a network? How invulnerable is a network when it experiences a negligible fault? How to rebuild it after faults? These are just some basic research problems about the invulnerability of complex networks.Two scientific problems can be proposed naturally:How to measure the invul-nerability of a complex network? How to establish an optimal survivable network? Based on complex network theory, graph theory, statistical analysis and computer simulations, we investigate the invulnerability measures and the optimal models of planar networks in this dissertation, which includes seven chapters.(1) Research based on the strategy of edges failure-the number of spanning trees. The number of spanning trees reflects the communication capability of a network. With the edge-attack probability increasing, the larger number of spanning trees is, the better invulnerability of the network has. We propose a linear algorithm for counting the number of spanning trees in a two-tree network. The result shows that the computation complexity is O(n), which is better than that of the matrix tree theorem with O(n2), where n is the number of steps. Meanwhile, we extend the algorithm and propose a linear algorithm for counting the number of spanning trees in a planar two-connect network and obtain the τ-graph of the corresponding network.(2) Research based on the strategy of edges failure-the reliability polynomial. Let G, G’∈∈Ω(n, e) and assume that each edge of G has the same failure probability q (≤q≤1). If Re(G, q)≥Re(G’, q), then, the bigger the connectivity probability of the G is, the more reliable the network G is, hence the better the invulnerability of the network has. We propose an algorithm for counting the reliability of a planar two-connect network. Using the algorithm, we obtain a uniformly optimal-reliability network model and a uniformly worst-reliability network model.(3) Research based on the strategy of vertex and edge failures-mixed relia-bility polynomial and the number of subtrees of a network. For a given network G ∈ Ω(n,e), assume that each vertex of G has the same failure probability p and each edge of G has the same failure probability q. For G, both vertices and edges are assumed to operate independently. Denote by R(G; p, q) the mixed reliability polynomial of G. Firstly, we give the relation between the mixed reliability poly-nomial and the number of subtrees of the network:if p→ 0, q→1, p+q= 1 and F(G)> F(G’), then R(G;p,q)> R(G’;p,q), where F(G) denotes the number of subtrees of G. The larger the subtree number is, the more invulnerability the graph has. Secondly, we propose an algorithm for counting the mixed reliability polynomial of tree-graphs, and obtain the mixed optimal network and the mixed worst network in trees. Finally, we study the subtree number of a particular type of trees.(4) Research based on a vertex strategy. Through simulations,we analyze the invulnerability of different networks using residual-connected component and average path length measures.