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
1 - 1 of 1
No Thumbnail Available
- Name:
- 2018_Tirthapura_CountingButterflies.pdf
- Size:
- 763.73 KB
- Format:
- Adobe Portable Document Format
- Description: