Efficient $k$-Truss Breaking and Minimization

The$k$-truss is a popular cohesive subgraph model for graph analysis, which requires each edge in the subgraph to be contained in at least$k-2$triangles, each consists three pairwisely connected edges. In this paper, we study the$k$-truss breaking problem (TBP) that aims to find the smallest set of edges whose removal makes the graph free of$k$-truss. The problem has been formulated in the literature with applications in community deception, critical connection identification, etc. However, existing solutions cannot scale to large graphs. We observe that chosen edges in a high-quality solution usually have high triangle support, while most share triangles with a significant number of easy-breaking edges (i.e., low-support edges). Motivated by these, we propose the Easy-Breaking Heuristic (EBH) that prioritizes the candidate edges based on their impact on easy-breaking edges. We also design several optimizations to further enhance the performance of EBH. Additionally, we extend our framework to efficiently handle the$k$-truss minimization problem (TMP), which aims to identify a set of at most$b$edges whose removal minimizes the size of the remaining k-truss. Extensive experiments demonstrate that our proposed algorithm outperforms state-of-the-art approaches by up to three orders of magnitude in efficiency when solving TBP, while maintaining comparable effectiveness. Additionally, our proposed algorithm achieves up to four orders of magnitude improvement in efficiency for TMP, along with generally better effectiveness.