{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T17:17:04Z","timestamp":1780766224236,"version":"3.54.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,10]]},"abstract":"<jats:p>\n            Counting triangles in a large graph is important for detecting network anomalies such as spam web pages and suspicious accounts (e.g., fraudsters and advertisers) on online social networks. However, it is challenging to compute the number of triangles in a large graph represented as a stream of edges with a low computational cost when given a limited memory. Recently, several effective sampling-based approximation methods have been developed to solve this problem. However, they assume the graph stream of interest contains no duplicate edges, which does not hold in many real-world graph streams (e.g., phone calling networks). In this paper, we observe that these methods exhibit a large estimation error or computational cost even when modified to deal with duplicate edges using deduplication techniques such as Bloom filter and hash-based sampling. To solve this challenge, we design a one-pass streaming algorithm for uniformly sampling distinct edges at a high speed. Compared to state-of-the-art algorithms, our algorithm reduces the sampling cost per edge from\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>k<\/jats:italic>\n            ) (\n            <jats:italic>k<\/jats:italic>\n            is the maximum number of sampled edges determined by the available memory space) to\n            <jats:italic>O<\/jats:italic>\n            (1) without using any additional memory space. Based on sampled edges, we develop a simple yet accurate method to infer the number of triangles in the original graph stream. We conduct extensive experiments on a variety of real-world large graphs, and the results demonstrate that our method is several times more accurate and faster than state-of-the-art methods with the same memory usage.\n          <\/jats:p>","DOI":"10.14778\/3149193.3149197","type":"journal-article","created":{"date-parts":[[2017,12,12]],"date-time":"2017-12-12T18:33:38Z","timestamp":1513103618000},"page":"162-175","source":"Crossref","is-referenced-by-count":43,"title":["Approximately counting triangles in large graph streams including edge duplicates with a fixed memory usage"],"prefix":"10.14778","volume":"11","author":[{"given":"Pinghui","family":"Wang","sequence":"first","affiliation":[{"name":"Xi'an Jiaotong University, China and Shenzhen Research Institute of Xi'an Jiaotong University, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yiyan","family":"Qi","sequence":"additional","affiliation":[{"name":"Xi'an Jiaotong University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yu","family":"Sun","sequence":"additional","affiliation":[{"name":"Xi'an Jiaotong University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiangliang","family":"Zhang","sequence":"additional","affiliation":[{"name":"King Abdullah University of Science and Technology, Thuwal, SA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Tao","sequence":"additional","affiliation":[{"name":"Xi'an Jiaotong University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaohong","family":"Guan","sequence":"additional","affiliation":[{"name":"Xi'an Jiaotong University, China and Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,10]]},"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.5555\/647904.739463"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505545"},{"key":"e_1_2_1_4_1","first-page":"1","volume-title":"RANDOM","author":"Bar-Yossef Z.","year":"2002","unstructured":"Z. Bar-Yossef , T. S. Jayram , R. Kumar , D. Sivakumar , and L. Trevisan . Counting distinct elements in a data stream . In RANDOM , pages 1 -- 10 , 2002 . Z. Bar-Yossef, T. S. Jayram, R. Kumar, D. Sivakumar, and L. Trevisan. Counting distinct elements in a data stream. In RANDOM, pages 1--10, 2002."},{"key":"e_1_2_1_5_1","first-page":"623","volume-title":"SODA","author":"Bar-Yossef Z.","year":"2002","unstructured":"Z. Bar-Yossef , R. Kumar , and D. Sivakumar . Reductions in streaming algorithms, with an application to counting triangles in graphs . In SODA , pages 623 -- 632 , 2002 . Z. Bar-Yossef, R. Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In SODA, pages 623--632, 2002."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839490.1839494"},{"issue":"5","key":"e_1_2_1_7_1","first-page":"2011","article-title":"Tolerating the community detection resolution limit with edge weighting","volume":"83","author":"Berry J. W.","unstructured":"J. W. Berry , B. Hendrickson , R. A. LaViolette , and C. A. Phillips . Tolerating the community detection resolution limit with edge weighting . Physical Review E , 83 ( 5 ):056119+, 2011 . J. W. Berry, B. Hendrickson, R. A. LaViolette, and C. A. Phillips. Tolerating the community detection resolution limit with edge weighting. Physical Review E, 83(5):056119+, 2011.","journal-title":"Physical Review E"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1452520.1452528"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1534"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594546"},{"key":"e_1_2_1_13_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001","unstructured":"T. H. Cormen , C. Stein , R. L. Rivest , and C. E. Leiserson . Introduction to Algorithms . McGraw-Hill Higher Education , 2 nd edition, 2001 . T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson. Introduction to Algorithms. McGraw-Hill Higher Education, 2nd edition, 2001.","edition":"2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.032093399"},{"key":"e_1_2_1_15_1","first-page":"127","volume-title":"AOFA","author":"Flajolet P.","year":"2007","unstructured":"P. Flajolet , E. Fusy , O. Gandouet , and F. Meunier . Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm . In AOFA , pages 127 -- 146 , 2007 . P. Flajolet, E. Fusy, O. Gandouet, and F. Meunier. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm. In AOFA, pages 127--146, 2007."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2015.46"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463704"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.2015.7421397"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487678"},{"key":"e_1_2_1_21_1","first-page":"710","volume-title":"COCOON","author":"Jowhari H.","year":"2005","unstructured":"H. Jowhari and M. Ghodsi . New streaming algorithms for counting triangles in graphs . In COCOON , pages 710 -- 716 , 2005 . H. Jowhari and M. Ghodsi. New streaming algorithms for counting triangles in graphs. In COCOON, pages 710--716, 2005."},{"key":"e_1_2_1_22_1","volume-title":"FURL: fixed-memory and uncertainty reducing local triangle counting for graph streams. CoRR, abs\/1611.06615","author":"Jung M.","year":"2016","unstructured":"M. Jung , S. Lee , Y. Lim , and U. Kang . FURL: fixed-memory and uncertainty reducing local triangle counting for graph streams. CoRR, abs\/1611.06615 , 2016 . M. Jung, S. Lee, Y. Lim, and U. Kang. FURL: fixed-memory and uncertainty reducing local triangle counting for graph streams. CoRR, abs\/1611.06615, 2016."},{"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\/2487788.2488173"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433480"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.07.017"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772756"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783285"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1076315"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594552"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939757"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505563"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2662017"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556569"},{"key":"e_1_2_1_39_1","volume-title":"Phd in Computer Science","author":"Schank T.","year":"2007","unstructured":"T. Schank . Algorithmic aspects of triangle-based network analysis . Phd in Computer Science , 2007 . T. Schank. Algorithmic aspects of triangle-based network analysis. Phd in Computer Science, 2007."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_54"},{"key":"e_1_2_1_41_1","volume-title":"Evolution of directed triangle motifs in the google+ OSN. CoRR, abs\/1502.04321","author":"Schi\u00f6berg D.","year":"2015","unstructured":"D. Schi\u00f6berg , F. Schneider , S. Schmid , S. Uhlig , and A. Feldmann . Evolution of directed triangle motifs in the google+ OSN. CoRR, abs\/1502.04321 , 2015 . D. Schi\u00f6berg, F. Schneider, S. Schmid, S. Uhlig, and A. Feldmann. Evolution of directed triangle motifs in the google+ OSN. CoRR, abs\/1502.04321, 2015."},{"issue":"1","key":"e_1_2_1_42_1","first-page":"32","article-title":"Directed closure measures for networks with reciprocity","volume":"5","author":"Seshadhri C.","year":"2017","unstructured":"C. Seshadhri , A. Pinar , N. Durak , and T. G. Kolda . Directed closure measures for networks with reciprocity . J. Complex Networks , 5 ( 1 ): 32 -- 47 , 2017 . C. Seshadhri, A. Pinar, N. Durak, and T. G. Kolda. Directed closure measures for networks with reciprocity. J. Complex Networks, 5(1):32--47, 2017.","journal-title":"J. Complex Networks"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1002\/sam.11224"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939771"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939771"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623669"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"issue":"2","key":"e_1_2_1_50_1","first-page":"1","article-title":"Visualizing the signatures of social roles in online discussion groups","volume":"8","author":"Welser H. T.","year":"2007","unstructured":"H. T. Welser , E. Gleave , D. Fisher , and M. Smith . Visualizing the signatures of social roles in online discussion groups . JoSS , 8 ( 2 ): 1 -- 32 , 2007 . H. T. Welser, E. Gleave, D. Fisher, and M. Smith. Visualizing the signatures of social roles in online discussion groups. JoSS, 8(2):1--32, 2007.","journal-title":"JoSS"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2556663"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556609"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2016.7840674"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3149193.3149197","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:34:21Z","timestamp":1672220061000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3149193.3149197"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["10.14778\/3149193.3149197"],"URL":"https:\/\/doi.org\/10.14778\/3149193.3149197","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,10]]}}}