高效搜索大规模二分图中具有时间复杂度保证的Top-k s-Biplexes研究

研究人员针对大规模二分图分析中枚举所有s-biplexes计算成本过高的问题，提出了Top-k s-biplex搜索(TBS)问题，开发了基于分支算法的MVBP框架，并通过2-hop分解、单边边界等技术优化为FastMVBP算法，将时间复杂度降至O*(γs d2 )，在真实数据集上实现三个数量级的性能提升，为社交网络分析和欺诈检测等应用提供了高效解决方案。

　　

在当今大数据时代，二分图作为一种重要的数据结构，被广泛应用于社交网络、电子商务和生物信息学等领域。这类图形由两个互不相连的顶点集合构成，能够清晰描述用户-商品、基因-蛋白质等二元关系。其中，s-biplex（s-双plex）作为一种特殊子图结构，允许每个顶点最多缺失s条边连接，比传统的双团（biclique）更具现实适用性。然而，现有方法在应对大规模图数据时面临严峻挑战——枚举所有s-biplex不仅计算成本高昂，还会产生大量无意义的小规模结果。

针对这一难题，国内研究人员开展了开创性研究，提出了Top-k s-biplex搜索（TBS）问题，旨在高效找出规模最大的k个极大s-biplex。该研究首先证明了TBS问题对于任意固定k≥1都是NP难问题，随后设计出突破性的解决方案。相关成果发表在《Expert Systems with Applications》上，为图数据分析提供了新的方法论。

研究团队采用多管齐下的技术路线：首先基于Bron-Kerbosch框架开发基础分支算法MVBP；进而引入创新的2-hop分解技术将子图规模从O(Δ³
)降至O(Δ²
)；设计单边边界策略实现更激进的剪枝；最后通过渐进式搜索动态调整目标尺寸边界。这些技术创新共同构成了最终的FastMVBP算法。

【A Basic Branching algorithm】部分展示了核心算法框架。MVBP算法通过系统性地探索解空间，避免了暴力枚举的O*(2ⁿ
)复杂度，将时间降至O*(γ_s
ⁿ
)，其中γ_s
<2是与s相关的参数。

【An Improved Algorithm】章节详细阐述了三大优化技术：2-hop分解利用图稀疏性特征，在AmazonRatings等真实数据集上将参数d₂
压缩至67（对应n=3,376,972）；单边边界策略分别为左右顶点集设计独立边界条件；渐进式搜索则通过启发式调整加速收敛。

实验验证环节选取8个真实数据集进行系统评测。在YouTube数据集上，FastMVBP搜索1-biplex仅需10.644秒，较FastBB和ListPlex分别提速50倍和1300倍。这种性能优势在社交推荐任务中转化为更精准的共同兴趣群体识别能力。

这项研究的重要意义在于：理论上，首次严格证明了TBS问题的计算复杂性，并建立了γ_s
<2的时间复杂度上界；工程上，通过2-hop分解等创新将指数项从n降至d₂
，使算法具备处理百万级顶点图的能力；应用上，为欺诈检测、社区发现等场景提供了可扩展的解决方案。研究团队在CRediT声明中明确标注了各位作者的贡献，其中Zhenxiang Xu负责软件开发验证，Yiping Liu进行形式化分析，Zhou Yi教授承担了核心概念构建和论文指导工作。

该成果的潜在应用价值值得期待。在电子商务领域，基于TBS的异常检测系统可识别协同刷评行为；在生物医学中，有助于发现基因调控模块；社交网络分析则能更精准定位兴趣社区。未来研究方向可能包括：开发分布式实现以应对超大规模图数据，探索近似算法保证，以及拓展到动态图场景等。