张 艺，邹晓红

(燕山大学 信息科学与工程学院，河北 秦皇岛 066004)

0 引言

网络的发展带来了图规模的扩大和图数据的激增，由于数据获取技术的误差、数据隐私保护等多种原因导致大量图数据具有不确定性。在不确定图中，顶点表示应用中的实体，边上的概率值表示实体之间存在关系的概率大小。团和极大团被视为图中稠密子结构的核心部分，蕴藏着丰富的知识信息，确定图中极大团的挖掘[1-2]已经无法满足人们对于图数据的需求，因此不确定图中极大团的挖掘成为人们日益关注的焦点。在生物信息学中，高通量生物检测技术存在固有误差使得蛋白质交互是否真实存在具有不确定性，如何从不确定图中挖掘极大团对蛋白质复合体预测非常重要；在无线传感器网络中，能量的耗尽、物理干扰等因素可能对传感器节点之间的通信链路产生影响，两个传感器节点之间的无线通信链路是否真实存在是不确定的；在社交网络中，由于人与人之间的社会关系具有动态性和时效性，加上对个人隐私的保护，网络中两个人之间此时此刻是否存在关系也是不确定的。因此不确定图中的极大团挖掘算法研究在实际应用中具有重要的意义。

近年来，不少学者致力于不确定图的研究，例如紧密子图、高度可靠的子图[3]等，极大团作为众多稠密子图[4-5]中最严格的定义形式，在不确定图中的研究已经取得了一些成果。文献[6]基于不确定性语义提出了极大团概率的概念，而后给出了一种分支界限搜索算法用于挖掘top-k极大团，在划分后的规模较小的扩展子图上应用此算法，极大团挖掘的效率进一步得到了提高[7]；……