随着现代化数据采集技术的快速发展，各行各业中都积累了大量用图表示的数据，这些图数据规模不仅巨大，而且还在不断地快速增长^[1]。如何在大规模的图数据中快速准确地找到重要的信息，具有十分重要的现实意义和商业价值。极大团是稠密子图的一种，极大团枚举（maximal cliques enumerate，MCE）用于从给定图中挖掘不被其他团包含的完全子图^[2]。MCE作为一个基本的图数据挖掘问题，应用场景非常多^[3]，例如社交网络中发现重叠社区^[4]，可进行好友推荐和广告推广^[5-6]，蛋白质交互网络（protein-protein interation networks, PPI）中发现不同蛋白质之间的关系，可用于生物研究和制药等^[7–9]。

在现实生活中，由于采集数据过程中的噪声^[10]、测量误差^[11]、预测的准确性^[12]及隐私问题^[13]导致抽象出的图具有不确定性，这种不确定性数据构建的图模型称为不确定图^[14]。由于不确定图上的概率维度的增加，这也会导致确定图上的研究成果不能直接应用于不确定图^[15]，而现有的$ \mathrm{M}\mathrm{C}\mathrm{E} $算法所关注的大多是精确和完备的确定图^[16]，因此亟须研究不确定图上的$ \mathrm{M}\mathrm{C}\mathrm{E} $问题。

围绕不确定图数据挖掘，学者们做出了很多研究，如朱鎔等^[17]研究了不确定图上挖掘稠密子图的问题，邹兆年等^[18]研究了不确定图上挖掘频繁子图模式的问题，相关学者研究了不确定图上的$ \mathrm{M}\mathrm{C}\mathrm{E} $问题^[19–24]。关于不确定图上$ \mathrm{M}\mathrm{C}\mathrm{E} $问题的研究，现有的不确定图中极大团挖掘算法通常采用裁剪策略和基于MULE（Maximal Uncertain Clique Enumeration）算法的递归回溯思想^[25]。其中，$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法是基于顶点编号升序处理的求解办法，总的时间复杂度是$ O\left(n\cdot {2}^{n}\right) $，$ n $为顶点数量，但当图的规模更大时，时间效率会降低。由于$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法是自底向上的方法，在枚举团时会引入多余的工作，为了提高效率，$ \mathrm{R}\mathrm{a}\mathrm{s}\mathrm{h}\mathrm{i}\mathrm{d} $等^[21]提出了一种自顶向下的枚举算法，实验证明在本身就稠密的图上该算法与具有相同理论复杂度的其他算法相比，时间快了30%。但是在稀疏图上，时间性能有待提高。基于此算法，Li等^[20]提出了基于核的剪枝算法，并就这些剪枝技术改进出新的算法来枚举所有的$ \left(k,\alpha \right)-\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{l}-\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{s} $（$\alpha $为概率阈值；k为顶点个数），该算法时间复杂度为$ O\left(n\cdot {2}^{l}\right) $，$ l $是顶点数量，其规模远小于原图顶点数量$ n $，跟$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $相比，时间效率有所提升，但处理大规模图时仍然很耗时。

由上述分析可知，目前不确定图尤其是大规模不确定图上的$ \mathrm{M}\mathrm{C}\mathrm{E} $问题依然需要解决时间效率问题。因此，本研究提出，构造$ \alpha $不确定图，以减小图的规模；提出了基于该图的高效枚举算法（multiple inversion list enumerate uncertain maximal cliques，MILEUMC），该算法分为“子图划分—枚举—验证”。先将$ \alpha $不确定图划分为规模更小的极大团子图，在极大团子图上用经典的枚举算法$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $枚举所有的$ \alpha $-极大团，在验证极大团时，本研究提出了基于多重倒排表的验证方法，实现了用去重和去包含关系完成去除伪极大团的工作。在每部分使用不同的多重倒排表可以缩减验证的工作量，并且正确地找到并去除伪极大团，从而提高时间效率。

在本研究中，分别定义了不确定图模型、团相关内容和研究的问题；构造$ \alpha $不确定图，并说明了在$ \alpha $不确定图上划分子图的作用和在该图上枚举的正确性；提出了$ \alpha $不确定图上枚举及高效验证算法$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $，以具体的实例说明枚举和验证极大团的过程，展示出所有的算法描述，并对其进行分析；实验证明，使用可表示不确定图的7个数据集，对所提出的算法进行3种实验，证明了算法的高效性；对本研究内容作出总结，并提供未来不确定图上枚举极大团可研究的相关方向。

1.   基本定义

本节介绍关于不确定图模型、极大团相关研究问题的定义。

1.1   不确定图的定义

给定无向不确定图$ {{G}}=\left({{V}},{{E}},{{P}}\right) $，其中，$ {{V}}= \left\{{v}_{1},{v}_{2},\cdots ,{v}_{n}\right\} $，表示不确定图的顶点集合，$ {{E}}= \left\{{e}_{1}, {e}_{2},\cdots ,{e}_{m}\right\} $，表示不确定图的边集合，$ P $表示图中边的不确定性，以权值的方式给出，取值为$ P\in \left(\mathrm{0,1}\right] $。图1为一个不确定图模型。

图  1  不确定图

Fig.  1  Uncertain graph

下载: 全尺寸图片

1.2   团的定义

给定无向确定图$ {{g}}=\left({{V}},{{E}}\right) $，$ {{C}} $为顶点集合，若$ {{C}}\subseteq {{V}} $，且${{ C}} $中任意2点间均有边相连，则C为团。如图2，$ {{{C}}}_{1}=\left\{\mathrm{1,2},\mathrm{3,4}\right\} $，$ {{{C}}}_{2}=\left\{\mathrm{2,4},5\right\} $，$ {{{C}}}_{1} $和$ {{{C}}}_{2} $都是团。

图  2  确定图

Fig.  2  Deterministic graph

下载: 全尺寸图片

1.3   团规模的定义

给定一个团$ { {C}} $，${ { C}} $中包含的顶点数量即为团规模的大小。可以表示为$ \mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}\left({ {C}}\right) $。

