{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T00:16:28Z","timestamp":1782519388012,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T00:00:00Z","timestamp":1597881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1740850, CCF-1813165, CCF-1909790"],"award-info":[{"award-number":["CCF-1740850, CCF-1813165, CCF-1909790"]}]},{"name":"ARO Award","award":["W911NF1910294"],"award-info":[{"award-number":["W911NF1910294"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,8,23]]},"DOI":"10.1145\/3394486.3403073","type":"proceedings-article","created":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T23:18:56Z","timestamp":1597965536000},"page":"306-316","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["How to Count Triangles, without Seeing the Whole Graph"],"prefix":"10.1145","author":[{"given":"Suman K.","family":"Bera","sequence":"first","affiliation":[{"name":"University of California, Santa Cruz, Santa Cruz, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz, Santa Cruz, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,8,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"crossref","unstructured":"Nesreen K Ahmed Nick Duffield Jennifer Neville and Ramana Kompella. 2014a. Graph sample and hold: A framework for big-graph analytics. In SIGKDD. ACM ACM 1446--1455.  Nesreen K Ahmed Nick Duffield Jennifer Neville and Ramana Kompella. 2014a. Graph sample and hold: A framework for big-graph analytics. In SIGKDD. ACM ACM 1446--1455.","DOI":"10.1145\/2623330.2623757"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601438"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505545"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2015.75"},{"key":"e_1_3_2_2_5_1","volume-title":"Proc. 13th Symposium on Discrete Algorithms (SODA). 623--632","author":"Bar-Yossef Ziv","unstructured":"Ziv Bar-Yossef , Ravi Kumar , and D. Sivakumar . 2002. Reductions in Streaming Algorithms, with an Application to Counting Triangles in Graphs . In Proc. 13th Symposium on Discrete Algorithms (SODA). 623--632 . Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. 2002. Reductions in Streaming Algorithms, with an Application to Counting Triangles in Graphs. In Proc. 13th Symposium on Discrete Algorithms (SODA). 623--632."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Luca Becchetti Paolo Boldi Carlos Castillo and Aristides Gionis. 2008. Efficient semi-streaming algorithms for local triangle counting in massive graphs. In Knowledge Data and Discovery (KDD). ACM 16--24.  Luca Becchetti Paolo Boldi Carlos Castillo and Aristides Gionis. 2008. Efficient semi-streaming algorithms for local triangle counting in massive graphs. In Knowledge Data and Discovery (KDD). ACM 16--24.","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_3_2_2_7_1","volume-title":"Proc. 34th International 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 Proc. 34th International Symposium on Theoretical Aspects of Computer Science. Suman K Bera and Amit Chakrabarti. 2017. Towards tighter space bounds for counting triangles and other substructures in graph streams. In Proc. 34th International Symposium on Theoretical Aspects of Computer Science."},{"key":"e_1_3_2_2_8_1","volume-title":"Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 457 -- 467","author":"Bera Suman K.","unstructured":"Suman K. Bera and C. Seshadhri . 2020. How the Degeneracy Helps for Triangle Counting in Graph Streams . In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 457 -- 467 . Suman K. Bera and C. Seshadhri. 2020. How the Degeneracy Helps for Triangle Counting in Graph Streams. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 457 -- 467."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021940"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_3_2_2_12_1","volume-title":"Conference on the World Wide Web (WWW).","author":"Chierichetti F.","unstructured":"F. Chierichetti , A. Dasgupta , R. Kumar , S. Lattanzi , and T. Sarlos . 2016. On Sampling Nodes in a Network . In Conference on the World Wide Web (WWW). F. Chierichetti, A. Dasgupta, R. Kumar, S. Lattanzi, and T. Sarlos. 2016. On Sampling Nodes in a Network. In Conference on the World Wide Web (WWW)."},{"key":"e_1_3_2_2_13_1","volume-title":"Proc. 45th International Colloquium on Automata, Languages and Programming.","author":"Chierichetti Flavio","year":"2018","unstructured":"Flavio Chierichetti and Shahrzad Haddadan . 2018 . On the Complexity of Sampling Vertices Uniformly from a Graph . In Proc. 45th International Colloquium on Automata, Languages and Programming. Flavio Chierichetti and Shahrzad Haddadan. 2018. On the Complexity of Sampling Vertices Uniformly from a Graph. In Proc. 45th International Colloquium on Automata, Languages and Programming."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2009.120"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-014-0168-6"},{"key":"e_1_3_2_2_16_1","volume-title":"Conference on the World Wide Web (WWW). 795--806","author":"Dasgupta A.","unstructured":"A. Dasgupta , R. Kumar , and T. Sarlos . 2014. On estimating the average degree . In Conference on the World Wide Web (WWW). 795--806 . A. Dasgupta, R. Kumar, and T. Sarlos. 2014. On estimating the average degree. In Conference on the World Wide Web (WWW). 795--806."},{"key":"e_1_3_2_2_17_1","volume-title":"Approximately Counting Triangles in Sublinear Time. In Annual IEEE Symposium on Foundations of Computer Science, GRS11 (Ed.). 614--633","author":"Eden T.","unstructured":"T. Eden , A. Levi , D. Ron , and C. Seshadhri . 2015 . Approximately Counting Triangles in Sublinear Time. In Annual IEEE Symposium on Foundations of Computer Science, GRS11 (Ed.). 614--633 . T. Eden, A. Levi, D. Ron, and C. Seshadhri. 2015. Approximately Counting Triangles in Sublinear Time. In Annual IEEE Symposium on Foundations of Computer Science, GRS11 (Ed.). 614--633."},{"key":"e_1_3_2_2_18_1","unstructured":"T. Eden D. Ron and C. Seshadhri. 2017. Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection. In International Colloquium on Automata Languages and Programming GRS11 (Ed.). 614--633.  T. Eden D. Ron and C. Seshadhri. 2017. Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection. In International Colloquium on Automata Languages and Programming GRS11 (Ed.). 614--633."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.89"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983849"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2688283.2688284"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2009-00292-2"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2691190.2691193"},{"key":"e_1_3_2_2_24_1","volume-title":"Fast Generation of Large Scale Social Networks While Incorporating Transitive Closures. In International Conference on Privacy, Security, Risk and Trust (PASSAT). 154--165","author":"Joseph J.","year":"2012","unstructured":"Joseph J. Pfeiffer III, Timothy La Fond , Sebasti\u00e1 n Moreno , and Jennifer Neville . 2012 . Fast Generation of Large Scale Social Networks While Incorporating Transitive Closures. In International Conference on Privacy, Security, Risk and Trust (PASSAT). 154--165 . Joseph J. Pfeiffer III, Timothy La Fond, Sebasti\u00e1 n Moreno, and Jennifer Neville. 2012. Fast Generation of Large Scale Social Networks While Incorporating Transitive Closures. In International Conference on Privacy, Security, Risk and Trust (PASSAT). 154--165."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.2015.7421397"},{"key":"e_1_3_2_2_27_1","unstructured":"Madhav Jha C Seshadhri and Ali Pinar. 2013. A space efficient streaming algorithm for triangle counting using the birthday paradox. In SIGKDD. ACM 589--597.  Madhav Jha C Seshadhri and Ali Pinar. 2013. A space efficient streaming algorithm for triangle counting using the birthday paradox. In SIGKDD. ACM 589--597."},{"key":"e_1_3_2_2_28_1","volume-title":"Computing and Combinatorics","author":"Jowhari Hossein","unstructured":"Hossein Jowhari and Mohammad Ghodsi . 2005. New streaming algorithms for counting triangles in graphs . In Computing and Combinatorics . Springer , 710--716. Hossein Jowhari and Mohammad Ghodsi. 2005. New streaming algorithms for counting triangles in graphs. In Computing and Combinatorics. Springer, 710--716."},{"key":"e_1_3_2_2_29_1","first-page":"19","article-title":"Estimating clustering coefficients and size of social networks via random walk","volume":"9","author":"Katzir Liran","year":"2015","unstructured":"Liran Katzir and Stephen J Hardiman . 2015 . Estimating clustering coefficients and size of social networks via random walk . ACM Transactions on the Web (TWEB) , Vol. 9 , 4 (2015), 19 . Liran Katzir and Stephen J Hardiman. 2015. Estimating clustering coefficients and size of social networks via random walk. ACM Transactions on the Web (TWEB), Vol. 9, 4 (2015), 19.","journal-title":"ACM Transactions on the Web (TWEB)"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963489"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989418"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915209"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/13090729X"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2012.625260"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"crossref","unstructured":"Jure Leskovec and Christos Faloutsos. 2006. Sampling from large graphs. In Knowledge Data and Discovery (KDD). ACM 631--636.  Jure Leskovec and Christos Faloutsos. 2006. Sampling from large graphs. In Knowledge Data and Discovery (KDD). ACM 631--636.","DOI":"10.1145\/1150402.1150479"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020431"},{"key":"e_1_3_2_2_37_1","volume-title":"Better Algorithms for Counting Triangles in Data Streams. In ACM Symposium on Principles of Database Systems. 401--411","author":"McGregor Andrew","unstructured":"Andrew McGregor , Sofya Vorotnikova , and Hoa T. Vu . 2016 . Better Algorithms for Counting Triangles in Data Streams. In ACM Symposium on Principles of Database Systems. 401--411 . Andrew McGregor, Sofya Vorotnikova, and Hoa T. Vu. 2016. Better Algorithms for Counting Triangles in Data Streams. In ACM Symposium on Principles of Database Systems. 401--411."},{"key":"e_1_3_2_2_38_1","volume-title":"Science","volume":"298","author":"Milo Ron","year":"2002","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 , Vol. 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, Vol. 298, 5594 (2002), 824--827."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556569"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2662075"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2930657"},{"key":"e_1_3_2_2_43_1","unstructured":"Ryan Rossi and Nesreen Ahmed. 2013. Network Repository. http:\/\/networkrepository.com  Ryan Rossi and Nesreen Ahmed. 2013. Network Repository. http:\/\/networkrepository.com"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_54"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.85.056109"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1002\/sam.11224"},{"key":"e_1_3_2_2_47_1","volume-title":"Scalable Subgraph Counting: The Methods Behind The Madness: WWW 2019 Tutorial. In Conference on the World Wide Web (WWW).","author":"Seshadhri C.","year":"2019","unstructured":"C. Seshadhri and Srikanta Tirthapura . 2019 . Scalable Subgraph Counting: The Methods Behind The Madness: WWW 2019 Tutorial. In Conference on the World Wide Web (WWW). C. Seshadhri and Srikanta Tirthapura. 2019. Scalable Subgraph Counting: The Methods Behind The Madness: WWW 2019 Tutorial. In Conference on the World Wide Web (WWW)."},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3059194"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"crossref","unstructured":"Kanat Tangwongsan Aduri Pavan and Srikanta Tirthapura. 2013. Parallel triangle counting in massive streaming graphs. In Knowledge Data and Discovery (KDD). ACM 781--786.  Kanat Tangwongsan Aduri Pavan and Srikanta Tirthapura. 2013. Parallel triangle counting in massive streaming graphs. In Knowledge Data and Discovery (KDD). ACM 781--786.","DOI":"10.1145\/2505515.2505741"},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"crossref","unstructured":"Charalampos E Tsourakakis U Kang Gary L Miller and Christos Faloutsos. 2009. Doulion: counting triangles in massive graphs with a coin. In Knowledge Data and Discovery (KDD). ACM 837--846.  Charalampos E Tsourakakis U Kang Gary L Miller and Christos Faloutsos. 2009. Doulion: counting triangles in massive graphs with a coin. In Knowledge Data and Discovery (KDD). ACM 837--846.","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_3_2_2_52_1","volume-title":"Revisiting Wedge Sampling for Triangle Counting. In Conference on the World Wide Web (WWW). 1875--1885","author":"Turk Ata","year":"2019","unstructured":"Ata Turk and Duru Turkoglu . 2019 . Revisiting Wedge Sampling for Triangle Counting. In Conference on the World Wide Web (WWW). 1875--1885 . Ata Turk and Duru Turkoglu. 2019. Revisiting Wedge Sampling for Triangle Counting. In Conference on the World Wide Web (WWW). 1875--1885."},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2017.55"},{"key":"e_1_3_2_2_54_1","volume-title":"Social network analysis: Methods and applications","author":"Wasserman Stanley","unstructured":"Stanley Wasserman and Katherine Faust . 1994. Social network analysis: Methods and applications . Vol. 8 . Cambridge university press . Stanley Wasserman and Katherine Faust. 1994. Social network analysis: Methods and applications. Vol. 8. Cambridge university press."},{"key":"e_1_3_2_2_55_1","volume-title":"Collective dynamics of 'small-world' networks. nature","author":"Watts Duncan J","year":"1998","unstructured":"Duncan J Watts and Steven H Strogatz . 1998. Collective dynamics of 'small-world' networks. nature , Vol. 393 , 6684 ( 1998 ), 440. Duncan J Watts and Steven H Strogatz. 1998. Collective dynamics of 'small-world' networks. nature, Vol. 393, 6684 (1998), 440."},{"key":"e_1_3_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2556663"}],"event":{"name":"KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","location":"Virtual Event CA USA","acronym":"KDD '20","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"]},"container-title":["Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3394486.3403073","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3394486.3403073","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3394486.3403073","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:38Z","timestamp":1750200098000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3394486.3403073"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,20]]},"references-count":56,"alternative-id":["10.1145\/3394486.3403073","10.1145\/3394486"],"URL":"https:\/\/doi.org\/10.1145\/3394486.3403073","relation":{},"subject":[],"published":{"date-parts":[[2020,8,20]]},"assertion":[{"value":"2020-08-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}