Incremental Maintenance of Maximal Bicliques in a Dynamic Bipartite Graph

Thumbnail Image
Date
2018-02-06
Authors
Das, Apurba
Tirthapura, Srikanta
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Person
Research Projects
Organizational Units
Organizational Unit
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Computer ScienceElectrical and Computer Engineering
Abstract

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.

Comments

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.

Description
Keywords
Citation
DOI
Copyright
Mon Jan 01 00:00:00 UTC 2018
Collections