1.4   成团概率的定义

给定不确定图$ { {G}}=\left({ {V}},{ {E}},{ {P}}\right) $，对于图$ { {G}} $中的任意一个团$ { {C}} $，成团概率$ p\left(\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{q}\left({ {C}}\right)\right) $是指连接团$ { {C}} $中所有顶点的边的概率之积。即

例如，在图1上，团$ {{ {C}}}_{1}=\left\{\mathrm{4,5},6\right\} $的成团概率$ p\left(\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{q}\left({{ {C}}}_{1}\right)\right)=0.8\times 0.9\times 0.9=0.648 $。

1.5   $ \alpha $-极大团的定义

给定无向不确定图$ { {G}}=\left({ {V}},{ {E}},{ {P}}\right) $和概率阈值$ \alpha $，存在一个顶点集合$ { {C}} $，$ { {C}}\subseteq { {V}} $，若$ { {C}} $中任意2点之间均有边相连，且$ p\left({\mathrm{cliq}}\left({ {C}}\right)\right) $ $ \geqslant $ $ \alpha $，则$ { {C}} $为$ \alpha $-团。如果不存在一个顶点$ v $（$ v\notin { {C}} $且$ v\in{ { V}} $），使得$ { {C}}\cup \left\{v\right\} $是一个$ \alpha $-团，即$ { {C}} $不被其他任意顶点集合所包含，则是一个$ \alpha $-极大团。

例如，在图1上，给定一个$ \alpha $为0.6，虽然$ {{ {C}}}_{4}=\left\{\mathrm{4,5}\right\} $是一个$ \alpha $-团（$ p\left(\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{q}\left({{ {C}}}_{4}\right)\right) \geqslant 0.6 $），但是，其被团$ {{ {C}}}_{3}=\left\{\mathrm{4,5},6\right\} $所包含，所以$ {{ {C}}}_{4} $不是一个$ \alpha $-极大团；而$ {{ {C}}}_{3} $既满足$ p\left(\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{q}\left({{ {C}}}_{3}\right)\right) \geqslant 0.6 $，且$ {{ {C}}}_{3} $不被其他团所包含，因此$ {{ {C}}}_{3} $是满足要求的$ \alpha $-极大团。

给定一个不确定图$ { {G}}=\left({ {V}},{ {E}},{ {P}}\right) $和概率阈值$ \alpha \left(0 < \alpha < 1\right) $，要求返回所有的$ \alpha $-极大团。

2.   α不确定图的构造

基于子图划分思想的算法$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C}+ $^[22]，在划分子图时过滤掉一些绝不可能成为$ \alpha $-极大团的顶点集合，能一定程度上减少计算时间，但顶点和边的数量依然很多。因此，本研究提出构造$ \alpha $不确定图以缩小图的规模，提升枚举效率。

2.1   α不确定图生成及子图划分作用

枚举极大团的基本过程是“子图划分—枚举—验证”，在子图划分的过程中，通过去掉彼此之间没有边相连的顶点，可以缩小子图规模，但在大规模图上处理起来依然很耗时。为减少枚举的工作，本研究提出构造$ \alpha $不确定图，用以在子图划分之前减小图的规模，再进行子图划分和枚举工作。现给出$ \alpha $不确定图的具体定义。

$ \mathit{\alpha } $不确定图的定义　给定一个不确定图$ { {G}} $，去掉图中概率阈值低于$ \alpha $的边，产生新的不确定图，由于该图中所有边的概率阈值均大于等于$ \alpha $，因此称这样的图为$ \alpha $不确定图。

关于在$ \alpha $不确定图上划分子图的作用，现给出推论和相关证明。

推论1　在$ \alpha $不确定图上划分子图，会得到数量更少的极大团子图，且划分速度会更快。

证明　由于$ \alpha $不确定图已经去掉很多不符合条件的边，图的规模大大减小，因此划分后会得到数量更少的极大团子图；在划分子图时，$ \mathrm{D}\mathrm{e}\mathrm{g}\mathrm{e}\mathrm{n}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y} $算法时间复杂度是$ O\left(dn\cdot {3}^{d/3}\right) $，其中，$ n $是顶点数量，$ d $表示图的简并度，$ d $远远小于$ n $，由于$ \alpha $不确定图的边有所减少，因此，$ d $会减少，划分的时间复杂度就会降低，划分速度会更快。

推论2　在$ \alpha $不确定图上划分子图，与在不经过处理的不确定图上划分的结果相比，得到的极大团子图的规模会更小，且在这样的极大团子图上枚举$ \alpha $-极大团，时间效率会提升。

证明　$ \alpha $不确定图与原不确定图相比，少了很多无用的边，划分子图后，每个子图是极大团完全连通子图，所以跟原来划分子图的结果相比，减少了很多顶点和边，极大团子图的规模会相对减小。在每个极大团子图上枚举$ \alpha $-极大团时，$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法的时间复杂度是$ O\left(n\cdot {2}^{n}\right) $，其中，$ n $是顶点数量，在枚举阶段，由于极大团子图的顶点数量与原不确定图划分的极大团子图的顶点数量相比会减少，因此枚举阶段的时间也会相应的减少，时间效率就能够得到提升。

为了证明在$ \alpha $不确定图上的枚举效率更高，本研究对此进行了实验验证。

2.2   α不确定图上枚举的正确性

在计算成团概率时，是计算各边之积，且每条边的概率阈值都小于等于1，如果在$ \alpha $不确定图上划分再枚举，不仅可以减小图规模，提高算法执行效率，还能不损失正确性，成功枚举出所有的$ \alpha $-极大团。

推论3　在$ \alpha $不确定图中挖掘$ \alpha $-极大团时，挖掘出来的极大团不会缺少也不会增多，并且是完全正确的。

