{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T05:14:35Z","timestamp":1755839675637,"version":"3.41.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,4,12]],"date-time":"2024-04-12T00:00:00Z","timestamp":1712880000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Netherlands Organisation for Scientific Research","doi-asserted-by":"crossref","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Alessio Conte and Roberto Grossi","award":["PRIN 2022TS4Y3N"],"award-info":[{"award-number":["PRIN 2022TS4Y3N"]}]},{"name":"NextGeneration EU","award":["PNRR ECS00000017"],"award-info":[{"award-number":["PNRR ECS00000017"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2024,7,31]]},"abstract":"<jats:p>\n            We introduce the general problem of identifying a smallest\n            <jats:italic>edge<\/jats:italic>\n            subset of a given graph whose deletion makes the graph community-free. We consider this problem under two community notions that have attracted significant attention:\n            <jats:italic>k<\/jats:italic>\n            -truss and\n            <jats:italic>k<\/jats:italic>\n            -core. We also introduce a problem variant where the identified subset contains edges incident to a given set of nodes and ensures that these nodes are not contained in any community:\n            <jats:italic>k<\/jats:italic>\n            -truss or\n            <jats:italic>k<\/jats:italic>\n            -core, in our case. These problems are directly applicable in social networks: The identified edges can be\n            <jats:italic>hidden<\/jats:italic>\n            by users or\n            <jats:italic>sanitized<\/jats:italic>\n            from the output graph; or in communication networks: the identified edges correspond to\n            <jats:italic>vital<\/jats:italic>\n            network connections. We present a series of theoretical and practical results. On the theoretical side, we show through non-trivial reductions that the problems we introduce are NP-hard and, in fact, hard to approximate. For the\n            <jats:italic>k<\/jats:italic>\n            -truss-based problems, we also show exact exponential-time algorithms, as well as a non-trivial lower bound on the size of an optimal solution. On the practical side, we develop a series of heuristics that are sped up by efficient data structures that we propose for updating the truss or core decomposition under edge deletions. In addition, we develop an algorithm to compute the lower bound. Extensive experiments on 11 real-world and synthetic graphs show that our heuristics are effective, outperforming natural baselines, and also efficient (up to two orders of magnitude faster than a natural baseline), thanks to our data structures. Furthermore, we present a case study on a co-authorship network and experiments showing that the removal of edges identified by our heuristics does not substantially affect the clustering structure of the input graph.\n          <\/jats:p>\n          <jats:p>This work extends a KDD 2021 paper, providing new theoretical results as well as introducing core-based problems and algorithms.<\/jats:p>","DOI":"10.1145\/3644077","type":"journal-article","created":{"date-parts":[[2024,2,15]],"date-time":"2024-02-15T05:16:04Z","timestamp":1707974164000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["On Breaking Truss-based and Core-based Communities"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1782-667X","authenticated-orcid":false,"given":"Huiping","family":"Chen","sequence":"first","affiliation":[{"name":"University of Birmingham, Birmingham, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0770-2235","authenticated-orcid":false,"given":"Alessio","family":"Conte","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7985-4222","authenticated-orcid":false,"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0888-5061","authenticated-orcid":false,"given":"Grigorios","family":"Loukides","sequence":"additional","affiliation":[{"name":"King\u2019s College London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1445-1932","authenticated-orcid":false,"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[{"name":"CWI, Amsterdam, The Netherlands and Vrije Universiteit, Amsterdam, TheNetherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1200-6015","authenticated-orcid":false,"given":"Michelle","family":"Sweering","sequence":"additional","affiliation":[{"name":"CWI, Amsterdam, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,4,12]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"A. A. Hagberg D. A. Schult and P. J. Swart. 2023. Network-X 3.1. Retrieved from https:\/\/networkx.org\/documentation\/stable\/release\/release_3.1.html"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.11"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.3934\/nhm.2008.3.371"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1055797"},{"key":"e_1_3_3_7_2","article-title":"An O (m) algorithm for cores decomposition of networks","author":"Batagelj V.","year":"2003","unstructured":"V. Batagelj and M. Zaversnik. 2003. An O (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049 (2003).","journal-title":"arXiv preprint cs\/0310049"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3343038"},{"issue":"1","key":"e_1_3_3_9_2","first-page":"8","article-title":"Combinatorial algorithms for string sanitization","volume":"15","author":"Bernardini G.","year":"2020","unstructured":"G. Bernardini, H. Chen, A. Conte, R. Grossi, G. Loukides, N. Pisanti, S. P. Pissis, G. Rosone, and M. Sweering. 2020. Combinatorial algorithms for string sanitization. ACM Trans. Knowl. Discov. Data 15, 1, Article 8 (2020), 34 pages.","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"e_1_3_3_10_2","article-title":"Hide and mine in strings: Hardness, algorithms, and experiments","author":"Bernardini G.","year":"2023","unstructured":"G. Bernardini, A. Conte, G. Gourdel, R. Grossi, G. Loukides, N. Pisanti, S. Pissis, G. Punzi, L. Stougie, and M. Sweering. 2023. Hide and mine in strings: Hardness, algorithms, and experiments. IEEE Trans. Knowl. Data Eng. 35, 6 (2023).","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_3_3_11_2","first-page":"440","volume-title":"ICALP","author":"Bhawalkar K.","year":"2012","unstructured":"K. Bhawalkar, J. Kleinberg, K. Lewi, T. Roughgarden, and A. Sharma. 2012. Preventing unraveling in social networks: The anchored k-core problem. In ICALP. 440\u2013451."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/1024185"},{"key":"e_1_3_3_13_2","first-page":"1006","volume-title":"SIGMOD","author":"Bonchi F.","year":"2019","unstructured":"F. Bonchi, A. Khan, and L. Severini. 2019. Distance-generalized core decomposition. In SIGMOD. 1006\u20131023."},{"key":"e_1_3_3_14_2","first-page":"117","volume-title":"KDD","author":"Chen H.","year":"2021","unstructured":"H. Chen, A. Conte, R. Grossi, G. Loukides, S. P. Pissis, and M. Sweering. 2021. On breaking truss-based communities. In KDD. 117\u2013126."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231755"},{"key":"e_1_3_3_16_2","first-page":"3","article-title":"Trusses: Cohesive subgraphs for social network analysis","volume":"16","author":"Cohen J.","year":"2008","unstructured":"J. Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. Nat. Secur. Agency Tech. Rep. 16 (2008), 3\u201329.","journal-title":"Nat. Secur. Agency Tech. Rep."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.3011667"},{"key":"e_1_3_3_18_2","first-page":"115","volume-title":"KDD","author":"Conte A.","year":"2017","unstructured":"A. Conte, D. Firmani, C. Mordente, M. Patrignani, and R. Torlone. 2017. Fast enumeration of large k-plexes. In KDD. 115\u2013124."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2019.104464"},{"key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1145\/780542.780629","volume-title":"STOC","author":"Dinur I.","year":"2003","unstructured":"I. Dinur, V. Guruswami, S. Khot, and O. Regev. 2003. A new multilayered PCP and the hardness of hypergraph vertex cover. In STOC. 595\u2013601."},{"key":"e_1_3_3_21_2","first-page":"2258","volume-title":"IJCAI","author":"Ebadian S.","year":"2019","unstructured":"S. Ebadian and X. Huang. 2019. Fast algorithm for k-truss discovery on public-private graphs. In IJCAI. 2258\u20132264."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130411"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3418226"},{"key":"e_1_3_3_26_2","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/263661.263684","volume-title":"PODS","author":"Gunopulos D.","year":"1997","unstructured":"D. Gunopulos, H. Mannila, R. Khardon, and H. Toivonen. 1997. Data mining, hypergraph transversals, and machine learning. In PODS. 209\u2013216."},{"key":"e_1_3_3_27_2","first-page":"1311","volume-title":"SIGMOD","author":"Huang X.","year":"2014","unstructured":"X. Huang, H. Cheng, L. Qin, W. Tian, and J. X. Yu. 2014. Querying k-truss community in large and dynamic graphs. In SIGMOD. 1311\u20131322."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099626"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_3_30_2","doi-asserted-by":"crossref","first-page":"767","DOI":"10.1145\/509907.510017","volume-title":"STOC","author":"Khot S.","year":"2002","unstructured":"S. Khot. 2002. On the power of unique 2-prover 1-round games. In STOC. 767\u2013775."},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2019.10.004"},{"key":"e_1_3_3_33_2","first-page":"325","volume-title":"SDM","author":"Laishram R.","year":"2020","unstructured":"R. Laishram, A. E. Sar, T. Eliassi-Rad, A. Pinar, and S. Soundarajan. 2020. Residual core maximization: An efficient algorithm for maximizing the size of the k-core. In SDM. 325\u2013333."},{"key":"e_1_3_3_34_2","first-page":"609","volume-title":"WWW","author":"Laishram R.","year":"2018","unstructured":"R. Laishram, A. E. Sariy\u00fcce, T. Eliassi-Rad, A. Pinar, and S. Soundarajan. 2018. Measuring and improving the core resilience of networks. In WWW. 609\u2013618."},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.01.012"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.026118"},{"issue":"969","key":"e_1_3_3_39_2","first-page":"2","article-title":"Solution of the problem of P. Erdos on the number of triangles in graphs with n vertices and [n2\/4]+ l edges","volume":"34","author":"Nikiforov V. S.","year":"1981","unstructured":"V. S. Nikiforov and N. G. Khadzhiivanov. 1981. Solution of the problem of P. Erdos on the number of triangles in graphs with n vertices and [n2\/4]+ l edges. CR Acad. Bulgare Sci. 34, 969-970 (1981), 2.","journal-title":"CR Acad. Bulgare Sci."},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036106"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-017-1064-y"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/604264.604271"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_3_3_44_2","first-page":"54","article-title":"Density-friendly graph decomposition","author":"Tatti N.","year":"2019","unstructured":"N. Tatti. 2019. Density-friendly graph decomposition. ACM Trans. Knowl. Discov. Data (Sep.2019) Article 54, 29 pages.","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.3301758"},{"key":"e_1_3_3_46_2","first-page":"217","volume-title":"ICDE","author":"Wang Z.","year":"2020","unstructured":"Z. Wang, C. Wang, W. Wang, X. Gu, B. Li, and D. Meng. 2020. Adaptive relation discovery from focusing seeds on large networks. In ICDE. 217\u2013228."},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2833070"},{"key":"e_1_3_3_48_2","first-page":"2147","volume-title":"WWW","author":"Yang D.","year":"2019","unstructured":"D. Yang, B. Qu, J. Yang, and P. Cudre-Mauroux. 2019. Revisiting user mobility and social relationships in LBSNs: A hypergraph embedding approach. In WWW. 2147\u20132157."},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210021"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2880976"},{"key":"e_1_3_3_51_2","first-page":"245","volume-title":"AAAI","author":"Zhang F.","year":"2017","unstructured":"F. Zhang, Y. Zhang, L. Qin, W. Zhang, and X. Lin. 2017. Finding critical users for social network engagement: The collapsed k-core problem. In AAAI, Satinder P. Singh and Shaul Markovitch (Eds.). 245\u2013251."},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.14778\/3115404.3115406"},{"key":"e_1_3_3_53_2","first-page":"557","volume-title":"ICDE","author":"Zhang F.","year":"2018","unstructured":"F. Zhang, Y. Zhang, L. Qin, W. Zhang, and X. Lin. 2018. Efficiently reinforcing social networks over user engagement and tie strength. In ICDE. 557\u2013568."},{"key":"e_1_3_3_54_2","first-page":"4867","volume-title":"IJCAI","author":"Zhou Z.","year":"2019","unstructured":"Z. Zhou, F. Zhang, X. Lin, W. Zhang, and C. Chen. 2019. K-core maximization: An edge addition approach. In IJCAI. 4867\u20134873."},{"key":"e_1_3_3_55_2","first-page":"1667","volume-title":"CIKM","author":"Zhu W.","year":"2018","unstructured":"W. Zhu, C. Chen, X. Wang, and X. Lin. 2018. K-core minimization: An edge manipulation approach. In CIKM. 1667\u20131670."},{"key":"e_1_3_3_56_2","first-page":"4874","volume-title":"IJCAI","author":"Zhu W.","year":"2019","unstructured":"W. Zhu, M. Zhang, C. Chen, X. Wang, F. Zhang, and X. Lin. 2019. Pivotal relationship identification: The k-truss minimization problem. In IJCAI. 4874\u20134880."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3644077","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3644077","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:56:58Z","timestamp":1750291018000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3644077"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,12]]},"references-count":55,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,7,31]]}},"alternative-id":["10.1145\/3644077"],"URL":"https:\/\/doi.org\/10.1145\/3644077","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2024,4,12]]},"assertion":[{"value":"2022-12-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}