Abstract
A k-truss is a graph such that each edge is contained in at least k-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 k-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 k-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 exponential-time 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).
Original language | English |
---|---|
Title of host publication | KDD '21 |
Subtitle of host publication | Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining |
Publisher | Association for Computing Machinery |
Pages | 117-126 |
Number of pages | 10 |
ISBN (Electronic) | 9781450383325 |
DOIs | |
Publication status | Published - 14 Aug 2021 |
Event | 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2021 - Virtual, Online, Singapore Duration: 14 Aug 2021 → 18 Aug 2021 |
Publication series
Name | Proceedings of the International Conference on Knowledge Discovery and Data Mining |
---|---|
Publisher | ACM |
ISSN (Print) | 2154-817X |
Conference
Conference | 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2021 |
---|---|
Country/Territory | Singapore |
City | Virtual, Online |
Period | 14/08/21 → 18/08/21 |
Bibliographical note
Funding Information:Acknowledgments H. Chen was supported by CSC scholarship. M. Sweering was supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003. A. Conte and R. Grossi were partially supported by MIUR, Grant 20174LF3T8 AHeAD.
Publisher Copyright:
© 2021 Owner/Author.
Keywords
- community detection
- graph algorithm
- k-truss
ASJC Scopus subject areas
- Software
- Information Systems