证明　在不确定图中，每条边的存在概率是相互独立的。根据式（1）可知，成团概率是各边之积。由于每条边的概率值$ P\in \left(\mathrm{0,1}\right] $，概率阈值$ \alpha \in \left(\mathrm{0,1}\right) $，所以当出现某条边的概率值小于$ \alpha $时$ \left(P\left(e\right) < \alpha \right) $，原来的团概率值乘以$ P\left(e\right) $，结果一定是小于$ \alpha $的，因此在枚举时，低于$ \alpha $阈值的边不会在考虑范围之内，该边一定不会出现在$ \alpha $-极大团中，得到的结果和在原不确定图上的枚举结果一致。

为了验证本研究提出的处理方法可以提高算法的效率，后续将对此进行实验来证明。实验基础分别为不经过处理的不确定图和$ \alpha $不确定图，在不同的数据集上进行实验，检验与此思路相关的4种算法，分别是$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C}+ $、$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{L} $、$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $和MULERPM算法在不确定图和$ \alpha $不确定图上的时间效率。

为了更好地说明情况，本研究将以具体的实例进行分析。

如果在图3中找到概率阈值为0.6的$ \alpha $-极大团，去掉概率值小于0.6的边，结果如图4所示。

图  3  原不确定图

Fig.  3  Original uncertain graph

下载: 全尺寸图片

图  4  α不确定图

Fig.  4  α uncertain graph

下载: 全尺寸图片

3.   α不确定图上的极大团枚举及高效验证

不确定图上枚举极大团现有的思想“子图划分—枚举—验证”中，子图划分阶段，在未经处理的不确定图上进行划分，可能会产生规模大且数量很多的极大团子图，导致枚举效率不高；在验证阶段，现有的使用倒排表和映射表结合的验证方法在伪极大团很多的情况下工作量会很大且耗时。针对以上问题，本研究提出了$ \alpha $不确定图上枚举极大团及高效验证算法MILEUMC，在$ \alpha $不确定图上进行子图划分，不仅能使划分出来的子图数量减少，子图的顶点数量也能大量减少，进而提高枚举效率；此外，还提出了基于多重倒排表(multiple inversion list，MIL)的验证方法，实现了去重和去包含关系来去除伪极大团。当伪极大团数量很多时，能够以较少的时间去伪，最终得到所有的$ \alpha $-极大团。具体的操作步骤和算法流程如图5所示。

图  5  不确定图上枚举极大团算法步骤

Fig.  5  Enumeration maximal clique algorithm steps on uncertain graphs

下载: 全尺寸图片

3.1   基于子图划分的不确定图$ \mathbf{\alpha } $-极大团枚举

在枚举极大团时，本研究使用了基于子图划分的算法和较为经典的$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法^[22]。

先将$ \alpha $不确定图当作确定图处理，再用Degeneracy算法将其划分为极大团子图，然后在每个极大团子图上分别用$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法枚举出所有的$ \alpha $-极大团。通过划分可以过滤掉原图中大多数绝不可能成为$ \alpha $-极大团的顶点集合，以减少算法需要考虑的顶点集合的数量和验证次数，跟直接使用$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法相比，可以提高算法的计算效率。

针对上述的例子，用$ \mathrm{D}\mathrm{e}\mathrm{g}\mathrm{e}\mathrm{n}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y} $算法对图4进行划分，结果如图6所示。

图  6  极大团子图

Fig.  6  Maximal clique subgraph

下载: 全尺寸图片

Li等^[20]列举的诸多枚举极大团的求解办法包括：基于深度优先搜索（depth-first search, DFS）的办法、基于简并顺序的方法和基于顶点编号升序的办法等。其中基于顶点编号升序的算法（MULE）与其他算法相比性能较好，时间复杂度是$ O\left(n\cdot {2}^{n}\right) $。虽然这种算法在顶点规模较大时，时间代价大，但是本研究的划分思想，将原图划分为规模更小的极大团子图，在极大团子图上调用$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法，与直接使用$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $相比，时间性能是较优的。

在划分后的所有极大团子图上用$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法枚举出符合条件的$ \alpha $-极大团。上述例子中，在4个子图上分别调用$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法，能够得到所有的$ \alpha $-极大团Aumc={{1,2,3},{1,3,4},{2,4},{2,4},{2,5},{4,5},{6,7,8},{6,7},{6,9},{7,9}}。但是这些$ \alpha $-极大团里面存在伪极大团。在不确定图$ { {G}} $中，不同的极大团子图挖掘出来许多满足条件的$ \alpha $-极大团，若该团满足以下2种情况之一，则被称为$ \alpha $-伪极大团。1）存在一个极大团$ { {C}} $，被其他极大团子图挖掘出来的更大的$ \alpha $-极大团所包含；2）存在2个完全相同的$ \alpha $-极大团$ { {C}} $。接下来需要去伪得到最终的结果集。

3.2   基于多重倒排表的不确定图枚举极大团验证

本研究提出基于多重倒排表的验证方法，分为去重和去包含关系去除伪极大团。

1)去重复极大团，在此处，多重倒排表$ \mathrm{M}\mathrm{I}\mathrm{L} $的索引为极大团的规模和各顶点之和，表示为$ \left(\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e},\mathrm{s}\mathrm{u}\mathrm{m}\right) $，每个索引后有其对应的倒排表$ \mathrm{I}\mathrm{L} $，在$ \mathrm{I}\mathrm{L} $中，索引为顶点编号，每个索引后为极大团编号，意为该顶点存在于哪些极大团中，表示为$ (\mathrm{k}\mathrm{e}\mathrm{y},\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}) $。

2)去包含关系极大团，在此处，$ \mathrm{M}\mathrm{I}\mathrm{L} $的索引为极大团的规模，表示为$ \left(\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}\right) $，每个索引后同样有其对应的$ \mathrm{I}\mathrm{L} $，$ \mathrm{I}\mathrm{L} $的索引为顶点编号，每个顶点编号后的内容也是极大团的编号，表示为$ (\mathrm{k}\mathrm{e}\mathrm{y},\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}) $。

