Electrical and Computer Engineering, Computer Science
Journal or Book Title
IEEE Transactions on Multi-Scale Computing Systems
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.
Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Das, Apurba and Tirthapura, Srikanta, "Incremental Maintenance of Maximal Bicliques in a Dynamic Bipartite Graph" (2018). Electrical and Computer Engineering Publications. 173.