{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T13:07:04Z","timestamp":1765544824073,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,8,14]],"date-time":"2021-08-14T00:00:00Z","timestamp":1628899200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Intesa Sanpaolo Innovation Center"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,8,14]]},"DOI":"10.1145\/3447548.3467260","type":"proceedings-article","created":{"date-parts":[[2021,8,13]],"date-time":"2021-08-13T18:33:08Z","timestamp":1628879588000},"page":"1501-1509","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Triangle-aware Spectral Sparsifiers and Community Detection"],"prefix":"10.1145","author":[{"given":"Konstantinos","family":"Sotiropoulos","sequence":"first","affiliation":[{"name":"Boston University, Boston, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charalampos E.","family":"Tsourakakis","sequence":"additional","affiliation":[{"name":"Boston University and ISI Foundation, Boston, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,8,14]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"July 2020. Stanford Network Analysis Project. http:\/\/snap.stanford.edu\/data\/ index.html.  July 2020. Stanford Network Analysis Project. http:\/\/snap.stanford.edu\/data\/ index.html."},{"key":"e_1_3_2_1_2_1","volume-title":"A separability framework for analyzing community structure. ACM Transactions on Knowledge Discovery from Data (TKDD)","author":"Abrahao Bruno","year":"2014","unstructured":"Bruno Abrahao , Sucheta Soundarajan , John Hopcroft , and Robert Kleinberg . 2014. A separability framework for analyzing community structure. ACM Transactions on Knowledge Discovery from Data (TKDD) , Vol. 8 , 1 ( 2014 ), 1--29. Bruno Abrahao, Sucheta Soundarajan, John Hopcroft, and Robert Kleinberg. 2014. A separability framework for analyzing community structure. ACM Transactions on Knowledge Discovery from Data (TKDD), Vol. 8, 1 (2014), 1--29."},{"key":"e_1_3_2_1_3_1","volume-title":"Lap Chi Lau, and Shayan Oveis Gharan","author":"Alev Vedat Levi","year":"2017","unstructured":"Vedat Levi Alev , Nima Anari , Lap Chi Lau, and Shayan Oveis Gharan . 2017 . Graph Clustering using Effective Resistance . arXiv preprint arXiv:1711.06530 (2017). Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. 2017. Graph Clustering using Effective Resistance. arXiv preprint arXiv:1711.06530 (2017)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492007.2492029"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1093"},{"key":"e_1_3_2_1_8_1","volume-title":"Science","volume":"353","author":"Benson Austin R","year":"2016","unstructured":"Austin R Benson , David F Gleich , and Jure Leskovec . 2016 . Higher-order organization of complex networks . Science , Vol. 353 , 6295 (2016), 163--166. Austin R Benson, David F Gleich, and Jure Leskovec. 2016. Higher-order organization of complex networks. Science, Vol. 353, 6295 (2016), 163--166."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"volume-title":"Convex optimization","author":"Boyd Stephen","key":"e_1_3_2_1_10_1","unstructured":"Stephen Boyd and Lieven Vandenberghe . 2004. Convex optimization . Cambridge university press . Stephen Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"U. Brandes D. Delling M. Gaertler R. G\u00f6rke M. Hoefer Z. Nikoloski and D. Wagner. 2007. On finding graph clusterings with maximum modularity. In Graph-Theoretic Concepts in Computer Science. Springer 121--132.  U. Brandes D. Delling M. Gaertler R. G\u00f6rke M. Hoefer Z. Nikoloski and D. Wagner. 2007. On finding graph clusterings with maximum modularity. In Graph-Theoretic Concepts in Computer Science. Springer 121--132.","DOI":"10.1007\/978-3-540-74839-7_12"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63516"},{"key":"e_1_3_2_1_13_1","series-title":"SIAM Journal on computing","volume-title":"Arboricity and subgraph listing algorithms","author":"Chiba Norishige","year":"1985","unstructured":"Norishige Chiba and Takao Nishizeki . 1985. Arboricity and subgraph listing algorithms . SIAM Journal on computing , Vol. 14 , 1 ( 1985 ), 210--223. Norishige Chiba and Takao Nishizeki. 1985. Arboricity and subgraph listing algorithms. SIAM Journal on computing, Vol. 14, 1 (1985), 210--223."},{"key":"e_1_3_2_1_14_1","volume-title":"Community detection in graphs. Physics reports","author":"Fortunato Santo","year":"2010","unstructured":"Santo Fortunato . 2010. Community detection in graphs. Physics reports , Vol. 486 , 3 ( 2010 ), 75--174. Santo Fortunato. 2010. Community detection in graphs. Physics reports, Vol. 486, 3 (2010), 75--174."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1210459"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP40776.2020.9053451"},{"key":"e_1_3_2_1_17_1","volume-title":"Tsourakakis","author":"Gionis Aristides","year":"2015","unstructured":"Aristides Gionis and Charalampos E . Tsourakakis . 2015 . Dense Subgraph Discovery. In KDD. Aristides Gionis and Charalampos E. Tsourakakis. 2015. Dense Subgraph Discovery. In KDD."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339628"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554840"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00132"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487678"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"e_1_3_2_1_24_1","first-page":"424","article-title":"Using Randomized Sparsification to Approximate Minimum Cuts","volume":"94","author":"Karger David R","year":"1994","unstructured":"David R Karger . 1994 . Using Randomized Sparsification to Approximate Minimum Cuts .. In SODA , Vol. 94. 424 -- 432 . David R Karger. 1994. Using Randomized Sparsification to Approximate Minimum Cuts.. In SODA, Vol. 94. 424--432.","journal-title":"SODA"},{"key":"e_1_3_2_1_25_1","unstructured":"G. Karypis and V. Kumar. 1995. Metis-unstructured graph partitioning and sparse matrix ordering system version 2.0. (1995).  G. Karypis and V. Kumar. 1995. Metis-unstructured graph partitioning and sparse matrix ordering system version 2.0. (1995)."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2665063"},{"volume-title":"Proceeding of the 17th international conference on World Wide Web. ACM, 695--704","author":"Leskovec J.","key":"e_1_3_2_1_27_1","unstructured":"J. Leskovec , K.J. Lang , A. Dasgupta , and M. W. Mahoney . 2008. Statistical properties of community structure in large social and information networks . In Proceeding of the 17th international conference on World Wide Web. ACM, 695--704 . J. Leskovec, K.J. Lang, A. Dasgupta, and M. W. Mahoney. 2008. Statistical properties of community structure in large social and information networks. In Proceeding of the 17th international conference on World Wide Web. ACM, 695--704."},{"volume-title":"Markov chains and mixing times","author":"Levin David A","key":"e_1_3_2_1_28_1","unstructured":"David A Levin and Yuval Peres . 2017. Markov chains and mixing times . Vol. 107 . American Mathematical Soc . David A Levin and Yuval Peres. 2017. Markov chains and mixing times. Vol. 107. American Mathematical Soc."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8056956"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330882"},{"key":"e_1_3_2_1_31_1","unstructured":"Ulrike V Luxburg Agnes Radl and Matthias Hein. 2010. Getting lost in space: Large sample analysis of the resistance distance. In Advances in Neural Information Processing Systems. 2622--2630.  Ulrike V Luxburg Agnes Radl and Matthias Hein. 2010. Getting lost in space: Large sample analysis of the resistance distance. In Advances in Neural Information Processing Systems. 2622--2630."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.63"},{"key":"e_1_3_2_1_33_1","volume-title":"Interlacing families II: Mixed characteristic polynomials and the Kadison?Singer problem. Annals of Mathematics","author":"Marcus Adam W","year":"2015","unstructured":"Adam W Marcus , Daniel A Spielman , and Nikhil Srivastava . 2015. Interlacing families II: Mixed characteristic polynomials and the Kadison?Singer problem. Annals of Mathematics ( 2015 ), 327--350. Adam W Marcus, Daniel A Spielman, and Nikhil Srivastava. 2015. Interlacing families II: Mixed characteristic polynomials and the Kadison?Singer problem. Annals of Mathematics (2015), 327--350."},{"key":"e_1_3_2_1_34_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_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSW.2018.8439897"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.12.007"},{"key":"e_1_3_2_1_38_1","volume-title":"The ground truth about metadata and community detection in networks. Science advances","author":"Peel Leto","year":"2017","unstructured":"Leto Peel , Daniel B Larremore , and Aaron Clauset . 2017. The ground truth about metadata and community detection in networks. Science advances , Vol. 3 , 5 ( 2017 ), e1602548. Leto Peel, Daniel B Larremore, and Aaron Clauset. 2017. The ground truth about metadata and community detection in networks. Science advances, Vol. 3, 5 (2017), e1602548."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159706"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989399"},{"volume-title":"SIGMOD '11","author":"Satuluri V.","key":"e_1_3_2_1_41_1","unstructured":"V. Satuluri , S. Parthasarathy , and Y. Ruan . 2011b. Local graph sparsification for scalable clustering . In SIGMOD '11 ( Athens, Greece). 721--732. V. Satuluri, S. Parthasarathy, and Y. Ruan. 2011b. Local graph sparsification for scalable clustering. In SIGMOD '11 (Athens, Greece). 721--732."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2007.05.001"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1911030117"},{"key":"e_1_3_2_1_44_1","unstructured":"Daniel Spielman. [n.d.]. Lecture 17 Sparsification by Effective Resistance Sampling. Available at https:\/\/www.cs.yale.edu\/homes\/spielman\/561\/lect17--15.pdf.  Daniel Spielman. [n.d.]. Lecture 17 Sparsification by Effective Resistance Sampling. Available at https:\/\/www.cs.yale.edu\/homes\/spielman\/561\/lect17--15.pdf."},{"key":"e_1_3_2_1_45_1","unstructured":"Daniel Spielman. 2021. Laplacians.jl. https:\/\/github.com\/danspielman\/Laplacians.jl.  Daniel Spielman. 2021. Laplacians.jl. https:\/\/github.com\/danspielman\/Laplacians.jl."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883040"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-010-0001-9"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052653"},{"key":"e_1_3_2_1_52_1","volume-title":"A note on sums of independent random matrices after Ahlswede-Winter. Lecture notes","author":"Vershynin Roman","year":"2009","unstructured":"Roman Vershynin . 2009. A note on sums of independent random matrices after Ahlswede-Winter. Lecture notes ( 2009 ). Roman Vershynin. 2009. A note on sums of independent random matrices after Ahlswede-Winter. Lecture notes (2009)."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098069"}],"event":{"name":"KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"],"location":"Virtual Event Singapore","acronym":"KDD '21"},"container-title":["Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447548.3467260","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447548.3467260","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:28Z","timestamp":1750191508000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447548.3467260"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,14]]},"references-count":54,"alternative-id":["10.1145\/3447548.3467260","10.1145\/3447548"],"URL":"https:\/\/doi.org\/10.1145\/3447548.3467260","relation":{},"subject":[],"published":{"date-parts":[[2021,8,14]]},"assertion":[{"value":"2021-08-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}