基于$ \mathrm{M}\mathrm{I}\mathrm{L} $的验证方法在处理伪极大团数量很多的问题上，能够有效减小验证工作量，在去重过程中，增加团内元素之和的排序维度，即在规模相同的情况下，按照元素之和的大小排序，进一步判断这些元素是否相同，使用$ \mathrm{M}\mathrm{I}\mathrm{L} $的数据结构来去除重复伪极大团，能够提高验证效率；在去包含关系过程中，使用$ \mathrm{M}\mathrm{I}\mathrm{L} $和优化后的映射表$ {R} $去除伪极大团，可以优先筛选出具有某些特征的极大团，从而提升验证效率。

3.2.1   去重复伪极大团

去重，去掉完全相同的$ \alpha $-极大团。每检测到一个$ \alpha $-极大团，根据索引找到其对应的$ \mathrm{I}\mathrm{L} $，再找到极大团中包含的顶点，将顶点对应的集合取交集，如果交集为空，说明该团在$ \mathrm{I}\mathrm{L} $中没出现过，是不重复的$ \alpha $-极大团。更新$ \mathrm{I}\mathrm{L} $中该极大团出现的记录，并将该团放入不含有重复伪极大团的结果集${ {\rm{Aumc}}}' $中。

在验证$ \alpha $-极大团过程中，对原$ { {\rm{Aumc}}} $集合按照团规模降序排序。为了能快速去除重复的伪极大团，在此基础上，本研究提出，在排序时，规模相同的情况下，按照元素之和的大小排序，进一步判断这些元素是否相同，如果相同，去掉相同的其他元素，可以减少待验证的$ { {\rm{Aumc}}} $集合的规模；当重复团数量很大的时候，能提高算法执行效率。

对$ \alpha $-极大团进行操作：

首先建立$ \mathrm{M}\mathrm{I}\mathrm{L} $，索引为$ \alpha $-极大团的规模和各顶点编号之和。根据每个团，得出$ \mathrm{M}\mathrm{I}\mathrm{L} $的索引值有(3,6)、 (3,8)、 (2,6)、 (2,7)、 (2,9)、 (3,21)、 (2,13)、(2,15)、(2,16)，每个不同的$ \left(\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e},\mathrm{s}\mathrm{u}\mathrm{m}\right) $都有对应的$ \mathrm{I}\mathrm{L} $，$ \mathrm{I}\mathrm{L} $的索引为顶点编号，索引下为包含该顶点的$ \alpha $-团的编号的集合。规定第1个$ \alpha $-团编号为0。

当检测到极大团$ \left\{\mathrm{2,4}\right\} $时，按照规定找到索引值为$ \left(\mathrm{2,6}\right) $的$ \mathrm{I}\mathrm{L} $，初始时，每个顶点下的集合都为空集。在$ \mathrm{I}\mathrm{L} $中找到团包含的顶点2和顶点4，将对应的集合取交集，发现交集为空，说明该团中的顶点在此之前没有出现在别的团中，更新$ \mathrm{I}\mathrm{L} $的值，将对应的团编号填入，并将该团放入不含有重复的$ \alpha $-极大团结果集$ { {\rm{Aumc}}}' $中。

再次遇到极大团$ \left\{\mathrm{2,4}\right\} $时，根据上述操作，对顶点2和顶点4对应的集合取交集，交集为2，说明该团中的顶点存在于编号为2的团中，由于此$ \mathrm{I}\mathrm{L} $中存放的都是规模相同的团，因此交集不为空，说明该团与之前的某团重复，不更新$ \mathrm{I}\mathrm{L} $，更新后的倒排表为表1。

按上述流程操作完得到最后的结果集Aumc′={{1,2,3},{1,3,4},{2,4},{2,5},{4,5},{6,7,8},{6,7},{6,9},{7,9}}。

3.2.2   去包含关系伪极大团

去包含关系的$ \alpha $-极大团。先将$ { {\rm{Aumc}}}' $按规模从大到小进行特殊的快速排序，得到集合$ { {\rm{Aumc}}} $。处理时，首先使用映射表$ R $筛选具有特征的$ \alpha $-极大团。$ R $的索引为顶点编号，每个顶点编号后是该顶点出现在$ \alpha $-极大团中的次数，也可以理解为出现在几个$ \alpha $-极大团中。

每检测到一个$ \alpha $-极大团，在$ R $中寻找对应的顶点，如果某顶点下的结果$ R\left[v\right] $为0，说明该团是一个之前从未出现过的团，此时动态更新$ R $和对应的$ \mathrm{I}\mathrm{L} $。该方法可以筛选出某些顶点只出现在某个极大团中的特殊情况。使用$ R $后，再使用$ \mathrm{M}\mathrm{I}\mathrm{L} $去伪。只有检测到的团为真正的$ \alpha $-极大团时，才更新$ R $和$ \mathrm{I}\mathrm{L} $。无法检测时，使用$ \mathrm{M}\mathrm{I}\mathrm{L} $验证。由于$ { {\rm{Aumc}}} $是降序排序，第1个极大团一定是真正的$ \alpha $-极大团，当检测一个极大团时，只需要与其规模更大的极大团进行比较，找到对应规模的$ \mathrm{I}\mathrm{L} $进行相应操作。如果现有的$ \mathrm{M}\mathrm{I}\mathrm{L} $里面没有当前被检测的极大团规模的$ \mathrm{I}\mathrm{L} $，根据当前的极大团，建立对应的$ \mathrm{I}\mathrm{L} $。然后找到当前团的顶点，将顶点对应的$ \mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r} $集合取交集。如果交集为空，说明当前团不被其他团所包含，是真正的$ \alpha $-极大团，动态更新$ R $和$ \mathrm{I}\mathrm{L} $；如果不为空，说明该团是伪极大团，需要使用falseSet记录，最后在$ { {\rm{Aumc}}}$中除去falseSet里存在的极大团，返回最终结果集result。

按上述规则操作后，检验到$ \{\mathrm{6,7},8\} $时，由于前3个集合中总有顶点后的$ \mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e} $值在检测时为0，因此能够检测出具有此特征的$ \alpha $-团{1,2,3}、{1,3,4}、{6,7,8}为真正的$ \alpha $-极大团，检测完$ \{\mathrm{6,7},8\} $的$ R $结果见表2。

