On Breaking Truss-Based Communities

Huiping Chen; Alessio Conte; Roberto Grossi; Grigorios Loukidis; Solon  Pissis; Michelle Sweering

doi:10.1145/3447548.3467365

On Breaking Truss-Based Communities

Huiping Chen, Alessio Conte, Roberto Grossi, Grigorios Loukidis^*, Solon Pissis, Michelle Sweering

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

59 Downloads (Pure)

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
Pages (from-to)	117-126
Number of pages	10
Journal	ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)
DOIs	https://doi.org/10.1145/3447548.3467365
Publication status	Published - 14 Aug 2021

Access to Document

10.1145/3447548.3467365

rst2724-chenA-CC-BY_kdd_final_versionFinal published version, 1.32 MBLicence: CC BY

Cite this

@article{a12ade7456894af0989f9874f90b263d,

title = "On Breaking Truss-Based Communities",

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).",

author = "Huiping Chen and Alessio Conte and Roberto Grossi and Grigorios Loukidis and Solon Pissis and Michelle Sweering",

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: {\textcopyright} 2021 Owner/Author.",

year = "2021",

month = aug,

day = "14",

doi = "10.1145/3447548.3467365",

language = "English",

pages = "117--126",

journal = "ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)",

}

TY - JOUR

T1 - On Breaking Truss-Based Communities

AU - Chen, Huiping

AU - Conte, Alessio

AU - Grossi, Roberto

AU - Loukidis, Grigorios

AU - Pissis, Solon

AU - Sweering, Michelle

N1 - 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.

PY - 2021/8/14

Y1 - 2021/8/14

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=85114911177&partnerID=8YFLogxK

U2 - 10.1145/3447548.3467365

DO - 10.1145/3447548.3467365

M3 - Article

SP - 117

EP - 126

JO - ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)

JF - ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)

ER -

On Breaking Truss-Based Communities

Abstract

Access to Document

Other files and links

Fingerprint

Cite this