{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T02:37:51Z","timestamp":1776134271450,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,10,1]],"date-time":"2010-10-01T00:00:00Z","timestamp":1285891200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell'Istruzione, dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["RBIN047MH9"],"award-info":[{"award-number":["RBIN047MH9"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2010,10]]},"abstract":"<jats:p>\n            In this article, we study the problem of approximate local triangle counting in large graphs. Namely, given a large graph\n            <jats:italic>G<\/jats:italic>\n            =(\n            <jats:italic>V,E<\/jats:italic>\n            ) we want to estimate as accurately as possible the number of triangles incident to every node\n            <jats:italic>v<\/jats:italic>\n            \u2208\n            <jats:italic>V<\/jats:italic>\n            in the graph. We consider the question both for undirected and directed graphs. The problem of computing the\n            <jats:italic>global<\/jats:italic>\n            number of triangles in a graph has been considered before, but to our knowledge this is the first contribution that addresses the problem of approximate\n            <jats:italic>local<\/jats:italic>\n            triangle counting with a focus on the efficiency issues arising in massive graphs and that also considers the directed case. The distribution of the local number of triangles and the related local clustering coefficient can be used in many interesting applications. For example, we show that the measures we compute can help detect the presence of spamming activity in large-scale Web graphs, as well as to provide useful features for content quality assessment in social networks.\n          <\/jats:p>\n          <jats:p>\n            For computing the local number of triangles (undirected and directed), we propose two approximation algorithms, which are based on the idea of min-wise independent permutations [Broder et al. 1998]. Our algorithms operate in a semi-streaming fashion, using\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>V<\/jats:italic>\n            |) space in main memory and performing\n            <jats:italic>O<\/jats:italic>\n            (log |\n            <jats:italic>V<\/jats:italic>\n            |) sequential scans over the edges of the graph. The first algorithm we describe in this article also uses\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>E<\/jats:italic>\n            |) space of external memory during computation, while the second algorithm uses only main memory. We present the theoretical analysis as well as experimental results on large graphs, demonstrating the practical efficiency of our approach.\n          <\/jats:p>","DOI":"10.1145\/1839490.1839494","type":"journal-article","created":{"date-parts":[[2010,10,19]],"date-time":"2010-10-19T12:36:24Z","timestamp":1287491784000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":64,"title":["Efficient algorithms for large-scale local triangle counting"],"prefix":"10.1145","volume":"4","author":[{"given":"Luca","family":"Becchetti","sequence":"first","affiliation":[{"name":"\u201cSapienza\u201d Universit\u00e0 di Roma, Rome, Italy"}]},{"given":"Paolo","family":"Boldi","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Milano, Milan, Italy"}]},{"given":"Carlos","family":"Castillo","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Spain, Barcelona Spain"}]},{"given":"Aristides","family":"Gionis","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Spain, Barcelona Spain"}]}],"member":"320","published-online":{"date-parts":[[2010,10,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA). 623--632","author":"Bar-Yossef Z.","unstructured":"Bar-Yossef , Z. , Kumar , R. , and Sivakumar , D . 2002. Reductions in streaming algorithms, with an application to counting triangles in graphs . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA). 623--632 . Bar-Yossef, Z., Kumar, R., and Sivakumar, D. 2002. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA). 623--632."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-8733(01)00035-1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401898"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Bohman T. Cooper C. and Frieze A. M. 2000. Min-wise independent linear permutations. Electronic J. Combinat. 7.  Bohman T. Cooper C. and Frieze A. M. 2000. Min-wise independent linear permutations. Electronic J. Combinat. 7.","DOI":"10.37236\/1504"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.109"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2005.132"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/829502.830043"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/647819.736184"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276781"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 6th International Conference on World Wide Web. Elsevier Science Publishers Ltd., 1157--1166","author":"Broder A. Z.","unstructured":"Broder , A. Z. , Glassman , S. C. , Manasse , M. S. , and Zweig , G . 1997. Syntactic clustering of the web . In Proceedings of the 6th International Conference on World Wide Web. Elsevier Science Publishers Ltd., 1157--1166 . Broder, A. Z., Glassman, S. C., Manasse, M. S., and Zweig, G. 1997. Syntactic clustering of the web. In Proceedings of the 6th International Conference on World Wide Web. Elsevier Science Publishers Ltd., 1157--1166."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 15th Annual European Symposium on Algorithms. 618--632","author":"Buriol L. S.","unstructured":"Buriol , L. S. , Frahling , G. , Leonardi , S. , and Sohler , C . 2007. Estimating clustering indexes in data streams . In Proceedings of the 15th Annual European Symposium on Algorithms. 618--632 . Buriol, L. S., Frahling, G., Leonardi, S., and Sohler, C. 2007. Estimating clustering indexes in data streams. In Proceedings of the 15th Annual European Symposium on Algorithms. 618--632."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189702.1189703"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277741.1277814"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 151--156","author":"Coppersmith D.","unstructured":"Coppersmith , D. and Kumar , R . 2004. An improved data stream algorithm for frequency moments . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 151--156 . Coppersmith, D. and Kumar, R. 2004. An improved data stream algorithm for frequency moments. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 151--156."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90719-V"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109635"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.032093399"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP). 207--216","author":"Feigenbaum J.","unstructured":"Feigenbaum , J. , Kannan , S. , Gregor , M. A. , Suri , S. , and Zhang , J . 2004. On graph problems in a semi-streaming model . In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP). 207--216 . Feigenbaum, J., Kannan, S., Gregor, M. A., Suri, S., and Zhang, J. 2004. On graph problems in a semi-streaming model. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP). 207--216."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017074.1017077"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060839"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases (VLDB). 721--732","author":"Gibson D.","unstructured":"Gibson , D. , Kumar , R. , and Tomkins , A . 2005. Discovering large dense subgraphs in massive graphs . In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB). 721--732 . Gibson, D., Kumar, R., and Tomkins, A. 2005. Discovering large dense subgraphs in massive graphs. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB). 721--732."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062745.1062789"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Henzinger M. R. Raghavan P. and Rajagopalan S. 1999. Computing on data streams. Dimacs Series in Discrete Mathematics and Theoretical Computer Science 107--118.   Henzinger M. R. Raghavan P. and Rajagopalan S. 1999. Computing on data streams. Dimacs Series in Discrete Mathematics and Theoretical Computer Science 107--118.","DOI":"10.1090\/dimacs\/050\/05"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2004.01.007"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 454--456","author":"Indyk P.","year":"1999","unstructured":"Indyk , P. 1999 . A small approximately min-wise independent family of hash functions . In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 454--456 . Indyk, P. 1999. A small approximately min-wise independent family of hash functions. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 454--456."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00040-7"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.07.017"},{"key":"e_1_2_1_35_1","unstructured":"Latapy M. and Magnien C. 2006. Measuring fundamental properties of real-world complex networks. arXiv:cs\/0609115v2.  Latapy M. and Magnien C. 2006. Measuring fundamental properties of real-world complex networks. arXiv:cs\/0609115v2."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Mitzenmacher M. and Upfal E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.   Mitzenmacher M. and Upfal E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_54"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.72"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"e_1_2_1_42_1","first-page":"2","article-title":"Visualizing the signatures of social roles in online discussion groups","volume":"8","author":"Welser H. T.","year":"2007","unstructured":"Welser , H. T. , Gleave , E. , Fisher , D. , and Smith , M. 2007 . Visualizing the signatures of social roles in online discussion groups . J. Soc. Struct. 8 , 2 . Welser, H. T., Gleave, E., Fisher, D., and Smith, M. 2007. Visualizing the signatures of social roles in online discussion groups. J. Soc. Struct. 8, 2.","journal-title":"J. Soc. Struct."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1839490.1839494","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1839490.1839494","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:22:35Z","timestamp":1750245755000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1839490.1839494"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["10.1145\/1839490.1839494"],"URL":"https:\/\/doi.org\/10.1145\/1839490.1839494","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10]]},"assertion":[{"value":"2009-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-10-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}