社交网络及生物网络等许多领域的数据都可建模成边带有存在概率的不确定图。不确定图上的查询与挖掘问题具有广泛应用。目前,不确定图数据查询与挖掘问题面临很多挑战,其中最重要的挑战是计算代价非常高。因为不确定图上的精确查询需要对指数级别数量的实例进行评估,所以即使一个简单的查询问题在不确定图上都成了#P-完全问题。现有的不确定图数据查询与挖掘算法通常基于采样技术。采样技术需要对不确定图的所有可能世界进行随机采样,并在大量获得的样本上进行相关的查询处理,因此计算代价较高。为进一步提高不确定图查询与挖掘问题的效率,本文研究不确定图代表性实例发现算法,即从不确定图的所有实例中找出一个或多个最能代表不确定图期望结构特性的实例。这样可以在这些代表性实例上做查询,进而在很大程度上提高查询效率。本文主要有以下贡献。本文提出基于三角形的代表性实例的概念,其目标是保留不确定图的顶点度分布与三角形度分布。该概念引入了三角形度的结构特性度量,克服了现有方法片面采用顶点度的不足。本文证明寻找基于三角形的代表性实例问题是NP完全问题。本文提出基于三角形的代表性实例发现算法。基于随机边交换的方法,该算法可精确高效地获得不确定图的基于三角形的代表性实例,解决了现有方法查询效率低的问题。本文提出寻找多个代表性实例的算法框架。该框架基于分层采样的思想,用本文提出的两种分层策略和选边策略将不确定图的所有实例集合划分成多个互不相交的子集。通过将该框架与基于三角形的代表性实例算法相结合,提出多个基于三角形的代表性实例发现算法。该算法克服了单个代表性实例算法不能很好地解决概率性查询问题的不足。本文提出一系列基于代表性实例的不确定图查询处理算法,包括顶点度分布查询、顶点三角形度分布查询、三角形计数查询、聚集系数查询、最短路径查询及可达性查询。本文做大量实验来证明基于三角形的代表性实例能准确且高效地解决很多不确定图上的查询问题,如聚集系数查询及最短路径问题。除此之外,多个基于三角形的代表性实例还能有效地解决类似可达性查询的概率性查询问题。