Incremental Maintenance of Maximal Bicliques in a Dynamic Bipartite Graph
Is Version Of
We consider incremental maintenance of maximal bicliques from a dynamic bipartite graph that changes over time due to the addition of edges. When new edges are added to the graph, we seek to enumerate the change in the set of maximal bicliques, without enumerating the set of maximal bicliques that remain unaffected. The challenge is to enumerate the change without explicitly enumerating the set of all maximal bicliques. In this work, we present (1)~Near-tight bounds on the magnitude of change in the set of maximal bicliques of a graph, due to a change in the edge set, and an (2)~Incremental algorithm for enumerating the change in the set of maximal bicliques. For the case when a constant number of edges are added to the graph, our algorithm is "change-sensitive", i.e., its time complexity is proportional to the magnitude of change in the set of maximal bicliques. To our knowledge, this is the first incremental algorithm for enumerating maximal bicliques in a dynamic graph, with a provable performance guarantee. Experimental results show that its performance exceeds that of baseline implementations by orders of magnitude.
This is a manuscript of an article published as Das, Apurba, and Srikanta Tirthapura. "Incremental Maintenance of Maximal Bicliques in a Dynamic Bipartite Graph." IEEE Transactions on Multi-Scale Computing Systems (2018). DOI: 10.1109/TMSCS.2018.2802920. Posted with permission.