论文标题
最多$ k $ -BIPLEX搜索在两部分图上：一种对称BK分支方法
Maximum $k$-Biplex Search on Bipartite Graphs: A Symmetric-BK Branching Approach
论文作者
论文摘要
两分图的最大$ k $ biplexes（Mbps）已用于诸如欺诈检测之类的应用。然而，通常存在指数级的MBP，这在列举Mbps时会引发两个问题，即有效性问题（许多Mbps的价值较低）和效率问题（枚举所有MBP在大图上不起作用）。解决此问题的现有建议对要列举每个MBP的顶点的数量施加了约束，但它们仍然不够（例如，它们需要指定约束，通常不易于用户友好，并且不能控制MBP的数量直接被列出）。因此，在本文中，我们研究了找到$ k $ Mbps的问题，其边缘最多称为maxbps，其中$ k $是积极的积分用户参数。新提案很好地避免了现有提案的缺点。我们正式证明了该问题的NP硬度。然后，我们设计了两种分支结合的算法，其中越好的一种称为fastbb的算法提高了最糟糕的时间复杂性到$ o^*（γ_k^n）$，其中$ o^*$抑制了多项式，$γ_k$是$ k $的实际数字，与$ k $相关，并且严格较小，并且比2 $ n $ n $ n $ n $ nebrape nubs norbrices nubs norbrices in norbrices numbers numbers vertices。例如，对于$ k = 1 $，$γ_k$等于$ 1.754 $。我们进一步介绍了三种技术来提高分支结合算法的性能，其中最佳的一种称为PBIE可以将时间复杂性进一步提高到$ o^*（γ_k^{d^3}）$，对于大稀疏图，其中$ d $是图形的最大程度。我们对真实和合成数据集进行了广泛的实验，结果表明，我们的算法比所有基本线都要快四个数量级，并且发现MAXBPS比在欺诈检测应用程序中找到所有MBP都更好。
Enumerating maximal $k$-biplexes (MBPs) of a bipartite graph has been used for applications such as fraud detection. Nevertheless, there usually exists an exponential number of MBPs, which brings up two issues when enumerating MBPs, namely the effectiveness issue (many MBPs are of low values) and the efficiency issue (enumerating all MBPs is not affordable on large graphs). Existing proposals of tackling this problem impose constraints on the number of vertices of each MBP to be enumerated, yet they are still not sufficient (e.g., they require to specify the constraints, which is often not user-friendly, and cannot control the number of MBPs to be enumerated directly). Therefore, in this paper, we study the problem of finding $K$ MBPs with the most edges called MaxBPs, where $K$ is a positive integral user parameter. The new proposal well avoids the drawbacks of existing proposals. We formally prove the NP-hardness of the problem. We then design two branch-and-bound algorithms, among which, the better one called FastBB improves the worst-case time complexity to $O^*(γ_k^ n)$, where $O^*$ suppresses the polynomials, $γ_k$ is a real number that relies on $k$ and is strictly smaller than 2, and $n$ is the number of vertices in the graph. For example, for $k=1$, $γ_k$ is equal to $1.754$. We further introduce three techniques for boosting the performance of the branch-and-bound algorithms, among which, the best one called PBIE can further improve the time complexity to $O^*(γ_k^{d^3})$ for large sparse graphs, where $d$ is the maximum degree of the graph. We conduct extensive experiments on both real and synthetic datasets, and the results show that our algorithm is up to four orders of magnitude faster than all baselines and finding MaxBPs works better than finding all MBPs for a fraud detection application.
