Campus Units

Electrical and Computer Engineering, Computer Science

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

2-6-2018

Journal or Book Title

IEEE Transactions on Multi-Scale Computing Systems

DOI

10.1109/TMSCS.2018.2802920

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.

Rights

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.

Copyright Owner

IEEE

Language

en

File Format

application/pdf

Published Version

Share

COinS