{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:32:30Z","timestamp":1787340750544,"version":"build-2736575974"},"reference-count":44,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>High triangle density---the graph property stating that a constant fraction of two-hop paths belongs to a triangle---is a common signature of social networks. This paper studies triangle-dense graphs from a structural perspective. We prove constructively that significant portions of a triangle-dense graph are contained in a disjoint union of dense, radius $2$ subgraphs. This result quantifies the extent to which triangle-dense graphs resemble unions of cliques. We also show that our algorithm recovers planted clusterings in approximation-stable $k$-median instances.<\/jats:p>","DOI":"10.1137\/140955331","type":"journal-article","created":{"date-parts":[[2016,3,1]],"date-time":"2016-03-01T10:14:39Z","timestamp":1456827279000},"page":"197-215","source":"Crossref","is-referenced-by-count":7,"title":["Decompositions of Triangle-Dense Graphs"],"prefix":"10.1137","volume":"45","author":[{"given":"Rishi","family":"Gupta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tim","family":"Roughgarden","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,3,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1038\/35019019"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450144"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00083-9"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1086\/421787"},{"key":"atypb6","first-page":"38","author":"Chakrabarti D.","year":"2006","journal-title":"ACM Comput. Surv."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.252631999"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/PL00012580"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1086\/228943"},{"key":"atypb10","first-page":"442","author":"Chakrabarti D.","year":"2004","journal-title":"Philadelphia"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"K. Faust,\n                      Comparing social networks: Size, density, and local structure\n                      , Metodoloski zvezki, 3 (2006), pp. 185-216.","DOI":"10.51936\/sdbv3216"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/316194.316229"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"atypb14","first-page":"417","author":"Ferrante A.","year":"2006","journal-title":"Proceedings of Conference on Computing and Combinatorics"},{"key":"atypb15","first-page":"4027","author":"Foucault Welles B.","year":"2010","journal-title":"ACM"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"atypb17","first-page":"471","author":"Gupta R.","year":"2014","journal-title":"ACM"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1086\/224954"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"J. J. Pfeiffer III, T. La Fond, S. Moreno, and J. Neville,\n                      Fast generation of large scale social networks while incorporating transitive closures\n                      , in Proceedings of the International Conference on Privacy, Security, Risk, and Trust (PASSAT), 2012, pp. 154-165.","DOI":"10.1109\/SocialCom-PASSAT.2012.130"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1038\/35022643"},{"key":"atypb21","first-page":"163","author":"Kleinberg J. M.","year":"2000","journal-title":"Proceedings of the Symposium on Theory of Computing"},{"key":"atypb22","first-page":"431","author":"Kleinberg J. M.","year":"2002","journal-title":"MA"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892065"},{"key":"atypb24","first-page":"993","author":"Lin H.","year":"2008","journal-title":"Proceedings of the Symposium on Discrete Algorithms"},{"key":"atypb25","first-page":"985","volume":"11","author":"Leskovec J.","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"atypb26","first-page":"1","author":"Leskovec J.","year":"2007","journal-title":"ACM Trans. Knowledge Discovery Data"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1004098107"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.98.2.404"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.68.026121"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.036104"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"A. Pinar, C. Seshadhri, and T. G. Kolda,\n                      The similarity between Stochastic Kronecker and Chung-Lu graph models\n                      , in Proceedings of the 2012 SIAM International Conference on Data Mining, SIAM, Philadelphia, 2012.","DOI":"10.1137\/1.9781611972825.92"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"atypb35","first-page":"861","author":"Sala A.","year":"2010","journal-title":"ACM"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.85.056109"},{"key":"atypb37","unstructured":"C. Seshadhri, A. Pinar, and T. G. Kolda,\n                      Fast triangle counting through wedge sampling\n                      , in Proceedings of the 2013 SIAM International Conference on Data Mining, SIAM, Philadelphia, 2013."},{"key":"atypb38","first-page":"721","author":"Satuluri V.","year":"2011","journal-title":"Proceedings of ACM SIGMOD"},{"key":"atypb39","unstructured":"E. Szemer\u00e9di,\n                      Regular partitions of graphs\n                      , Probl\u00e8mes Combinatoires th\u00e9orie Graphes, 260 (1978), pp. 399-401."},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488502"},{"key":"atypb41","unstructured":"J. Ugander, B. Karrer, L. Backstrom, and C. Marlow,\n                      The Anatomy of the Facebook Social Graph\n                      , arXiv:1111.4503, 2011."},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1002\/wics.184"},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"S. Wasserman and K. Faust,\n                      Social Network Analysis: Methods and Applications\n                      , Cambridge University Press, Cambridge, UK, 1994.","DOI":"10.1017\/CBO9780511815478"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1038\/30918"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140955331","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:46:20Z","timestamp":1787337980000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140955331"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/140955331"],"URL":"https:\/\/doi.org\/10.1137\/140955331","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}