https://hal.inria.fr/hal-03498386Chen, HuipingHuipingChenDepartment of Informatics [King's College London] - King‘s College LondonConte, AlessioAlessioConteDI - Dipartimento di Informatica [Pisa] - University of Pisa - Università di Pisa Grossi, RobertoRobertoGrossiERABLE - Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale - Inria Grenoble - Rhône-Alpes - Inria - Institut National de Recherche en Informatique et en AutomatiqueDI - Dipartimento di Informatica [Pisa] - University of Pisa - Università di Pisa Loukides, GrigoriosGrigoriosLoukidesDepartment of Informatics [King's College London] - King‘s College LondonPissis, SolonSolonPissisCWI - Centrum Wiskunde & InformaticaVU - Vrije Universiteit Amsterdam [Amsterdam]ERABLE - Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale - Inria Grenoble - Rhône-Alpes - Inria - Institut National de Recherche en Informatique et en AutomatiqueSweering, MichelleMichelleSweeringCWI - Centrum Wiskunde & InformaticaOn Breaking Truss-Based CommunitiesHAL CCSD2021graph algorithmk-trusscommunity detection[INFO] Computer Science [cs]Sagot, Marie-France2021-12-21 08:56:512023-03-15 08:53:382021-12-21 09:57:00enConference papershttps://hal.inria.fr/hal-03498386/document10.1145/3447548.3467365application/pdf1A-truss is a graph such that each edge is contained in at least − 2 triangles. This notion has attracted much attention, because it models meaningful cohesive subgraphs of a graph. We introduce the problem of identifying a smallest edge subset of a given graph whose removal makes the graph-truss-free. We also introduce a problem variant where the identified subset contains only edges incident to a given set of nodes and ensures that these nodes are not contained in any-truss. These problems are directly applicable in communication networks: the identified edges correspond to vital network connections; or in social networks: the identified edges can be hidden by users or sanitized from the output graph. We show that these problems are NP-hard. We thus develop exact exponentialtime algorithms to solve them. To process large networks, we also develop heuristics sped up by an efficient data structure for updating the truss decomposition under edge deletions. We complement our heuristics with a lower bound on the size of an optimal solution to rigorously evaluate their effectiveness. Extensive experiments on 10 real-world graphs show that our heuristics are effective (close to the optimal or to the lower bound) and also efficient (up to two orders of magnitude faster than a natural baseline).