Abstract
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