检测$ \left\{\mathrm{2,4}\right\} $时，顶点2和顶点4的$ \mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e} $值均不为0，所以需要借助$ \mathrm{M}\mathrm{I}\mathrm{L} $检测是否为包含关系的伪极大团。检测到$ \left\{\mathrm{2,5}\right\} $时，顶点5的$ \mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e} $值为0，所以$ \left\{\mathrm{2,5}\right\} $是一个$ \alpha $-极大团。同理，检测到$ \left\{\mathrm{4,5}\right\} $、$ \left\{\mathrm{6,7}\right\} $和$ \left\{\mathrm{7,9}\right\} $时，对应顶点的$ \mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e} $值均不为0，需要借助$ \mathrm{M}\mathrm{I}\mathrm{L} $去伪。检测$ \left\{\mathrm{6,9}\right\} $时，9的$ \mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e} $值为0，因此$ \left\{\mathrm{6,9}\right\} $为$ \alpha $-极大团。结果见表3。

在去包含关系的伪极大团时，本研究同样使用$ \mathrm{M}\mathrm{I}\mathrm{L} $去伪，$ \mathrm{M}\mathrm{I}\mathrm{L} $的索引为团的规模，每个规模对应一张$ \mathrm{I}\mathrm{L} $。对应上述实例，同步更新规模为3和规模为2的$ \mathrm{I}\mathrm{L} $，使用完$ R $后更新的最终$ \mathrm{I}\mathrm{L} $结果见表4和表5。

团$ \{\mathrm{1,2},3\} $、$ \{\mathrm{1,3},4\} $、$ \{\mathrm{6,7},8\} $，其规模已是最大，一定不会被同规模的团包含。接下来使用$ \mathrm{M}\mathrm{I}\mathrm{L} $对$ \left\{\mathrm{2,4}\right\} $、$ \left\{\mathrm{4,5}\right\} $、$ \left\{\mathrm{6,7}\right\} $、$ \left\{\mathrm{7,9}\right\} $进行验证。由于待检验的团规模都是2，且已去重，所以只需要将这些团与规模大于2的团进行比较即可。

检测$ \left\{\mathrm{2,4}\right\} $时，在规模为3的$ \mathrm{I}\mathrm{L} $中找到顶点2和顶点4，将顶点的$ \mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r} $集合取交集，交集为空，说明该团中的顶点不存在于之前的任何团中，更新$ \mathrm{I}\mathrm{L} $和$ R $。同理，检测$ \left\{\mathrm{4,5}\right\} $ ，结果为$ \alpha $-极大团，更新ZL和R。当检测到$ \left\{\mathrm{6,7}\right\} $时，由于顶点6和顶点7的$ \mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r} $交集为2，不为空，说明顶点6和7曾出现在团2中，记录falseSet[MC]值为$ \mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e} $。检测$ \left\{\mathrm{7,9}\right\} $，结果为$ \alpha $-极大团，更新两表。

$ R $和$ \mathrm{I}\mathrm{L} $的最终结果见表6和表7。

最后，将不在falseSet中的团$ \mathrm{M}\mathrm{C} $存储在result中，所有的$ \alpha $-极大团为result={{1,2,3},{1,3,4},{6,7,8},{2,4},{2,5},{4,5},{6,9},{7,9}}。

3.3   算法描述与分析

本研究提出了$ \alpha $不确定图上极大团枚举及验证算法$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $，以下给出相关算法的描述和算法分析。

算法1　MILEUMC（）

输入　不确定图G，概率阈值α

输出　α-极大团结果集result

1) Aumc ← $\varnothing $，result ← $\varnothing $

2) //剔除E中概率小于α的边

3) for all e $ \in $ E do

4) if P(e) < α then

5) Delete e from G

6) end if

7) end for

8) return G

9) Amc ← Degeneracy(G) //通过子图划分算法得到极大团子图集合

10) for each subgraph g in Amc do

11) Aumc ← MULE(g,α) //对每个极大团子图调用MULE算法

12) end for

13) Aumc = EarseDup(Aumc) //在Aumc中去除重复团并根据团规模进行排序

14) MIL = GenerateMIL(Aumc) //初始化多重倒排表

15) falseSet = FindAllFalseMC(Aumc,MIL)//根据多重倒排表找到所有包含关系的伪_极大团

16) //去除伪极大团

17) for each MC in Aumc do

18) if MC is not in falseSet then

19) result ← MC

20) end if

21) end for

22) return result

算法2　GenerateMIL（）

输入　去重后的结果集Aumc

输出　多重倒排表MIL

1) //将规模最大的团编号插入到多重倒排表中

2) IL ← $\varnothing $，MIL ← $\varnothing $，C ← Aumc[0]

3) for each v in C do

4) IL[v] ← 0

5) end for

6) IL.MCsize ← C.size

7) MIL ← IL

8) return MIL

算法3　EraseDup（）

输入　调用MULE的结果集Aumc

输出　不含有重复团的结果集Aumc´

1) //此处多重倒排表(MSIL)索引为团规模与顶点编号之和，加快查找重复团的速度

2) MSIL ← $\varnothing $，Aumc´ ← $\varnothing $

3) for each MC in Aumc do

4) IL ← MSIL [MC.size,MC.sum]

5) X ← IL[v₀]

6) for each v in MC(v≠v₀) do

7) X ← X ∩ IL[v]

8) end for

9) if X = $\varnothing $ then

10) for each v in MC do

11) IL[v] ← MC.index

12) Aumc´ ← MC

13) end for

14) end if

15) end for

16) return Aumc´

算法4　FindAllFalseMC（）

输入　去重后的结果集Aumc，多重倒排表MIL

输出　包含关系的伪极大团集合falseSet

1) R ← $\varnothing $，falseSet ← $\varnothing $

2) //R为映射表，falseSet记录伪极大团

3) for each MC in Aumc do

