Page 399 - 《软件学报》2025年第4期

代强强 等: 面向二部图的极大缺陷二团高效枚举算法 1805

算法 3. 优化枚举算法.
输入: 二部图 G 以及正整数 k 与 q ⩾ k +1 ;
q 的极大 k-缺陷二团.
输出: 所有不小于
1. O ← {v 1 ,v 2 ,...,v n } 为 G 中顶点的退化排序;
2. foreach v i ∈ O∧v i ∈ L then
≻ ≻ ≻
3. 构造子图 G = (L ,R v i ,E v i ) 并利用上界剪枝技术删除 G 中的冗余顶点;
v i v i v
≻
4. (G ) ⩾ q−k} ;
X L ← {v j ∈ R v i |j < i,d v j
v i
≻ X L ∅ ); /*该递归加入了上界剪枝技术、线性更新技术以及分支优化技术*/
,
,
5. Branch( v i ∅ L , R v i , ,
v i
6. end for
定理 9. 算法 3 ′ n ′ x 2k+5 −2x 2k+4 3 n 与
′
O(nm γ ) , 其中
的时间复杂度为
k γ k 为线性方程 + x −2x+2 = 0 的最大实根,
′ ≻ 和 γ k 分别等于 和
m 分别为最大子图 G 的顶点数和边数, 如当 k = 0, 1 2 时, 1.544, 1.891 1.975.
v
个算法, 用于枚举给定二部图中的极大
证明: 容易看出算法 3 的时间复杂度为处理最大子图 G 的时间乘以 n . 此外, 在处理子图 G 时, 算法 3 的时
≻
≻
v
v
间复杂度主要与 Branch T(n) 为 Branch G 的总递归
≻
处理子图
的递归数量以及每层递归消耗的时间有关. 为此, 设
v
′
次数, 则算法的时间复杂度为 O(nm T(n)) . 因为 Update 的时间复杂度为线性的所以每层递归的时间复杂度为
′
O(m ) . 下面将重点分析 T(n) 的大小上界.
当 |C L \N(S R )| > k 时, 算法将利用对称集合枚举技术搜索极大 k-缺陷二团. 由于该技术最多生成 k +1 个子分
k+1
∑
支, 则容易得到 T(n) = T(n−i) 的递归关系.
i=1
|C L \N(S R )| ⩽ k 时, 算法直接使用分支定界算法枚举极大 T(n) = T(n−1)+T(n−1) 的
当 k-缺陷二团, 容易得到
v
递归关系. 然而, 由于被选择分支的顶点 v 在当前搜索空间中都具有最小的度. 为此, 在枚举包含 的子分支
T(n−1) 中, 在最坏情况下, 该节点与候选集中的顶点最少存在一个非邻居. 而且, 在该子分支中, 候选集中另外一
个具有最小度的顶点 u 将用于扩展新的当前解, 从而使得当前解在候选集中的非共同邻居数量进一步增大. 在最
|C L \N(S R )| > k . 因此, 可以
坏情况下, 当 k +1 个顶点加入当前解 (S L ,S R ) 时, 该子递归分支 T(n−k −1) 中满足条件
k+1 2k+2
∑ ∑
得到 T(n−k −1) = T(n−i−k −1) . 综上, 可以得到一种更紧的最终递归关系 T(n) = T(n−i) . 此外, 由于最深
i=1 i=1
的递归 T(n−2k −2) 等价于二团枚举, 可以容易验证, 在该情况下的递归关系为 T(n−2k −2) = 2T(n−2k −4) . 综上,
2k+1
∑
算法 3 的最终的递归关系为 T(n) = T(n−i)+ 2T(n−2k −4) , 基于文献 [33] 中的定理 2.1, 可以证明 T(n) 的大小

i=1
n n 2k+5 2k+4 3
与 γ 有关, 其中 γ 为方程 x −2x + x −2x+2 = 0 的最大实根. 因此, 得证.

k k
5 实验分析

5.1 实验设置
(1) 算法: 本文实现了 3 k-缺陷二团, 分别为 iMDCE、MDCE 和 Basic.
其中, iMDCE 是提出的算法 3, 包含了本文提出的所有优化技术; MDCE 是在 iMDCE 的基础上去除了第 4.4 节分
支优化部分的极大 k-缺陷二团枚举算法; Basic 是在 MDCE 的基础上去除对称集合枚举技术的极大 k-缺陷二团枚
举算法. 值得注意的是, iMDCE 与 MDCE 和 Basic 的唯一区别仅在于分支策略上, 3 个算法均包含了第 4.1–4.3 节
的优化技术. 所有算法均由 C++实现, 并在一台配置为 2.2 GHz CPU 和 64 GB 内存的服务器中进行测试.
(2) 数据集: 本实验使用了 6 个真实的二部图数据以测试所提算法的性能, 数据主要包括了社交网络数据、合
作网络数据以及用户标签网络数据等. 具体统计如表 1 所示, 其中 d 1max 与 d 2max 分别表示 L 与 R 中顶点的最大度.
所有的数据均可从 http://konect.cc/networks 下载.