Maximum Biplex Search over Bipartite Graphs
Wensheng Luo, Kenli Li, Xu Zhou, Yunjun Gao, Keqin Li
Abstract
As a typical most-to-most connected quasi-biclique model, k-biplex is a superset of bicliques, which allows nodes on each side of a fully connected subgraph to lose at most <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> connections. In this paper, we investigate the maximum biplex search problem for the first time. The goal here is to find a k-biplex with the maximum number of edges and we have proved that the problem is NP-hard. It is widely used in fraudulent reviewer group detection, gene expression analysis, social recommendation, and other real-life applications. To solve this problem, a maximum k-biplex search algorithm (MBS) is first presented by integrating two pruning strategies, including degree-based and 2-hop-based pruning. In addition, we define a new dense subgraph over bipartite graphs, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\langle x, y\rangle$</tex> -core, and develop a core-based maximum k-biplex search algorithm (MBS-Core) which can significantly reduce the search space with the introduction of a core-based graph reduction technique. In particular, it only needs to search these cores instead of the entire graph to obtain the maximum k-biplex. Moreover, a parallel algorithm and a heuristic algorithm are developed to achieve better query performance on larger-scale bipartite graphs. Extensive experiments have been conducted on real-life and synthetic datasets to verify the efficiency and effectiveness of the proposed algorithms. Our results show that MBS-Core is up to 3 orders of magnitude faster than the existing approaches.