Incremental Maintenance of Maximal Bicliques in a Dynamic Bipartite Graph

dc.contributor.author Das, Apurba
dc.contributor.author Tirthapura, Srikanta
dc.contributor.author Tirthapura, Srikanta
dc.contributor.department Computer Science
dc.contributor.department Electrical and Computer Engineering
dc.date 2018-04-28T10:49:54.000
dc.date.accessioned 2020-06-30T02:02:32Z
dc.date.available 2020-06-30T02:02:32Z
dc.date.copyright Mon Jan 01 00:00:00 UTC 2018
dc.date.issued 2018-02-06
dc.description.abstract <p>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.</p>
dc.description.comments <p>This is a manuscript of an article published as Das, Apurba, and Srikanta Tirthapura. "Incremental Maintenance of Maximal Bicliques in a Dynamic Bipartite Graph." <em>IEEE Transactions on Multi-Scale Computing Systems</em> (2018). DOI: <a href="http://dx.doi.org/10.1109/TMSCS.2018.2802920" target="_blank">10.1109/TMSCS.2018.2802920</a>. Posted with permission.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/ece_pubs/173/
dc.identifier.articleid 1171
dc.identifier.contextkey 12001154
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath ece_pubs/173
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/20998
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/ece_pubs/173/2018_Tirthapura_IncrementalMaintenance.pdf|||Fri Jan 14 21:20:10 UTC 2022
dc.source.uri 10.1109/TMSCS.2018.2802920
dc.subject.disciplines Computer Sciences
dc.subject.disciplines Electrical and Computer Engineering
dc.subject.keywords Heuristic algorithms
dc.subject.keywords Bipartite graph
dc.subject.keywords Algorithm design and analysis
dc.subject.keywords Maintenance engineering
dc.subject.keywords Time complexity
dc.subject.keywords Itemsets
dc.subject.keywords Data mining
dc.title Incremental Maintenance of Maximal Bicliques in a Dynamic Bipartite Graph
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isAuthorOfPublication b0235db2-0a72-4dd1-8d5f-08e5e2e2bf7d
relation.isOrgUnitOfPublication f7be4eb9-d1d0-4081-859b-b15cee251456
relation.isOrgUnitOfPublication a75a044c-d11e-44cd-af4f-dab1d83339ff
File
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
2018_Tirthapura_IncrementalMaintenance.pdf
Size:
1.31 MB
Format:
Adobe Portable Document Format
Description:
Collections