Efficient Maximum (α,β)-Quasi Biclique Computation on Bipartite Graphs

A bipartite cohesive subgraph refers to a bipartite subgraph in which the vertices are highly interconnected. In this paper, we consider the (α,β)-quasi biclique model, which allows for connection proportions on two sides of vertices to be no less than α and β, respectively. Building upon this model, we propose the maximum (α,β)-quasi biclique search problem, which finds applications in various domains, including abnormal behavior detection, community group search, and biological gene expression detection. Due to the inefficiency of the baseline, we design effective preprocessing methods, upper bounding and reduction techniques, and advanced branching strategies, which collectively constitute our optimized algorithm called MVQB. Finally, through extensive experiments on real-world bipartite graphs, we validate the efficiency improvement of our proposed algorithm MVQB over the baseline, which demonstrates a speed improvement of up to six orders of magnitude.