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

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

Key words: bipartite graph; cohesive subgraph mining; k-defective biclique

随着信息技术的广泛应用, 各领域产生了大量关系复杂的图数据, 如社交网络数据、生物信息网络数据以及
金融交易数据等. 这些网络数据中通常包含了许多的稠密子图结构, 如何从图数据中挖掘稠密子图结构是图分析
中一个重要的研究问题. 因为, 稠密子图挖掘问题在社交网络分析 [1] 、蛋白质络合物分析 [2] 以及金融统计分析 [3] 等
领域具有重要的应用价值. 例如在社交网络数据中, 稠密子图挖掘可以用于了解社区的内在结构特征, 识别用户群
体之间的重要联系, 以及发现潜在的社交圈子或社交事件, 对社交媒体营销、舆情分析以及社交网络动态的理解
具有重要意义.
然而, 某些特定领域中的数据一般具有不同的实体, 而且实体之间的关系仅在不同类型的实体之间产生, 利用
传统图结构对数据进行建模已经无法满足各领域的应用需求. 例如电子商务中用户与商品的关系数据 [4] 、合作网
络中作者与出版物的关系数据 [5] 、社交网络中用户与网页间的关系数据 [6] 以及生物信息网络中基因与蛋白质的
关系数据 [7] 等均存在不同的实体. 为此, 一种常见的图结构, 即二部图, 也广泛用于建模现实应用中包含不同实体
类型的图数据, 其表示顶点可以分为两个相互独立的集合, 并且图上每条边上的顶点分别属于不同的集合中.
二团作为二部图中一种基本的稠密子图模型, 其表示为完全二部图子图, 即相互独立的集合 X 和 Y 之间的任
何一对顶点都存在边连接. 由于该模型在社区检测 [8−11] 、欺诈检测 [12] 和生物网络分析 [13] 等领域的重要应用价值,
研究者针对极大二团枚举问题进行了广泛研究, 并提出了一系列的高效算法 [14−20] . 然而, 要求二部图中两部分顶点
集中任意一对顶点都存在边连接可能过于严格, 因为许多真实的二部图数据是基于传感器或者实验数据而收集生
成的, 其中可能存在噪声或者错误. 此外, 在二部图数据中, 对于没有直接连接关系的顶点仍然可能具有较强的关
联关系. 例如在电子商务的刷单行为检测中, 欺诈用户与被刷单的产品形成了一种稠密子图结构, 但每个欺诈用户
可能不会对同一组商品进行频繁刷单. 因此, 利用二团模型进行欺诈检测极有可能导致挖掘结果不准确. 为了提高
实际应用的效果, 一种可行的解决方法是从二部图数据中挖掘松弛的二团子图以替代二团模型的挖掘任务.
近年来, 研究者们还提出了许多其他的松弛的二团模型, 例如 (α, β)-核 [21] 、k-bitruss [22] 以及 k-biplex [23] 等. 然
而, 上述松弛的二团模型在特定应用场景中仍然存在各自的缺陷性. 具体地, 基于最小度定义的 (α, β)-核模型和基
于蝴蝶 (2×2 的二团) 数量定义的 k-bitruss 模型对子图的稠密度的限制过于松弛. 此类模型在处理真实图数据时,
可能导致检索出的子图社区规模过大 k-缺陷二团模型, 当设置
(顶点数量可能多达上千甚至上万个). 这样的结果可能无法直接使用, 仍然
需要耗费较高的人力资源进行进一步的筛选. 此外, 虽然基于非邻居数量定义的 k-biplex 模型可以搜索到规模较
小的社区结构, 但该模型仍然难以细粒度地检索二部图中社区的不同结构关系. 例如, 若二部图中稠密子图两边顶
点数不大于 6 时, 该模型只能将 k 设置为 1 或者 2, 难以发现具有不同结构的社区.
为了解决上述问题, 本文将传统图数据中一种广泛研究的 k-缺陷团模型 [24] 引入至二部图数据的稠密子图建
模中, 并提出了一种称之为 k-缺陷二团的稠密子图模型. 该模型表示与完全子图二团相差最多 k 条边的二部图子
k = 0 时, k-缺陷二团等价于二团, 为此提出的模型是二团模型的一种泛化, 可为稠密子图挖掘任务提
图. 显然, 当
供更高的灵活性 (基于不同的 k 值搜索不同的稠密子图). 此外, 相较于 k-biplex, k-缺陷二团模型是基于缺失的边
数 k 约束稠密子图的, 可以基于不同的阈值 k 以更细粒度地检测社区的结构变化情况. 图 1 进一步说明了提出的 k-
缺陷二团模型相较于二团模型在真实社区挖掘中的优势. 具体地, 图 1(a) 展示了互联网电影资料库 (https://www.
imdb.com/) 中包含 8 部电影和 8 个演员的二部图网络, 可以看出基于二团模型仅可以挖掘出 3×3 的二团社区关
系 (图 1(b) 所示). 然而, 基于提出的 k 大于 0 时, 可以得到具有更多关系的稠密子图社区.
如当 k=3 时, 所提模型可以挖掘出 4×4 的社区关系 (图 1(c)). 此外, 所得社区仍然具有较高的稠密度, 表示所提模
型在社区挖掘方面具有实际意义. 基于 Yannakakis 定理 [25] , 从二部图中枚举极大二团是一个 NP-难问题. 为此, 如
何设计高效的算法从二部图中枚举极大 k-缺陷二团是一个极具挑战的问题. 针对该问题, 本文提出了一种新的对
称集合枚举技术. 其主要思想是, 设 D 为集合 S 的非共同邻居集合, 当枚举包含 S 的极大 k-缺陷二团时, 当前任务
可以划分为包含 S 和 D 中前 i 个顶点但不包含第 i+1 个顶点的子任务, 其中 0 ⩽ i ⩽ k . 由于 k-缺陷二团中最多允
许缺失 k 条边, 则子任务的个数最多被限制在 k +1 个以内.