BBK: a simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs

双分图是现实世界网络的一种普遍建模工具，捕捉到两种不同类型顶点之间的交互。在这个框架内，当研究密集子图时，双完全子图是关键的结构：它们是顶点的集合，使得第一类顶点与第二类顶点的所有顶点相互作用。因此，它们允许识别网络中密切相关的顶点组，例如具有相似兴趣的个人或具有相似内容的网页。本文介绍了一种新的算法，用于枚举双分图中最大双完全子图。这个算法被称为BBK（双分Bron-Kerbosch），是Bron-Kerbosch算法的双分图扩展，该算法枚举标准（非双分图）图中的最大团。它比现有算法更快，并允许枚举无法通过现有实现进行管理的大型双分图。我们在理论上对其进行了分析，以建立两个复杂度公式：一个作为输入特征的函数，一个作为算法输出特征的函数。我们还提供了BBK的C ++开放访问实现，用于实验和验证其在大规模真实数据集上的效率，并显示其执行时间实际上比现有算法更短。这些实验还表明，处理顶点的顺序以及选择哪种类型的顶点来启动枚举会影响计算时间。

本文旨在介绍一种新的算法，用于在二分图中枚举最大双团。这个算法被称为BBK算法，主要是为了解决在大规模的二分图中枚举最大双团的问题。

BBK算法是一种新的扩展到二分图情况下的Bron-Kerbosch算法，它比现有的算法更快，并允许在现有实现无法管理的大规模二分图上进行枚举。

本文提供了C++的BBK算法的开源实现，并在大规模真实数据集上验证了其效率。实验表明，BBK算法的执行时间比现有算法短。文章还分析了BBK算法的理论复杂度，并探讨了顶点处理顺序和枚举起始顶点类型选择对计算时间的影响。

近期在这个领域中，还有一些相关的研究，例如《Efficient algorithms for listing comaximal and non-maximal cliques in large graphs》和《A Fast Algorithm for Enumerating Maximal Bicliques》。