Efficient p-Biclique Query on Large Bipartite Networks

The biclique is an important model in finding bipartite cohesive subgraphs. This paper proposes the model of p-biclique and aims to enumerate every p-biclique in a bipartite network. For each vertex u in the p-biclique, at least p fraction of u’s neighbors are inside the biclique, and at most \(1-p\) fraction are outside. Compared with the traditional biclique model, our p-biclique model can guarantee the engagement level of vertices, thus providing bicliques with higher quality. We propose an efficient algorithm for enumerating maximal p-bicliques in a bipartite network. The algorithm incorporates three novel rules for graph reduction that can significantly improve empirical efficiency. The experiments on real-world networks demonstrate that our algorithm is efficient and our model is effective.