TopK-BC: Efficient Maintenance of Top k (p,q)-bicliques over Streaming Bipartite Graphs

Bipartite graphs are ubiquitous, such as E-commerce network and gene networks. Efficient analysis of (p, q)- biclique is one of the important problems over bipartite graphs. However, existing works over (p, q)-biclique suffer from two main challenges. Firstly, most of them only focus on static graphs, while lots of bipartite graph-structured data are constantly created in real world, forming streaming bipartite graphs. Secondly, results of (p, q)-biclique could be of exponential scale, which may overwhelm analysts. Hence, computing top$k$most important (p, q)-bicliques is worth considering. In this paper, we study a new problem to maintain top$k$densest (p, q)-bicliques over a streaming bipartite graph. We propose a new framework, called as TopK-BC, to compute the proposed problem effectively. We design an efficient pruning strategy for edge deletion stage, called IDpruning. In particular, we maintain an intermediate density for each edge to efficiently compute high-density (p, q)-bicliques. Also, we introduce effective optimization technologies to filter out unpromising intermediate results and further enhance the performance. Extensive experiments over real world datasets confirm the efficiency and effectiveness of our solution.