Locating pivotal connections: the K-Truss minimization and maximization problems

In social networks, the strength of relationships between users can significantly affect the stability of the network. Two users are more likely to build the friendship if they share some common friends. Meanwhile, the breakdown or enhancement of critical connections may lead to a cascaded phenomenon and cause the social network collapsed or reinforced. In this paper, we leverage the k-truss model to measure the stability of a social network. To identify the critical edges, we propose two novel problems named k-truss minimization problem and k-truss maximization problem. Given a social network G, a positive integer k and a budget b, it aims to find b edges for deletion (resp. addition), which can lead to the maximum number of edges collapsed (resp. added) in the k-truss of G. We prove that both problems are NP-hard. To accelerate the computation, novel pruning rules and searching paradigms are developed for the corresponding problem. Comprehensive experiments are conducted over 9 real-life networks to demonstrate the effectiveness and efficiency of our proposed models and approaches.