1. 绪论
1.1. 引言
在社交网络分析中，完全图(团)是一个重要的概念，它表示网络中的每个个体都与所有其他个体直接相连，从而形成了一个紧密联系的社交圈。然而，在现实世界中，并非所有社区成员都认识彼此，这种不完全的社交关系促使了松弛团模型的产生[1]。松弛团模型放宽了完全图的严格限制，允许图中存在一定数量的缺失边，从而更真实地反映了社交网络的复杂性。根据应用的场景不同，研究人员对不同的团性质进行松弛进而提出了各种松弛团模型。在松弛团模型的众多变体中，k-club和k-defective clique是两种常见的模型，它们通过引入参数k来控制图的紧密程度[2]。这些模型在大规模图数据中具有重要的应用价值，但同时也带来了巨大的计算挑战。当前对于松弛团模型的研究主要集中于大规模图用例上，但是数量繁多的顶点和边对相应问题的求解造成了巨大的挑战。因此，如何对大规模的图用例进行降维，以缩减输入图的规模显得尤为重要。为了解决上述问题，本文将以松弛团中重要的两类问题：最大k-club问题以及最大k-defective clique问题为核心，研究设计针对这两个问题的图约减技术。
1.2. 松弛团问题的定义及研究现状
1.2.1. 常见松弛团模型和相关问题
图约减技术是图论中用于简化问题复杂度的关键手段，其核心是在保留问题关键信息的前提下，通过删除冗余顶点、边或子图，降低图的规模与密度，从而提升后续算法的求解效率。常见的图约减方法包括基于顶点度数的约减、基于子图连通性的约减、基于上下界估计的剪枝等，这些方法广泛应用于团问题、顶点覆盖问题、图染色问题等组合优化问题中[3]。
松弛团问题是团问题的扩展，其核心是通过引入参数松弛“任意两顶点必相连”的严格约束，以适应现实网络的稀疏性与不完全性。从理论上看，松弛团问题的计算复杂性与参数密切相关：多数松弛团问题(如最大k-club、最大k-defective clique)均被证明为NP难问题[4]，这意味着在大规模图上直接求解的计算成本极高，因此图约减技术成为提升求解效率的关键支撑。
常见的松弛团模型包括：
k-plex：子图中每个顶点至少与其他k-1个顶点相连(即顶点度数不小于|C|-k，其中C为子图顶点集)；
k-club：子图中任意两顶点的最短路径长度不超过k；
k-defective clique：子图的缺失边数不超过k (与同规模完全图相比)。
这些模型通过不同维度的松弛(如距离、边密度)，为不同场景的社区检测提供了灵活工具，例如k-club适用于识别“多步可达”的紧密社区，k-defective clique适用于允许少量关系缺失的稠密子图挖掘。
1.2.2. 最大k-Club问题
2000年，Bourjolly等首次提出最大k-club问题并设计三种启发式搜索策略。2002年，该问题被证明具有NP难度，同时出现基于整数线性规划(ILP)和分支定界(BB)的早期精确算法[5]，此后多数精确算法均基于这两种技术发展而来。Pajouh和Balasundaram进一步证明k-club极大性问题的NP难度，提出结合图着色技术的上界估计BB算法；Shahinpour和Butenko [6]开发变邻域局部搜索算法，改进了Bourjolly等人[7]的BB算法初始下界。
ILP领域中，Veremyev和Boginskii提出基于路径枚举的创新模型；Buchanan和Salemi的模型因变量少、效率高受关注；Almeida和Carvalho针对3-club问题提供上界分析与ILP模型[8]；Pajouh等则深入研究最大2-club问题的多面体结构，在《Operations Research》发表相关ILP模型[9]。
启发式算法方面，Shahinpour和Butenko的变邻域局部搜索融合顶点增减等策略；2014年Almeida和Carvalho的改进型两阶局部搜索算法显著提升效率[10]。2022年Chen等人引入动态图约减技术，通过生成树保持解一致性，设计分层阈值格局检测策略避免循环[11]，据此开发的NukCP算法在多数场景下计算时间更短、解更优，且能在NDR数据集上为所有测试案例提供有效解[12]，展现出强实用性。
近年研究中，针对大规模图的分布式求解成为新方向。例如，2023年Li等人基于MapReduce框架设计并行约减策略，将k-club问题分解为子图任务，在百万级顶点图上实现了高效求解，为最大k-club问题的工程应用提供了新思路。
1.2.3. 最大k-Defective Clique问题
尽管最大k-defective clique问题的研究相对较少，但已有系列重要进展[13]。2013年，Trukhanov等通过遗传学特性分析，开发出首个基于俄罗斯套娃搜索策略的完备算法；2018年，Gschwind等人引入交替递增验证过程，对该算法进行显著改进。
2020年，Stozhkov等基于Motzkin-Straus二阶公式[14]提出创新连续平方公式，首次将其应用于k-defective clique模型，为问题解决提供新视角。2021年，Chen等人设计多种图约减技术，开发出针对该问题的高效分支限界算法MADEC；2022年，Gao等人扩展MADEC的约减策略，引入新边约减技术，提出当前最先进的完备算法KDBB [15]。
此外，Chen等人结合顶点信息开发混合收益值启发式方法，优化候选顶点选择，并设计新哈希函数与约束条件，构建解禁忌搜索算法CSTDC [16]。2023年，Wang等人针对动态图场景，提出增量式约减策略，通过维护顶点度数与缺失边数的动态变化，实现了动态图中最大k-defective clique的高效更新，拓展了该问题的应用场景。
1.3. 相关技术和工具介绍
1.3.1. VMware Workstation
VMware Workstation是一款桌面虚拟化软件，支持在单一物理机上创建并运行多个独立虚拟机(可安装不同操作系统)，为IT开发、软件测试等场景提供高效测试平台。其虚拟网络模拟、实时快照、共享文件夹等功能简化了实验流程，是本研究的首选虚拟机工具。
1.3.2. Linux系统
Linux是开源操作系统内核，基于GNU GPL协议分发，支持进程管理、内存调度等核心功能，由全球开发者社区维护。本研究采用CentOS发行版，其稳定的命令行环境和高效资源管理能力，适合大规模图数据的计算需求。
1.3.3. C++语言
C++是支持面向对象、过程化及泛型编程的高效语言，兼具底层硬件控制能力和跨平台特性，适合实现图约减算法中的邻接表操作、迭代逻辑等核心功能。其丰富的标准库(如容器、算法)可加速开发，故为本研究的编程语言。
1.4. 主要研究目标与方法
本文的主要目标是探索图约减技术在松弛团问题中的应用，特别是针对最大k-club问题和最大k-defective clique问题。为了实现这一目标，本文首先回顾了图约减技术的基本原理，然后分别针对最大k-club问题和最大k-defective clique问题设计了相应的高效约减算法——G_NP和G_KD，用于对大规模图进行有效约减。
1.4.1. 算法部分
将根据最大k-club问题和最大k-defective clique问题的结构特征设计有效的图约减策略，进而降低输入图的复杂度来加速松弛团问题的求解过程。其中涉及到的主要研究内容为设计基于图的连通性、度数、子图结构等方面的约减策略，从而开发高效的算法来解决松弛团问题。这些算法包括基于贪婪策略、启发式方法等技术。
1.4.2. 实验部分
将通过是否调用相关问题的约减方法，观察分析约减方法在这两个问题求解过程中对于输入图规模的影响，进而检验所提出的策略是否能够有效地对最大k-club问题以及最大k-defective问题进行约减。
2. 约减策略
2.1. 最大k-Club问题的约减策略
最大k-club问题的约减主要围绕计算图中k-club的下界值以及各个顶点的上界值展开。通常来说，任意一个k-club的大小就可以作为图的下界值，而每个顶点的k阶闭邻居数量便是一个简单的上界值。文献中针对该问题的约减策略主要分为TRIM方法和DRM方法，两者均是采用上述的上下界计算方式，区别的地方在于各自的维护方法不同，导致计算的效率也有所影响。
2.1.1. TRIM方法
TRIM是一种专门针对k-club问题设计的约减方法。它基于动态规划的思想，迭代地删除图中的冗余顶点。具体来说，TRIM方法包括以下步骤：
1) 计算每个顶点的上界(k阶邻域大小)和下界(启发式估计的最大k-club规模)；
2) 迭代删除上界 ≤ 下界的顶点及关联边，并更新其k阶邻域内顶点的上界；
3) 重复步骤2直至无顶点可删除。
TRIM方法的优点在于它能够有效地减少搜索空间，但缺点是计算上界的过程可能会非常耗时，尤其是对于大规模图来说，这可能会导致算法运行时间较长。
2.1.2. DRM方法
DRM (Dynamic Reduction Method)是TRIM方法的一个改进版本，旨在提高约减过程的效率，因此在处理大规模图时更具效率。DRM方法的核心思想是在删除顶点的同时动态更新上界，而不是重新计算。这减少了不必要的计算开销，并加快了约减过程。DRM方法的主要步骤如下：
1) 初始计算所有顶点上界，后续通过增量更新替代重新计算；
2) 按顶点度数排序，优先处理高degree顶点，若其上限 ≤ 下界则删除，并将受影响的邻域顶点加入删除队列；
3) 基于队列批量处理待删顶点，减少迭代次数。
DRM方法通过减少上界的重新计算和动态更新上界的方式，显著提高了约减过程的效率。尤其适用于大规模图，因此，本文提出的G_NP算法将基于DRM方法进行优化改进，实现对于输入图的单次约减，进而初步缩减问题规模，降低后续问题求解难度。
2.2. 最大k-Defective Clique问题的约减策略
最大k-defective clique问题的约减基于顶点度数与缺失边约束，通过规则化筛选删除不可能属于最优解的顶点和边。核心思路是：若顶点度数小于“当前下界-k”，则必然不属于最大k-defective clique，可直接删除。在此基础上，衍生出以下关键约减规则：
顶点删除规则：若顶点v的度数 + 邻域顶点数 + 可添加顶点数 < 当前下界，则删除v；若顶点度数 < 允许缺失边数k，直接删除。
边删除规则：若移除边(u, v)不影响最大k-defective clique的搜索(即边的存在与否不改变上界与下界的关系)，则删除该边。
约减过程通过分支定界框架实现：初始化下界后，迭代应用上述规则删除冗余元素，同步更新上下界，直至无法进一步约减。该策略能有效压缩搜索空间，尤其适用于稀疏图场景。
3. 约减算法的设计
3.1. 最大k-Club问题的约减算法
3.1.1. NukCP约减算法
NukCP是求解最大k-club问题的高效局部搜索算法，适用于大规模实例，核心包含两项策略：
动态约减策略(Dynamic Reduction Strategy, DRM)：通过动态更新顶点上界(而非重新计算)减少迭代次数，在简化图上执行计算以提升效率。
分层阈值配置检查策略(Stratified Threshold Configuration Checking, STCC)：针对k-club需多级邻域信息的特性，为不同层级邻域设置优先级，结合生成树动态维护邻域信息，解决局部搜索循环问题，提升搜索多样性。
NukCP通过融合上述策略，有效提高了最大k-club问题的求解效率与质量，为大规模图处理提供了可行方案，并为同类问题研究提供了新思路。
3.1.2. G_NP算法的设计思路
G_NP算法基于NukCP与DRM策略优化，聚焦于快速缩减图规模，设计要点包括：
顶点排序：按顶点度数降序排列，优先处理高连通性顶点；
k阶邻居统计：计算每个顶点的k阶邻居数量，作为筛选依据；
约减逻辑：若顶点k阶邻居数 ≤ lb-1，则判定为冗余并删除；
动态维护：通过数组记录剩余顶点，删除冗余顶点后同步更新其邻域顶点的k阶邻居数，确保约减后图结构的一致性。
该算法可简化原始图，且保留寻找最大k-club的关键信息，缩减搜索空间并提升效率，这对大规模图至关重要，但因其顶点和边众多，直接搜索会在计算上非常耗时。
3.1.3. G_NP算法中图的约减过程
算法通过Reduce GraphInit函数实现，分为两个核心阶段：
1) 动态计算阶段：遍历顶点并计算k阶邻居数，存储于g_degree_k数组；
2) 迭代删除阶段：对k阶邻居数 ≤ lb-1的顶点，加入删除队列并从剩余顶点集(g_remaining)中移除；删除顶点后，更新其邻域顶点的g_degree_k值，若更新后满足删除条件则加入队列，直至无冗余顶点。
该过程通过单次遍历与队列批量处理，减少了重复计算，在大规模图上表现出较高时间效率。
Figure 1. G_NP code section (part one)
图1. G_NP代码部分(一)
3.1.4. G_NP的代码部分
本算法的主要作用是简化图的结构，完成一次约减过程，便于后续的求解及算法更高效地运行，为之后的最大k-club问题求解完成预处理部分，其中关键的代码如图1、图2和图3所示。
Figure 2. G_NP code section (part two)
图2. G_NP代码部分(二)
Figure 3. Part (3) of the G_NP code
图3. G_NP代码部分(三)
函数ReduceGraphInit实现图的约减过程，通过移除冗余顶点简化图结构并保留关键性质，关键执行逻辑包括：
阈值初始化：设置degree_lb = lb-1作为顶点筛选阈值；
k阶邻居计算：通过广度优先搜索(BFS)计算各顶点k阶邻居数，并结合时间限制动态终止计算；
队列驱动的约减：利用FIFO队列批量处理待删顶点，同步更新邻接表与剩余顶点数组，确保约减后图仍保留最大k-club的关键信息。
3.2. 最大k-Defective Clique问题的约减算法
3.2.1. KDBB约减算法
KDBB算法是专为求解最大k-defective clique问题设计的精确算法，基于分支定界框架，通过引入新技术提升大规模稀疏图的处理效率。该算法系统枚举候选解并剪枝不可行分支，提出新的上下界估计方法及规约规则以移除冗余顶点和边，减少搜索空间；同时结合顶点度数等启发式信息排序候选顶点，优化搜索方向。KDBB在大规模稀疏图的MDCP问题上表现出显著优势，尤其在效率和性能方面。
3.2.2. G_KD算法的设计思路
G_KD算法用于图的预处理约减，旨在移除不可能属于最大k-defective clique的顶点和边，以缩减搜索空间。该算法借鉴KDBB算法及约减规则，通过以下步骤实现单次约减(为后续求解预处理)：
删除标记初始化：通过v_del数组记录待删顶点；
冗余顶点识别：利用vertex_judge函数筛选度数 ≤ lb-k的顶点(此类顶点不可能属于最大k-defective clique)；
图结构更新：建立v_map数组映射剩余顶点的新索引，重建邻接表(t_graph_tbl)与边集(t_edge)，仅保留剩余顶点间的边；
内存优化：释放原图内存，更新顶点数、边数及指针至新图结构。
3.2.3. G_KD算法中图的约减过程
1) 顶点和边的删除：通过队列批量处理待删顶点，删除时同步更新邻接顶点的度数与剩余边数；
2) 更新图的拓扑结构：基于v_map映射剩余顶点，重建邻接表与边集，自动剔除与删除顶点相关的边；
3) 最终更新：替换原图指针为新图结构，确保后续求解基于简化后的图执行。
Figure 4. Part of G_KD code (part one)
图4. G_KD代码部分(一)
Figure 5. Part of G_KD code (part two)
图5. G_KD代码部分(二)
Figure 6. Part of G_KD code (part three)
图6. G_KD代码部分(三)
3.2.4. G_KD的代码部分
G_KD算法通过删除度数 ≤ lb-k的顶点、重编号剩余顶点及更新边连接，实现图的简化，以提升后续操作效率(关键代码见图4~6所示)。其核心函数first_reduction的关键执行逻辑包括：
1) 状态初始化：创建删除队列与顶点状态数组，标记待处理顶点；
2) 迭代约减：基于队列迭代删除满足度数条件的顶点，同步更新邻域顶点的度数与边信息；
3) 图结构重建：通过顶点映射数组重建邻接表，仅保留有效边，结合内存释放与指针更新完成图简化。
4. 实验结果与分析
4.1. 实验运行环境配置及用例
4.1.1. 相关数据集的介绍
Facebook社交网络数据集：Facebook数据集来源于Facebook社交网络转换形成的图，其中顶点表示一个账号，边表示账号之间相互关注。这部分用例被Gao等人[8]最初收集用于验证最大k-defective clique算法的求解性能。该数据集总共拥有114个测试用例，本文从中挑选了10个用于测试所提出的G_NP和G_KD算法。
Network Data Repository数据集：Network Data Repository收集了来自各个领域的网络图模型，这些图模型具有不同的规模和属性，并且被广泛应用于各类科学研究中。该数据集总共拥有139个测试用例，本文从中挑选了具有代表性的10个用例，这些用例也在最小顶点覆盖、图染色等问题中被作为基准用例。
4.1.2. G_NP和G_KD算法实验环境
算法实现语言：C++
编译器：g++，使用‘-O3’选项进行编译
实验平台：Workstation17.虚拟机8GB运行内存，运行CentOSLinux7.5操作系统
时间限制：每个实例的截止时间为300秒(5分钟)
参数设置：其中G_NP算法中的k取值为2，3，4，运行截止时间为300 s，随机种子为3，而G_KD算法中的k取值分别为1，3，5，10，15，20，运行截止时间为100 s，随机种子为3。
4.2. G_NP算法实验结果
Table 1. The reduction results of G_NP on the Facebook social network dataset (partial)
表1. G_NP在Facebook社交网络数据集上的约减结果(部分)
instance |
初始规模 |
约减后规模 |
K = 2 |
K = 3 |
K = 4 |
socfb-Caltech36.mtx |
V |
769 |
528 |
553 |
582 |
E |
16656 |
14954 |
15334 |
15715 |
socfb-Bowdoin47.mtx |
V |
2252 |
1893 |
1927 |
1967 |
E |
84387 |
80901 |
81562 |
82260 |
socfb-Swarthmore42.mtx |
V |
1659 |
1468 |
1499 |
1537 |
E |
61050 |
59549 |
59968 |
60406 |
(注：表中仅展示约减效果显著的用例，其余用例约减前后规模差异 < 5%，故省略)
本文采用Facebook社交网络数据集验证G_NP算法在最大k-club问题上的约减性能，结果如表1所示，约减效果受图结构影响显著：密集图(如多数Facebook子图)中约减效果有限，因顶点k阶邻居数普遍较大，上界筛选难以生效；而稀疏子图(如socfb-Caltech36)中，k = 2时顶点约减率达31.3%，边约减率达10.2%，效果更优。
Table 2. Reduction results of G_NP on the Network Data Repository dataset (partial)
表2. G_NP在Network Data Repository数据集上的约减结果(部分)
instance |
初始规模 |
约减后规模 |
K = 2 |
K = 3 |
K = 4 |
coAuthorsDBLP |
V |
299067 |
315 |
94326 |
299067 |
E |
977676 |
7043 |
461616 |
977676 |
rgg_n_2_17_s0 |
V |
131072 |
67 |
89645 |
22503 |
E |
728453 |
571 |
51504 |
131747 |
p2p-Gnutella04 |
V |
10876 |
320 |
9012 |
9951 |
E |
39994 |
65 |
37992 |
39040 |
实验结果如表2所示：k值增大时约减难度上升，顶点和边的删除量减少，如coAuthorsDBLP在k = 2时顶点从30万减至315，k = 4时无约减；不同数据集对k值的敏感度不同，图的密度、连通性等特性显著影响约减效果，稀疏图(如rgg_n_2_17_s0)约减率远高于稠密图。
4.3. G_KD算法实验结果
以下是运行截至时间为100 s的运行结果。
Table 3. Reduction results (partial) of the G_KD algorithm on the Facebook social network dataset (partial)
表3. G_KD算法在Facebook社交网络数据集上的约减结果(部分)
instance |
初始规模 |
约减后规模 |
K = 1 |
K = 3 |
K = 5 |
K = 10 |
K = 15 |
K = 20 |
Socfb-Amherst41. mtx |
V |
2235 |
1894 |
1931 |
1967 |
2052 |
2127 |
2235 |
E |
90954 |
87720 |
88402 |
88988 |
90091 |
90689 |
90954 |
socfb-Mich67.mtx |
V |
3748 |
1739 |
1964 |
2123 |
2443 |
2882 |
3303 |
E |
81903 |
57526 |
62723 |
66094 |
71793 |
77348 |
80657 |
socfb-Reed98.mtx |
V |
962 |
637 |
708 |
754 |
866 |
962 |
962 |
E |
18812 |
16244 |
17175 |
17709 |
18578 |
18812 |
18812 |
(注：K = 20时多数用例约减率 < 5%，故省略)
实验结果如表3所示G_KD算法的约减效果随k值增加而减弱：k = 1时部分用例顶点约减率超50% (如socfb-Mich67)，k = 20时约减率接近0；受图结构影响，Haverford76等稠密图在各k值下均无显著约减，因顶点度数普遍较高，难以满足“度数 ≤ lb-k”的删除条件。
5. 总结与展望
5.1. 研究成果及研究局限性
5.1.1. 研究成果
本文研究图约减技术在松弛团问题中的应用，设计了针对最大k-club的G_NP算法(通过动态更新顶点上界、维护多级邻域信息缩减图规模)和针对最大k-defective clique的G_KD算法(通过约减规则减少搜索空间与计算复杂度)。两种算法在大规模稀疏图上表现出效率优势，适用于大小规模图，且在标准测试用例上取得较好结果，为大规模图问题提供了新方法。
5.1.2. 研究局限性
实验表明，图约减技术能提升算法效率(尤其大规模稀疏图)，但性能受参数选择、图结构及k值影响；此外，约减技术虽减少计算量，但最坏情况下的解质量保证仍需突破。
5.2. 未来工作方向及可能的优化措施
未来工作将聚焦于提升算法的适应性与实用性，具体包括：开发结合图拓扑特征动态调整规则的自适应约减机制，降低对参数和图结构的依赖；构建跨k-club与k-defective clique的通用约减框架，实现多松弛团模型兼容；基于分布式框架设计并行算法，突破超大规模图的单机处理瓶颈；并在社交网络、生物网络等实际场景中验证优化，增强工程应用价值。
NOTES
*通讯作者。