{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:41:58Z","timestamp":1787017318101,"version":"build-2736575974"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T00:00:00Z","timestamp":1641600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Natural Sciences and Engineering Research Council (NSERC) of Canada"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,8,31]]},"abstract":"<jats:p>We study the fundamental problem of butterfly (i.e., (2,2)-bicliques) counting in bipartite streaming graphs. Similar to triangles in unipartite graphs, enumerating butterflies is crucial in understanding the structure of bipartite graphs. This benefits many applications where studying the cohesion in a graph shaped data is of particular interest. Examples include investigating the structure of computational graphs or input graphs to the algorithms, as well as dynamic phenomena and analytic tasks over complex real graphs. Butterfly counting is computationally expensive, and known techniques do not scale to large graphs; the problem is even harder in streaming graphs. In this article, following a data-driven methodology, we first conduct an empirical analysis to uncover temporal organizing principles of butterflies in real streaming graphs and then we introduce an approximate adaptive window-based algorithm, sGrapp, for counting butterflies as well as its optimized version sGrapp-x. sGrapp is designed to operate efficiently and effectively over any graph stream with any temporal behavior. Experimental studies of sGrapp and sGrapp-x show superior performance in terms of both accuracy and efficiency.<\/jats:p>","DOI":"10.1145\/3495011","type":"journal-article","created":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T15:51:00Z","timestamp":1641657060000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["sGrapp: Butterfly Approximation in Streaming Graphs"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5725-1781","authenticated-orcid":false,"given":"Aida","family":"Sheshbolouki","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, Ontario, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8126-1717","authenticated-orcid":false,"given":"M. Tamer","family":"\u00d6zsu","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Ontario, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,1,8]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnx001"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/974750.974756"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505545"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3365676"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545464"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.066102"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1839490.1839494"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.aad9029"},{"key":"e_1_3_1_13_2","volume-title":"Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science","author":"Bera Suman K.","year":"2017","unstructured":"Suman K. Bera and Amit Chakrabarti. 2017. Towards tighter space bounds for counting triangles and other substructures in graph streams. In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_21"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3186586"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0036-4"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778638"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2004-00020-6"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3483529.3483688"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020513"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2382577.2382581"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-020-61330-6"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476258"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457538"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.03.007"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036102"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3400903.3400925"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213899"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463704"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2691190.2691193"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904486"},{"key":"e_1_3_1_33_2","doi-asserted-by":"crossref","unstructured":"Zan Huang. 2010. Link prediction based on graph topology: The predictive value of generalized clustering coefficient. https:\/\/ssrn.com\/abstract=1634014.","DOI":"10.2139\/ssrn.1634014"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/2958119.2958158"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.036109"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588563"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2012.625257"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_1_39_2","doi-asserted-by":"crossref","unstructured":"Matthieu Latapy Clemence Magnien and Nathalie Del Vecchio. 2006. Basic notions for the analysis of large affiliation networks\/bipartite graphs. Social Networks 30 1 (2008) 31\u201348. DOI:https:\/\/doi.org\/10.1016\/j.socnet.2007.04.006","DOI":"10.1016\/j.socnet.2007.04.006"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00624-7"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3022186"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.056127"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397234"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364330"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213854"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.026118"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594552"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018731"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.066116"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.67.026112"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220097"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357983"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1209\/0295-5075\/111\/40010"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976021.2"},{"key":"e_1_3_1_59_2","first-page":"141","volume-title":"Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases","author":"Shin Kijung","year":"2018","unstructured":"Kijung Shin, Jisu Kim, Bryan Hooi, and Christos Faloutsos. 2018. Think before you discard: Accurate triangle counting in graph streams with deletions. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 141\u2013157."},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375392"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.101.052305"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.Congress.2014.13"},{"key":"e_1_3_1_63_2","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339497"},{"key":"e_1_3_1_64_2","doi-asserted-by":"publisher","DOI":"10.5555\/876875.878988"},{"key":"e_1_3_1_65_2","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921073"},{"key":"e_1_3_1_66_2","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149197"},{"key":"e_1_3_1_67_2","first-page":"10881","volume-title":"Proceedings of the 37th International Conference on Machine Learning","author":"You Jiaxuan","year":"2020","unstructured":"Jiaxuan You, Jure Leskovec, Kaiming He, and Saining Xie. 2020. Graph structure of neural networks. In Proceedings of the 37th International Conference on Machine Learning. 10881\u201310891."},{"key":"e_1_3_1_68_2","first-page":"265","volume-title":"Proceedings of the International Conference Complex Networks and their Applications","author":"Zhang Jianpeng","year":"2017","unstructured":"Jianpeng Zhang, Kaijie Zhu, Yulong Pei, George H. L. Fletcher, and Mykola Pechenizkiy. 2017. Clustering-structure representative sampling from graph streams. In Proceedings of the International Conference Complex Networks and their Applications. 265\u2013277."},{"key":"e_1_3_1_69_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2008.09.006"},{"key":"e_1_3_1_70_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-55130-8_42"},{"key":"e_1_3_1_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/3400903.3400916"},{"key":"e_1_3_1_72_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-020-60205-0"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3495011","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3495011","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:49:19Z","timestamp":1750178959000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3495011"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,8]]},"references-count":71,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8,31]]}},"alternative-id":["10.1145\/3495011"],"URL":"https:\/\/doi.org\/10.1145\/3495011","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,8]]},"assertion":[{"value":"2021-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}