Counting Butterfies from a Large Bipartite Graph Stream

dc.contributor.author Sanei-Mehri, Seyed-Vahid
dc.contributor.author Zhang, Yu
dc.contributor.author Sariyuce, Ahmet
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-12-27T00:15:49.000
dc.date.accessioned 2020-06-30T02:02:47Z
dc.date.available 2020-06-30T02:02:47Z
dc.date.copyright Mon Jan 01 00:00:00 UTC 2018
dc.date.issued 2018-01-01
dc.description.abstract <p>We consider the estimation of properties on massive bipartite graph streams, where each edge represents a connection between entities in two different partitions. We present sublinear-space one-pass algorithms for accurately estimating the number of butterflies in the graph stream. Our estimates have provable guarantees on their quality, and experiments show promising tradeoffs between space and accuracy. We also present extensions to sliding windows. While there are many works on counting subgraphs within unipartite graph streams, our work seems to be one of the few to effectively handle bipartite graph streams.</p>
dc.description.comments <p>This is a pre-print of the article Sanei-Mehri, Seyed-Vahid, Yu Zhang, Ahmet Erdem Sariyuce, and Srikanta Tirthapura. "Counting Butterfies from a Large Bipartite Graph Stream." <em>arXiv preprint arXiv:1812.03398 </em>(2018). Posted with permission.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/ece_pubs/203/
dc.identifier.articleid 1204
dc.identifier.contextkey 13496723
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath ece_pubs/203
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/21031
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/ece_pubs/203/2018_Tirthapura_CountingButterflies.pdf|||Fri Jan 14 22:23:09 UTC 2022
dc.subject.disciplines Computer Sciences
dc.subject.disciplines Electrical and Computer Engineering
dc.title Counting Butterfies from a Large Bipartite Graph Stream
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
Name:
2018_Tirthapura_CountingButterflies.pdf
Size:
763.73 KB
Format:
Adobe Portable Document Format
Description:
Collections