Reliability Analysis Of Topology Graph And Its Applications In Mobile Social Networks

The focus of this thesis is the reliability of topology graph and its applications in mobile social networks (MSNs). Topology graph is a geometric structure composed of nodes and edges. Any network can be abstracted as a topology graph. Node failure would be inevitable with the enlargement of scale of network, and as a result, reliability analysis of topology graph is particularly important. The ability of fault tolerance is an important factor to measure the reliability of topology graph. Rapid diagnosis, location, repair or removal for faulty node can improve the robustness and reliability of topology graph. As a new research field with great potentiality, MSNs have received great attention from many researchers in recent years. This thesis further studies routing optimization and security of MSNs by applying the research results of reliability of topology graph.Firstly, this thesis studies the reliability problem of topology graph in terms of fault tolerance performance. The ability of fault tolerance plays a very important role for the reliability of topology graph. Extra connectivity is a measure index of fault tolerant ability of topology graph, which ensures that the number of nodes of each component is not trivial when it is disconnected. The study explores the combinatorial fault tolerant properties of regular graphs to establish the extra con-nectivity of regular graphs. This thesis not only studies the determined influence of extra connectivity on the reliability of topology graph, but also analyzes the overall reliability problem of topology graph through the subgraph reliability under probability model.Secondly, this thesis explores the reliability of topology graph from the aspect of fault diagnosis performance. We need to detect faulty nodes and repair or replace them when faulty nodes arises. The key problem is how to identify the faulty node through a fault-free node. Once faulty nodes are identified, they can be isolated to guarantee the reliability of topology graph. Fault diagnosis is usually divided into precise diagnosis and pessimistic diagnosis. The conditional diagnosability is an accurate diagnosis strategy, which ensures that each node's neighbors will not be faulty at the same time. Therefore, it improves the diagnostic ability of topology graph. This thesis studies the conditional diagnosability of regular topology graphs under the PMC model and the comparison model, respectively, t/m-diagnosabiliy is a pessimistic diagnosis strategy, the basic idea of which is to improve the self diagnostic ability with a limited number of misdiagnosed nodes. This thesis explores the t/m-diagnosis algorithm and t/m-diagnosability of regular graphs under the PMC model.Finally, this thesis uses the reliability performance of topology graph to study routing optimization and security of MSNs. This thesis first explores social features of users in MSNs to construct the routing priority relation graph (RPRG) and analyzing the regularity of RPRG. This study secondly establishes the fault tolerant data delivery routing of MSNs through the routing selection of RPRG. In the process of looking for data delivery routing, one adaptive detection algorithm for malicious users is proposed by the help of RPRG and PMC detection model. This thesis finally computes the trustworthiness of users by combining RPRG and trust management mechanism, which can be used to propose the reliable routing scheme.