{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T23:35:41Z","timestamp":1791588941745,"version":"4.3.4"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,1,31]],"date-time":"2018-01-31T00:00:00Z","timestamp":1517356800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"AFOSR\/AOARD","award":["FA2386-16-1-4044"],"award-info":[{"award-number":["FA2386-16-1-4044"]}]},{"name":"High Performance Big Data Analytics Platform Performance Acceleration Technologies Development","award":["R0190-15-2012"],"award-info":[{"award-number":["R0190-15-2012"]}]},{"name":"Research Resettlement Fund for the new faculty of Seoul National University"},{"name":"Institute for Information communications Technology Promotion (IITP) grant funded by the Korea government"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2018,2,28]]},"abstract":"<jats:p>How can we estimate local triangle counts accurately in a graph stream without storing the whole graph? How to handle duplicated edges in local triangle counting for graph stream? Local triangle counting, which computes the number of triangles attached to each node in a graph, is a very important problem with wide applications in social network analysis, anomaly detection, web mining, and the like.<\/jats:p>\n          <jats:p>\n            In this article, we propose algorithms for local triangle counting in a graph stream based on edge sampling: M\n            <jats:sc>ascot<\/jats:sc>\n            for a simple graph, and M\n            <jats:sc>ulti<\/jats:sc>\n            BM\n            <jats:sc>ascot<\/jats:sc>\n            and M\n            <jats:sc>ulti<\/jats:sc>\n            WM\n            <jats:sc>ascot<\/jats:sc>\n            for a multigraph. To develop M\n            <jats:sc>ascot<\/jats:sc>\n            , we first present two naive local triangle counting algorithms in a graph stream, called M\n            <jats:sc>ascot<\/jats:sc>\n            -C and M\n            <jats:sc>ascot<\/jats:sc>\n            -A. M\n            <jats:sc>ascot<\/jats:sc>\n            -C is based on constant edge sampling, and M\n            <jats:sc>ascot<\/jats:sc>\n            -A improves its accuracy by utilizing more memory spaces. M\n            <jats:sc>ascot<\/jats:sc>\n            achieves both accuracy and memory-efficiency of the two algorithms by unconditional triangle counting for a new edge, regardless of whether it is sampled or not. Extending the idea to a multigraph, we develop two algorithms M\n            <jats:sc>ulti<\/jats:sc>\n            BM\n            <jats:sc>ascot<\/jats:sc>\n            and M\n            <jats:sc>ulti<\/jats:sc>\n            WM\n            <jats:sc>ascot<\/jats:sc>\n            . M\n            <jats:sc>ulti<\/jats:sc>\n            BM\n            <jats:sc>ascot<\/jats:sc>\n            enables local triangle counting on the corresponding simple graph of a streamed multigraph without explicit graph conversion; M\n            <jats:sc>ulti<\/jats:sc>\n            WM\n            <jats:sc>ascot<\/jats:sc>\n            considers repeated occurrences of an edge as its weight and counts each triangle as the product of its three edge weights. In contrast to the existing algorithm that requires prior knowledge on the target graph and appropriately set parameters, our proposed algorithms require only one parameter of edge sampling probability.\n          <\/jats:p>\n          <jats:p>\n            Through extensive experiments, we show that for the same number of edges sampled, M\n            <jats:sc>ascot<\/jats:sc>\n            provides the best accuracy compared to the existing algorithm as well as M\n            <jats:sc>ascot<\/jats:sc>\n            -C and M\n            <jats:sc>ascot<\/jats:sc>\n            -A. We also demonstrate that M\n            <jats:sc>ulti<\/jats:sc>\n            BM\n            <jats:sc>ascot<\/jats:sc>\n            on a multigraph is comparable to M\n            <jats:sc>ascot<\/jats:sc>\n            -C on the counterpart simple graph, and M\n            <jats:sc>ulti<\/jats:sc>\n            WM\n            <jats:sc>ascot<\/jats:sc>\n            becomes more accurate for higher degree nodes. Thanks to M\n            <jats:sc>ascot<\/jats:sc>\n            , we also discover interesting anomalous patterns in real graphs, including\n            <jats:italic>core-peripheries<\/jats:italic>\n            in the web, a\n            <jats:italic>bimodal<\/jats:italic>\n            call pattern in a phone call history, and\n            <jats:italic>intensive collaboration<\/jats:italic>\n            in DBLP.\n          <\/jats:p>","DOI":"10.1145\/3022186","type":"journal-article","created":{"date-parts":[[2018,2,1]],"date-time":"2018-02-01T13:10:52Z","timestamp":1517490652000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Memory-Efficient and Accurate Sampling for Counting Local Triangles in Graph Streams"],"prefix":"10.1145","volume":"12","author":[{"given":"Yongsub","family":"Lim","sequence":"first","affiliation":[{"name":"Seoul National University, Seoul, South Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Minsoo","family":"Jung","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, South Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"U.","family":"Kang","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, South Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,1,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623757"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13672-6_40"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505545"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/1929861.1929864"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339539"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms.\u00a0 623--632","author":"Bar-Yossef Ziv"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839490.1839494"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.056119"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020513"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2009.120"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939771"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062745.1062885"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.032093399"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463704"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487678"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2700395"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11533719_72"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_53"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2022850.2022852"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.244"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588563"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433480"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.07.017"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783285"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Ron Milo Shai Shen-Orr Shalev Itzkovitz Nadav Kashtan Dmitri Chklovskii and Uri Alon. 2002. Network motifs: Simple building blocks of complex networks. Science 298 5594 (2002) 824--827.  Ron Milo Shai Shen-Orr Shalev Itzkovitz Nadav Kashtan Dmitri Chklovskii and Uri Alon. 2002. Network motifs: Simple building blocks of complex networks. Science 298 5594 (2002) 824--827.","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487696"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594552"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.12.007"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505563"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939757"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2662017"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556569"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970397"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_54"},{"key":"e_1_2_1_38_1","volume-title":"Editorial: Which wei wang? Physical Review Special Topics\u2014Accelerators and Beams 10, 12","author":"Sprouse Gene D.","year":"2007"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634169"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339722"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556213"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_2_1_44_1","first-page":"752","article-title":"Visualizing the signatures of social roles in online discussion groups","volume":"8","author":"Welser Howard T.","year":"2007","journal-title":"Journal of Social Structure"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556609"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3022186","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3022186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:54Z","timestamp":1750220634000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3022186"}},"subtitle":["From Simple to Multigraphs"],"short-title":[],"issued":{"date-parts":[[2018,1,31]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2,28]]}},"alternative-id":["10.1145\/3022186"],"URL":"https:\/\/doi.org\/10.1145\/3022186","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,31]]},"assertion":[{"value":"2015-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}