本文研究了拓扑图的可靠性及其在移动社会网络中的应用.拓扑图是由点和边构成的几何结构,任何网络都可以抽象成一个拓扑图.随着网络规模的扩大,节点故障是不可避免的.因此,拓扑图可靠性分析就显得特别重要.容错能力是衡量拓扑图可靠的一个重要因素.对故障节点进行快速诊断、定位、修复、移除可以提高系统的鲁棒性和可靠性.移动社会网络作为一个全新的并具有很大潜力的研究领域,近年来得到了许多研究人员的关注.本文运用拓扑图可靠性的研究成果进一步研究了移动社会网络的路由优化和安全问题.首先,本文从容错性能方面研究了拓扑图的可靠性问题.故障容错能力对拓扑图的可靠性起着非常重要的作用.外连通度是衡量拓扑图故障容错能力的一个指标,外连通度保证了拓扑图不连通后的每个分支中节点的数量是不平凡的.本文通过探索正则图的分支容错能力来建立正则图的外连通度.除了通过外连通度对拓扑图可靠性的确定型影响进行研究,本文还在概率模型下通过子图可靠度分析了拓扑图的全局可靠性问题.其次,本文从故障诊断性能角度来探索拓扑图的可靠性.当节点发生故障时,我们需要检测出故障节点并修复或者替换这些节点.关键问题就是怎样通过一个无故障的节点来识别故障节点.一旦故障节点被识别出,就可以对它进行隔离,使得拓扑图的可靠性得到保障.故障诊断通常又分为精确诊断和悲观诊断两类.条件诊断度是一种精确诊断策略,它保证了每个节点的邻居节点不会同时出现故障,从而提高拓扑图的诊断能力.本文分别研究了正则图在PMC模型和比较模型下的条件诊断度.t/m-诊断度是一种悲观诊断策略,t/m-诊断度的基本思想是通过一定数量的误诊节点来提高拓扑图的自我诊断能力.本文研究了在PMC模型下正则图的t/m-诊断算法和t/m-诊断度.最后,本文利用拓扑图的可靠性能研究了移动社会网络的路由优化和安全问题.首先通过探索移动社会网络中用户的社会属性来构造路由优先关系图并分析其正则性.其次,通过路由优先关系图的路径选择获得了移动社会网络的容错数据分发路由.在寻找数据分发路由的过程中,利用路由优先关系图和PMC检测模型提出了一类自适应的恶意用户检测算法.最后,结合路由优先关系图和信任管理机制计算了移动社会网络中用户可信度,从而提出了可靠路由方案.