4) //对每个团先使用映射表验证，R[v]值为0说明该团是α-极大团，不需要再用MIL验证

5) for each v in MC do

6) if R[v] = 0 then

7) UpdateMILR(MC,MIL,R)

8) end if

9) end for

10) if 映射表检测为α-极大团 then

11) continue //继续下一次团验证

12) end if

13) //在多重倒排表中按照规模大小使用倒排表验证，对每个倒排表取交集，交集均为空则该团为极大团，反之为伪极大团

14) for each IL in MIL do

15) if IL.MCsize ≤ MC.size then

16) break

17) end if

18) X ← IL[v₀]

19) for each v in MC do

20) X ← X ∩ IL[v]

21) end for

22) if X = $\varnothing $ then

23) UpdateMILR(MC,MIL,R)

24) else

25) falseSet[MC] = true

26) end if

27) end for

28) end for

29) return falseSet

算法5　UpdateMILR（）

输入　当前α-团MC，多重倒排表MIL，映射表R

输出　更新后的多重倒排表MIL，映射表R

1) ILL ← $\varnothing $

2) //若当前团规模与多重倒排表中最小规模倒排表规模不同，则需要新建倒排表，反之使用最小规模倒排表

3) if LastIL.MCsize == MC.size then

4) ILL = LastIL

5) else

6) ILL.MCsize = MC.size

7) MIL ← ILL

8) end if

9) //将团编号插入倒排表，并更新多重倒排表和映射表

10) for each v in MC do

11) ILL[V] ← MC.index

12) R[v] ← R[v] + 1

13) end for

14) MIL ← ILL

15) return MIL, R

枚举阶段中，构造$ \alpha $不确定图，用$ \mathrm{D}\mathrm{e}\mathrm{g}\mathrm{e}\mathrm{n}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y} $算法划分子图的最坏时间复杂度是$ O\left({n}'\cdot {3}^{{n}'/3}\right) $，其中，$ {n}' $为子图中的顶点数目，远小于原图中的顶点数目$ n $。在子图中调用$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法的最坏时间复杂度为$ O\left({n}'\cdot {2}^{{n}'}\right) $。

验证阶段中，Li等^[20]的验证算法$ \mathrm{D}\mathrm{P}\mathrm{M}\mathrm{C} $最坏时间复杂度为$ O\left({n}'\cdot {3}^{{n}'/3}\right) $，杜明等^[23]的改进$ \mathrm{F}\mathrm{D}\mathrm{P}\mathrm{M}\mathrm{U} $算法最坏时间复杂度也是$ O\left({n}'\cdot {3}^{{n}'/3}\right) $，最好情况的时间复杂度为$ O\left({3}^{{n}'/3}\right) $，张艺等^[24]的验证算法$ \mathrm{I}\mathrm{R}\mathrm{P}\mathrm{M}\mathrm{C} $时间复杂度为$ O\left(n\cdot {3}^{n/3}\right) $。而本研究提出的基于多重倒排表的验证方法去除伪极大团的最坏时间复杂度为$ O\left({n}'\cdot {3}^{{n}'/3}\right) $，最好情况下也是$ O\left({3}^{{n}'/3}\right) $，但是在此时间维度下，由于本研究将复杂的工作简单化，工作量减小，提出的验证算法所花费的时间在大多数情况下，都要比前2种验证算法花费时间少。

由此可以得出，算法$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $的最坏时间复杂度为$ O\left({n}'\cdot {3}^{{n}'/3}\right) $，与子图划分思路相同的2种算法$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C}+ $、$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{L} $相比，执行效率更高。

4.   实验分析

为验证算法的正确性和有效性，本研究进行了3种实验。下面将分别对实验的不同环节进行验证。

4.1   实验环境

实验所使用的硬件平台是11th Gen Intel(R) Core(TM) i7-11700K 主频为3.60 GHz的CPU，16 GB的RAM内存，操作系统为Windows10 64位的系统；实验的运行环境是Microsoft Visual Studio 2022；编程语言为C++。

4.2   数据集

本研究使用7个数据集来评估几种算法的性能。这些数据集包括amaze5、yago5、mtbrv5、citeseer5、anthra5、ecoo5、agrocyc5。其中anthra5、mtbrv5、agrocyc5和ecoo5描述了生物化学和基因组之间的生物学序列；$ \mathrm{a}\mathrm{m}\mathrm{a}\mathrm{z}\mathrm{e}5 $描述了生物体内的化学反应网络；$ \mathrm{c}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{r} 5$描述了蛋白质反应的传递网络；$ \mathrm{y}\mathrm{a}\mathrm{g}\mathrm{o} 5$描述了不同语义关系之间的语义信息。这些信息各自代表了不同领域的相关知识，都蕴含有不确定信息，均可用不确定图来存储信息。具体的数据集信息见表8。其中$ \left|{ {V}}\right| $表示不确定图中的顶点数目，$ \left|{ {E}}\right| $表示不确定图中边的数目。

4.3   性能比较与分析

本研究主要进行了3种实验，实验1为在同一数据集下，在$ \alpha $不确定图上和原不确定上进行极大团枚举的算法效率对比实验；实验2为在给定同一个$ \alpha $概率阈值的情况下，通过表8的数据集生成不确定图来枚举极大团，比较算法$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $^[19]、$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C}+ $^[22]、$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{L} $^[23]、$ \mathrm{I}\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E}\mathrm{R}\mathrm{P}\mathrm{M}\mathrm{C} $^[25]和本研究提出的枚举算法$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $在7个不同的数据集上执行的时间效率；实验3为在同一数据集中，5种算法在不同的$ \alpha $情况下时间性能的比较。最后通过对比，证实$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法的高效性。

4.3.1   相同数据集下的不同不确定图的算法对比实验

