2024/09/27 by Xu, Zhenxiang, Liu, Yiping, Zhou, Yi +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Retrieval (cs.IR)
paper · doi:10.48550/arxiv.2409.18473
In a bipartite graph, a subgraph is an s-biplex if each vertex of the subgraph is adjacent to all but at most s vertices on the opposite set. The enumeration of s-biplexes from a given graph is a fundamental problem in bipartite graph analysis. However, in real-world data engineering, finding all s-biplexes is neither necessary nor computationally affordable. A more realistic problem is to identify some of the largest s-biplexes from the large input graph. We formulate the problem as the \em top-k s-biplex search (TBS) problem, which aims to find the top-k maximal s-biplexes with the most vertices, where k is an input parameter. We prove that the TBS problem is NP-hard for any fixed k≥ 1. Then, we propose a branching algorithm, named MVBP, that breaks the simple 2n enumeration algorithm. Furthermore, from a practical perspective, we investigate three techniques to improve the performance of MVBP: 2-hop decomposition, single-side bounds, and progressive search. Complexity analysis shows that the improved algorithm, named FastMVBP, has a running time O^*(γsd2), where γs<2, and d2 is a parameter much smaller than the number of vertex in the sparse real-world graphs, e.g. d2 is only 67 in the AmazonRatings dataset which has more than 3 million vertices. Finally, we conducted extensive experiments on eight real-world and synthetic datasets to demonstrate the empirical efficiency of the proposed algorithms. In particular, FastMVBP outperforms the benchmark algorithms by up to three orders of magnitude in several instances.