{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T16:21:31Z","timestamp":1780590091097,"version":"3.54.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,1,29]],"date-time":"2016-01-29T00:00:00Z","timestamp":1454025600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002809","name":"Generalitat de Catalunya","doi-asserted-by":"publisher","award":["GRC-2014-890"],"award-info":[{"award-number":["GRC-2014-890"]}],"id":[{"id":"10.13039\/501100002809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["TIN2013-47008-R"],"award-info":[{"award-number":["TIN2013-47008-R"]}],"id":[{"id":"10.13039\/501100004837","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":[[2016,2,24]]},"abstract":"<jats:p>\n            Community detection has arisen as one of the most relevant topics in the field of graph data mining due to its applications in many fields such as biology, social networks, or network traffic analysis. Although the existing metrics used to quantify the quality of a community work well in general, under some circumstances, they fail at correctly capturing such notion. The main reason is that these metrics consider the internal community edges as a set, but ignore how these actually connect the vertices of the community. We propose the Weighted Community Clustering (\n            <jats:italic>WCC<\/jats:italic>\n            ), which is a new community metric that takes the triangle instead of the edge as the minimal structural motif indicating the presence of a strong relation in a graph. We theoretically analyse\n            <jats:italic>WCC<\/jats:italic>\n            in depth and formally prove, by means of a set of properties, that the maximization of\n            <jats:italic>WCC<\/jats:italic>\n            guarantees communities with cohesion and structure. In addition, we propose\n            <jats:italic>Scalable Community Detection (SCD)<\/jats:italic>\n            , a community detection algorithm based on\n            <jats:italic>WCC<\/jats:italic>\n            , which is designed to be fast and scalable on SMP machines, showing experimentally that\n            <jats:italic>WCC<\/jats:italic>\n            correctly captures the concept of community in social networks using real datasets. Finally, using ground-truth data, we show that\n            <jats:italic>SCD<\/jats:italic>\n            provides better quality than the best disjoint community detection algorithms of the state of the art while performing faster.\n          <\/jats:p>","DOI":"10.1145\/2775108","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T20:37:54Z","timestamp":1454359074000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Put Three and Three Together"],"prefix":"10.1145","volume":"10","author":[{"given":"Arnau","family":"Prat-P\u00e9rez","sequence":"first","affiliation":[{"name":"DAMA-UPC, Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Dominguez-Sal","sequence":"additional","affiliation":[{"name":"Sparsity Technologies, Barcelona, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Josep-M.","family":"Brunat","sequence":"additional","affiliation":[{"name":"Departament Matem\u00e0tica Aplicada II, Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Josep-Lluis","family":"Larriba-Pey","sequence":"additional","affiliation":[{"name":"DAMA-UPC, Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,1,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature09182"},{"key":"e_1_2_1_2_1","first-page":"066118","article-title":"Communities and bottlenecks: Trees and treelike networks have high modularity. Phy","volume":"85","author":"Bagrow J. P","year":"2012","unstructured":"J. P Bagrow . 2012 . Communities and bottlenecks: Trees and treelike networks have high modularity. Phy . Rev. E 85 , 6 (2012), 066118 . J. P Bagrow. 2012. Communities and bottlenecks: Trees and treelike networks have high modularity. Phy. Rev. E 85, 6 (2012), 066118.","journal-title":"Rev. E"},{"key":"e_1_2_1_3_1","volume-title":"JSTAT 2008","author":"Blondel V. D.","year":"2008","unstructured":"V. D. Blondel , J. L. Guillaume , R. Lambiotte , and E. Lefebvre . 2008. Fast unfolding of communities in large networks . JSTAT 2008 , 10 ( 2008 ), 10008. V. D. Blondel, J. L. Guillaume, R. Lambiotte, and E. Lefebvre. 2008. Fast unfolding of communities in large networks. JSTAT 2008, 10 (2008), 10008."},{"key":"e_1_2_1_4_1","first-page":"066111","article-title":"Finding community structure in very large networks. Phy","volume":"70","author":"Clauset A.","year":"2004","unstructured":"A. Clauset , M. E. J. Newman , and C. Moore . 2004 . Finding community structure in very large networks. Phy . Rev. E 70 , 6 (2004), 066111 . A. Clauset, M. E. J. Newman, and C. Moore. 2004. Finding community structure in very large networks. Phy. Rev. E 70, 6 (2004), 066111.","journal-title":"Rev. E"},{"key":"e_1_2_1_5_1","volume-title":"Retrieved","year":"2012","unstructured":"Dblp. 2012. Retrieved September 2012 from http:\/\/dblp.uni-trier.de\/xml\/. Dblp. 2012. Retrieved September 2012 from http:\/\/dblp.uni-trier.de\/xml\/."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.107.065701"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.40"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/347090.347121"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0605965104"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_12_1","first-page":"046106","article-title":"Performance of modularity maximization in practical contexts. Phy","volume":"81","author":"Good B. H.","year":"2010","unstructured":"B. H. Good , Y. A. de Montjoye , and A. Clauset . 2010 . Performance of modularity maximization in practical contexts. Phy . Rev. E 81 , 4 (2010), 046106 . B. H. Good, Y. A. de Montjoye, and A. Clauset. 2010. Performance of modularity maximization in practical contexts. Phy. Rev. E 81, 4 (2010), 046106.","journal-title":"Rev. E"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2578726.2578737"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"e_1_2_1_15_1","first-page":"056117","article-title":"Community detection algorithms: a comparative analysis. Phy","volume":"80","author":"Lancichinetti A.","year":"2009","unstructured":"A. Lancichinetti . 2009 . Community detection algorithms: a comparative analysis. Phy . Rev. E 80 , 5 (2009), 056117 . A. Lancichinetti. 2009. Community detection algorithms: a comparative analysis. Phy. Rev. E 80, 5 (2009), 056117.","journal-title":"Rev. E"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0018961"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401948"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772755"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.v58:7"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.soc.27.1.415"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2005.04.022"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.98.2.404"},{"key":"e_1_2_1_23_1","first-page":"026113","article-title":"Finding and evaluating community structure in networks. Phy","volume":"69","author":"Newman M. E. J.","year":"2004","unstructured":"M. E. J. Newman and M. Girvan . 2004 . Finding and evaluating community structure in networks. Phy . Rev. E 69 , 2 (2004), 026113 . M. E. J. Newman and M. Girvan. 2004. Finding and evaluating community structure in networks. Phy. Rev. E 69, 2 (2004), 026113.","journal-title":"Rev. E"},{"key":"e_1_2_1_24_1","first-page":"036122","article-title":"Why social networks are different from other types of networks. Phy","volume":"68","author":"Newman M. E. J.","year":"2003","unstructured":"M. E. J. Newman and J. Park . 2003 . Why social networks are different from other types of networks. Phy . Rev. E 68 , 3 (2003), 036122 . M. E. J. Newman and J. Park. 2003. Why social networks are different from other types of networks. Phy. Rev. E 68, 3 (2003), 036122.","journal-title":"Rev. E"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"A. Padrol-Sureda G. Perarnau-Llobet J. Pfeifle and V. Munt\u00e9s-Mulero. 2010. Overlapping community search for social networks. In ICDE. IEEE 992--995.  A. Padrol-Sureda G. Perarnau-Llobet J. Pfeifle and V. Munt\u00e9s-Mulero. 2010. Overlapping community search for social networks. In ICDE. IEEE 992--995.","DOI":"10.1109\/ICDE.2010.5447860"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"A. Prat-P\u00e9rez D. Dominguez-Sal and J. L. Larriba-Pey. 2011. Social based layouts for the increase of locality in graph operations. In DASFAA. Springer Berlin Heidelberg 558--569.   A. Prat-P\u00e9rez D. Dominguez-Sal and J. L. Larriba-Pey. 2011. Social based layouts for the increase of locality in graph operations. In DASFAA. Springer Berlin Heidelberg 558--569.","DOI":"10.1007\/978-3-642-20149-3_40"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568010"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1209\/0295-5075\/106\/38001"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0400054101"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036106"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0706851105"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989399"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2006.11.072"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559988"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.138"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433471"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2014.2364018"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2775108","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2775108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:39Z","timestamp":1750231179000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2775108"}},"subtitle":["Triangle-Driven Community Detection"],"short-title":[],"issued":{"date-parts":[[2016,1,29]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,2,24]]}},"alternative-id":["10.1145\/2775108"],"URL":"https:\/\/doi.org\/10.1145\/2775108","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,29]]},"assertion":[{"value":"2014-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}