为更好地证明在$ \alpha $不确定图上枚举$ \alpha $-极大团算法的高效性，选用具有代表性的2种数据集，分别是$ \left|{ {E}}\right|/\left|{ {V}}\right| $值在2左右的$ \mathrm{a}\mathrm{m}\mathrm{a}\mathrm{z}\mathrm{e}5 $数据集和$ \left|{ {E}}\right|/\left|{ {V}}\right| $在12左右的$ \mathrm{y}\mathrm{a}\mathrm{g}\mathrm{o}5 $数据集，分别进行了$ \alpha $为0.6和0.8的2种实验。进行比较的算法分别是$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C}+ $、$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{L} $和$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法，如图7和图8所示。

图  7  α为0.6时各算法在amaze5数据集上的运行时间

Fig.  7  Running time of each algorithm on amaze5 data set (α is 0.6)

下载: 全尺寸图片

图  8  α为0.6时各算法在yago5数据集上的运行时间

Fig.  8  Running time of each algorithm on yago5 data set (α is 0.6)

下载: 全尺寸图片

由图7和图8可以看出，3种算法在$ \mathrm{a}\mathrm{m}\mathrm{a}\mathrm{z}\mathrm{e}5 $数据集和$ \mathrm{y}\mathrm{a}\mathrm{g}\mathrm{o}5 $数据集上，在$ \alpha $不确定图上的运行时间效率更高，并且经过检查对比，3种算法在$ \alpha $不确定图上均能正确枚举出所有的$ \alpha $-极大团。

由图9和图10可以看出，以“划分−枚举−验证”为思路的$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C}+ $和$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{L} $算法在$ \alpha $不确定图上比在原不确定图上运行要快很多，在$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法中，运行时间接近。由于$ \mathrm{y}\mathrm{a}\mathrm{g}\mathrm{o}5 $数据集的$ \left|{ {E}}\right|/\left|{ {V}}\right| $值为12左右，即在边更多的大图上，采用划分子图的方法，可能会产生很多的子图，因此在每个子图上枚举反而会比较耗时，而$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法按照节点编号进行回溯，使得枚举过程不会产生伪极大团，所以在这样的图上表现会较好，因此，在$ \alpha $不确定图和原不确定图上运行，$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法在原不确定图上运行时间会比在$ \alpha $不确定图上稍快一些，但总体相差不大。

图  9  α为0.8时各算法在amaze5数据集上的运行时间

Fig.  9  Running time of each algorithm on amaze5 data set (α is 0.8)

下载: 全尺寸图片

图  10  α为0.8时各算法在yago5数据集上的运行时间

Fig.  10  Running time of each algorithm on yago5 data set (α is 0.8)

下载: 全尺寸图片

4.3.2   阈值相同下的数据集对比实验

为更好比较几种算法的执行效率，随机确定几个$ \alpha $的值，这里取$ \alpha $为0.2、0.6和0.9。结果如图11~13所示。

图  11  α为0.2时各算法在7个不同的数据集上的运行时间

Fig.  11  Running time of each algorithm on 7 different data sets (α is 0.2)

下载: 全尺寸图片

图  12  α为0.6时各算法在7个不同的数据集上的运行时间

Fig.  12  Running time of each algorithm on 7 different data sets (α is 0.6)

下载: 全尺寸图片

图  13  α为0.9时各算法在7个不同的数据集上的运行时间

Fig.  13  Running time of each algorithm on 7 different data sets (α is 0.9)

下载: 全尺寸图片

当$ \alpha $设置为0.2时，可以看出$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法在不同的数据集上表现不同。在$\left|{ {E}}\right|/\left|{ {V}}\right|$值较大的$ \mathrm{y}\mathrm{a}\mathrm{g}\mathrm{o}5 $数据集和$ \mathrm{c}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{r}5 $数据集上，该算法与其他算法的区别较大，时间效率不高，在这2个数据集上，$ \mathrm{I}\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E}\mathrm{R}\mathrm{P}\mathrm{M}\mathrm{C} $算法是运行效率最高的。在其他数据集上，$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法时间效率比$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $高，比$ \mathrm{I}\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E}\mathrm{R}\mathrm{P}\mathrm{M}\mathrm{C} $、$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{L} $和$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C}+ $算法低。

在$ \mathrm{y}\mathrm{a}\mathrm{g}\mathrm{o}5 $数据集和$ \mathrm{c}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{r}5 $数据集中，由于此时的概率阈值较小，采用“子图划分−枚举−验证”思路的$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C}+ $、$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{L} $和$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $会枚举出较多的$ \alpha $-极大团，验证的时间也就更多；$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法中不需要验证阶段，按照节点编号回溯的机制避免了伪极大团的产生；而$ \mathrm{I}\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E}\mathrm{R}\mathrm{P}\mathrm{M}\mathrm{C} $算法在改进$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法的过程中通过计算扩展后的集合概率验证是否为$ \alpha $-团，减少算法递归次数，还删除已使用顶点集合$ { {X}} $的计算，提高了算法执行效率，跟$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法相比，效率更高。因此，当$ \alpha $阈值较小时，$ \mathrm{I}\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E}\mathrm{R}\mathrm{P}\mathrm{M}\mathrm{C} $在5种算法中，时间效率高。

由图12可知，当$ \alpha $设置成为0.6时，$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法在时间效率上总体高于其他4种算法，性能得到了很大的提高。只有在$ \mathrm{c}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{r}5 $数据集和$ \mathrm{y}\mathrm{a}\mathrm{g}\mathrm{o}5 $数据集上$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法不是最快的，IMULERPMC时间效率最高，但是$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法比$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{L}\mathrm{和}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C}+ $算法运行效率都高。尤其在yago5数据集上，MILEUMC算法跟EUML算法和EUMC+算法相比，时间快了近1倍。

由图13得知，当$ \alpha $设置成为0.9时，与$ \alpha $为0.6时相比，在$ \mathrm{y}\mathrm{a}\mathrm{g}\mathrm{o}5\mathrm{和}\mathrm{c}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{r}5 $数据集上表现有所提升，时间效率接近$ \mathrm{I}\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E}\mathrm{R}\mathrm{P}\mathrm{M}\mathrm{C} $，且与子图划分思路相同的$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{L}\mathrm{和}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C}+ $算法相比，时间效率快7~8倍。在其他$\left|{ {E}}\right|/\left|{ {V}}\right|$为2左右的数据集上，$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法都比其他4个算法快很多，只需要花一半时间就可以枚举出所有的极大团。

