图作为建模大规模网络的通用数据结构一直以来受到了学术界的广泛关注,比如交通网络、社交网络、生物网络、协作网络和通信网络等都可以抽象为图。由于数据采集和处理过程中随时可能出现的噪声和误差,这将会导致图数据具有不确定性。于是,最近学术界开始关注不确定图中的社区挖掘问题。不确定图是在确定图的基础上增加了概率维度,它能够表达更丰富的语义并且能更好的表示数据本身固有的不确定性。但是由于不确定图中概率维度的增加,这也会导致确定图中的研究成果不能直接应用于不确定图。基于以上背景,本文重点研究不确定图中基于k-median和k-center聚类的社区发现问题以及不确定图中考虑节点影响力的社区搜索问题。针对不确定图中基于k-median和k-center聚类的社区发现问题,本文分析了这些问题的难度,并提出了比现有研究具有更佳近似比保证的算法。具体来说,本文所提算法为k-median问题提供(1-1/e)近似比保证,为k-center问题提供(OPTkc)近似比保证,其中OPTkc是k-center的最优目标函数值。此外,本文所提算法还结合了几种优化方法,可显著提高其实际运行效率。大量的实验结果表明,本文所提算法在运行效率和返回解的质量上均明显优于现有方法。针对不确定图中考虑节点影响力的社区搜索问题,目前关于这方面的研究都只考虑到了在确定图中的情况。本文基于(k,η)-core的概念提出了一种新颖的社区模型,称为influential(k,η)-commiunity。基于这个新的社区模型,本文提出了一个在线搜索算法SearchIC。大量的实验结果表明,本文所提算法比现有的在线搜索算法在运行速度上要快好几个数量级。