Efficient maintenance for maximal bicliques in bipartite graph streams

Maximal biclique enumeration is a fundamental problem in analysing bipartite graphs, which has a wide range of real applications, such as web mining, recommendation systems, and social network analysis. As real-world bipartite graphs constantly evolve over time, it is useful and necessary to incrementally maintain maximal bicliques in dynamic bipartite graphs. Existing solutions for this problem suffer from the major issue of enumerating duplicate maximal bicliques, which inevitably bring huge computation overhead. In this paper, we devise a novel framework to efficiently maintain maximal bicliques when the graph evolves with edge insertions. There are two major steps, i.e., new maximal biclique enumeration and subsumed maximal biclique enumeration. In particular, we sort edges in order when a batch of edges is inserted or removed. Based on the sequence of edges, we construct a recursion search tree to avoid duplicate new maximal bicliques and non-maximal bicliques. Besides, for subsumed maximal biclique eumeration, we first check the maximality of bicliques in an efficient way, and then delete these are no longer maximal. Furthermore, we also show that our techniques can be easily extended to deal with edge deletions. The experiment results demonstrate the efficiency of our techniques, which show a superior performance over the state-of-the-art method.