结合表9和实验的结果发现，随着$ \alpha $的增大，$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法的运行效率会越来越高，即当想要挖掘联系更加紧密的子图时，在$\left|{ {E}}\right|/\left|{ {V}}\right|$相对不大的图上，$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法是最优选择，可以节约一半的时间。

4.3.3   数据集相同下的阈值对比实验

本研究还进行了不同$ \alpha $对$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $、$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{L} $、$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C}+ $、$ \mathrm{I}\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E}\mathrm{R}\mathrm{P}\mathrm{M}\mathrm{C} $和$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法的时间性能影响的实验。针对$ \left|{ {E}}\right|/\left|{ {V}}\right| $值为2的$ \mathrm{a}\mathrm{m}\mathrm{a}\mathrm{z}\mathrm{e}5 $数据集、$ \left|{ {E}}\right|/\left|{ {V}}\right| $值为2的边点更多的$ \mathrm{a}\mathrm{n}\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{a}5 $数据集和$ \left|{ {E}}\right|/\left|{ {V}}\right| $值为8左右的$ \mathrm{c}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{r}5 $数据集检测了$ \alpha $为0.1~0.9时，5种算法运行时间的变化。图14和图15为实验的结果。

图  14  5种算法在同一数据集amaze5上不同α的运行时间

Fig.  14  Running time of five algorithms with different α values on the same data set amaze5

下载: 全尺寸图片

图  15  5种算法在同一数据集anthra5上不同α的运行时间

Fig.  15  Running time of five algorithms with different α values on the same data set anthra5

下载: 全尺寸图片

由图14可以看出，在$ \mathrm{a}\mathrm{m}\mathrm{a}\mathrm{z}\mathrm{e}5 $数据集上，随着$ \alpha $取值越来越大，$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{L} $算法运行时间先上升后保持平稳波动，$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C}+\mathrm{和}\mathrm{I}\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E}\mathrm{R}\mathrm{P}\mathrm{M}\mathrm{C} $算法时间变化不大，$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法在5种算法中始终是最耗时的，而$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法的运行时间越来越短，时间效率大大提高。几乎所有的$ \alpha $取值都满足$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法是最快的，尤其是当$ \alpha $为0.9时，$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法比$ \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E} $算法运行时间快近2倍，比其他3种算法运行时间快1倍左右。

由图15可以看出，当$ \alpha $很小，为0.1、0.2时，$ \mathrm{I}\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E}\mathrm{R}\mathrm{P}\mathrm{M}\mathrm{C} $算法运行时间最短。但随着$ \alpha $的增长，$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法运行时间越来越短，当$ \alpha $增长到0.6时，从此处开始，$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法在5种算法中表现最好，且到$ \alpha $为0.9该算法的效率都是最高的。

由图16可知，在$ \mathrm{c}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{r}5 $数据集上，随着$ \alpha $的不断增加，MULE、IMULERPMC和EUMC+算法性能较平稳，变化不大，其中，$ \mathrm{I}\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E}\mathrm{R}\mathrm{P}\mathrm{M}\mathrm{C} $算法时间消耗较少；$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{L} $算法运行时间先上升后下降，波动较大；$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法的运行时间会越来越少，从$ \alpha $变为0.3开始，运行效率比EUML和EUMC+都好；在5种算法中，在$ \mathrm{c}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{r}5 $数据集上$ \mathrm{I}\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E}\mathrm{R}\mathrm{P}\mathrm{M}\mathrm{C} $算法表现最好。

图  16  5种算法在同一数据集citeseer5上不同α的运行时间

Fig.  16  Running time of five algorithms with different α values on the same data set citeseer5

下载: 全尺寸图片

综合表9和实验结果可以看出，在$\left|{ {E}}\right|/\left|{ {V}}\right|$值为2的相对稀疏的数据集不管是规模小的$ \mathrm{a}\mathrm{m}\mathrm{a}\mathrm{z}\mathrm{e}5 $，还是规模较大的$ \mathrm{a}\mathrm{n}\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{a}5 $上，$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法表现始终最好，是5种算法中运行效率最高的；而在$ \left|E\right|/\left|V\right| $值较大的数据集$ \mathrm{c}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{e}\mathrm{r}5 $上，$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $算法虽然没有$ \mathrm{I}\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{E}\mathrm{R}\mathrm{P}\mathrm{M}\mathrm{C} $算法时间性能好，但总体来说，比$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{L} $和$ \mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C}+ $算法的效率更优。

5.   结束语

本研究分析了在不确定图上枚举极大团的问题。针对时间效率问题，提出了$ \alpha $不确定图的构建及其上的极大团枚举算法$ \mathrm{M}\mathrm{I}\mathrm{L}\mathrm{E}\mathrm{U}\mathrm{M}\mathrm{C} $，尤其在验证方面，提出了基于多重倒排表的验证方法，使用多重倒排表和优化过的映射表去除伪极大团。通过实验证明，构建$ \alpha $不确定图用于枚举，在大规模图上，最快可以节约近10倍的时间；基于多重倒排表的验证方法下，枚举算法MILEUMC在要求挖掘联系很紧密，即阈值为0.8、0.9的极大团时，7个数据集中在$\left|{ {E}}\right|/\left|{ {V}}\right|$值为2左右的较稀疏的大图上，MILEUMC算法运行效率最高，更具有现实意义；在$\left|{ {E}}\right|/\left|{ {V}}\right|$值约为8或12的较稠密的图上随着$ \alpha $值的增大，相较EUMC+和EUML算法，该算法表现也会越来越好。

虽然大多数情况下，MILEUMC算法与其他算法相比，运行效率较高，但是当$ \alpha $很小时（0.1~0.2），不管是在稀疏图还是稠密图上，该算法没有其他算法的运行效率高。未来，还需研究更适合所有情况下的效率更高的不确定图极大团枚举算法。