  In a social network, the strength of relationships between users can
significantly affect the stability of the network. In this paper, we use the
k-truss model to measure the stability of a social network. To identify
critical connections, we propose a novel problem, named k-truss minimization.
Given a social network G and a budget b, it aims to find b edges for deletion
which can lead to the maximum number of edge breaks in the k-truss of G. We
show that the problem is NP-hard. To accelerate the computation, novel pruning
rules are developed to reduce the candidate size. In addition, we propose an
upper bound based strategy to further reduce the searching space. Comprehensive
experiments are conducted over real social networks to demonstrate the
efficiency and effectiveness of the proposed techniques.
