随着信息技术的发展，越来越多的领域开始使用“图”来表示和存储数据对象之间的关系。这种类型的数据被称作“图数据”。近年来，在现实应用中积累了大量的图数据，其中蕴含了大量有用的知识。“图挖掘”能够从图数据中发现数据对象之间关系的存在模式、结构特征与形成规律等知识，因而具有重要研究意义。　　在现实世界中，由于数据获取技术的局限、数据不精确性和数据不完整性等原因，数据非确定性在图数据中普遍存在。这种带有非确定性的图数据被称作“非确定图数据”，例如生物信息学中的蛋白质交互网络、无线传感器网络的拓扑结构等。以蛋白质交互网络为例，由于高通量生物实验技术的可靠性不高，因此实验获得的每个蛋白质交互（即网络中的边）未必真实存在，而是具有一定的非确定性，反映该蛋白质交互实际存在的可能性。　　由于在非确定图数据中蕴含着大量有用的知识，因此挖掘非确定图数据（简称非确定图挖掘）具有非常重要的意义。然而，现有的方法无法解决非确定图挖掘问题。一方面，传统的图挖掘算法无法解决非确定图挖掘问题，这是因为：第一、传统图数据模型无法描述图数据的非确定性；第二、传统图挖掘问题的定义在非确定图数据上并不适用；第三、非确定图数据使得挖掘间题的固有计算复杂性大大增加，原有的图挖掘算法无法解决这样困难的问题。另一方面，非确定数据挖掘的研究主要关注于非确定关系数据和非确定XML数据，现有的算法无法处理结构复杂的图数据。目前尚无对非确定图数据的模型、存储、查询、分析与挖掘的系统性研究。　　本文运用算法学和数据挖掘的相关理论、方法与技术，以最小化时间和空间复杂性、最大化挖掘结果质量为目标，研究非确定图挖掘，包括非确定图数据模型、期望语义下的频繁子图模式挖掘算法、概率语义下的频繁子图模式挖掘算法和top-k极大团挖掘算法。主要研究成果如下：　　(1)本文提出了一种非确定图数据模型，其中包括非确定图和非确定图数据库的形式化定义，并对模型的语义进行了严格阐述。另外，本文还对该模型进行了简单的扩展，得到了带标记的非确定图数据模型。这些模型是非确定图挖掘算法研究的基础。　　(2)本文在期望语义下研究了非确定图数据库上的频繁子图模式挖掘，提出了子图模式的期望支持度来评价子图模式的重要性，并在此基础上形式化定义了期望语义下的频繁子图模式挖掘问题。本文严格地证明了该问题是一个NP-难问题，且计算子图模式的期望支持度是一个＃P-难问题。为了降低计算复杂性，本文的方法试图计算一个￡一近似频繁子图模式集合，该集合包含全部频繁子图模式和少量非频繁子图模式，但这些非频繁子图模式的期望支持度低于期望支持度闽值minSUp的比例不得超过E。本文提出的近似挖掘算法实际计算一个(6)一近似频繁子图模式集合，任何频繁子图模式均以较高的概率属于该集合，任意期望支持度低于f1-e)minsup的非频繁子图模式均以较低的概率包含于该集合。真实数据上的实验结果表明该近似挖掘算法非常高效，而且挖掘结果的近似质量也非常高。　　(3)本文在概率语义下研究了非确定图数据库上的频繁子图模式挖掘，提出了子图模式的妒一频繁概率来评价子图模式的重要性，并在此基础上形式化定义了概率语义下的频繁子图模式挖掘问题。本文严格证明了该问题是一个NP一难问题，且计算子图模式的妒一频繁概率是一个#P一难问题。为了降低计算复杂性，本文的方法试图计算一个￡一近似频繁子图模式集合，该集合色含全部频繁子图模式和少量非频繁子图模式，但这些非频繁子图模式的妒一频繁概率不得比(,-频繁概率阈值丁低超过E。本文提出的近似挖掘算法实际计算一个(6)一近似频繁子图模式集合，保证任意频繁子图模式属于该集合的概率不低于《1-6)／2)8，其中s是该子图模式的边数，并且任意妒一频繁概率小于丁-￡的非频繁子图模式属于该集合的概率不高于6／2。本文还在理论上给出了算法参数6的设置方法来保证挖掘结果的近似质量。真实数据上的实验结果表明该近似挖掘算法非常高效，而且挖掘结果的近似质量也非常高。　　(4)本章研究了非确定图上的top-k极大团挖掘问题，提出了极大团概率来评价顶点子集成为极大团的可能性，形式化地证明了该问题是一个NP-难问题。本章提出了一种在多项式时间内计算顶点子集的极大团概率的算法，并在此基础上提出了一种基于分支限界搜索的挖掘算法。该算法采用了多项高效的裁剪技术、新型的搜索策略与预处理技术。真实数据上的实验结果表明本章提出的算法具有很高的效率，并且将该算法用于蛋白质复合体的预测能大大提高预测的精度。