随着科学技术的迅猛发展,图结构越来越广泛地被应用于各行各业的数据挖掘和分析中。图结构抽象了事物之间的关系与联系,为人们的研究分析提供了便利。结构聚类作为一种重要的图结构数据的分析挖掘工具,不仅可以找出网络中稠密连接的簇,还可以识别其中的离群点与中介点,从而更好地理解图中各点的角色与它们之间的关系。现有的结构聚类研究主要是针对确定图的,即图上的点与边都确定存在。然而在科学研究与现实生活中,由于种种原因,许多的关系存在不确定性。例如社交网络中受个人隐私保护影响的不确定关系、生物网络中受实验因素影响的不确定关联、移动点对点网络中受环境影响的不确定连接等。这些不确定性通常需要使用不确定图(概率图)来表征。为此,需要考虑不确定图上的结构聚类问题。然而,现有的确定图上的结构聚类算法往往不能准确地表征不确定图上的连通关系。因此,在本文中,我们提出了一个不确定图上的结构聚类算法问题,目的是找出一个给定的概率图上的可靠结构聚类,并给出了它的形式化定义。在此基础上,设计并实现了一个不确定图上的结构聚类求解算法。具体地,本文首先对不确定图上的结构聚类算法问题的定义进行了研究。分析总结了现有的确定图上结构聚类问题模型,从而推广出不确定图上的结构聚类算法的问题定义。不同于确定图上的结构聚类,本文的结构聚类问题依赖于一种全新定义的概念——可靠结构相似度。可靠结构相似度度量了概率图上两个节点之间的结构相似的概率。从而可以用一个概率来衡量节点之间的相似性。随后,由于可靠结构相似度的求解是一个比较困难的问题,直接求解具有很高的时间复杂度,是不可取的。为此,本文详细分析了可靠结构相似度的求解过程,并在此基础上设计了一种基于动态规划思想的求解算法。该算法能够快速地求解可靠结构相似度问题,在该算法的基础上,本文根据目前最好的确定图上结构聚类算法,设计出不确定图上结构聚类算法框架。为了进一步加快我们算法的速度,我们设计了多种强有力的剪枝和优化措施。最后,我们使用了五个真实的数据集对我们所提出的算法进行了较为全面的研究与分析。通过与现有聚类算法的比较,我们的算法可以得到更好的不确定图上的聚类。同时,通过性能分析,我们验证了优化措施的有效性。综合实验的结果,得出我们的算法能够有效且高效地完成不确定图上的结构聚类问题。