Critical Edge Detection On Social Network Based On K-core And K-truss Model

With the rapid development of Internet,social networks such as facebook and twit-ter,have become an indispensable part of people’s daily life in recent years.And there has been growing interest in social networks.To measure the cohesiveness of subgraph,many subgraph models are proposed in literatures,such as k-core,k-truss k-plex,clique and so on.However,k-plex and clique have a strict constraint and cannot be computed in polynomial time,so the applications of these two models are limited.K-core and k-truss are simple and can be computed in polynomial time.So they are widely used in real world problems.In social networks,the strength of relationships between users can significantly affect the stability of the network.The willingness of a user to stay in a social network is affected by his/her friends in the social network.And the strength of relationship be-tween two users is usually affected by the number of their common friends.So mining critical relationship in social networks is very important.For instance,we can enhance the network stability by strengthening the important relations,or identify the crucial connections of an enemy’s network for attack purpose.In this thesis,we propose two novel problems based on the k-core and k-truss models,named k-core minimization and l-truss minimization problem.Given a graph G,an integer k and a budget b,we aim to find an edge set with size b,so that we can get the minimum k-core and k-truss by deleting B from G.We first formally define these two problems and prove they are NP-hard and cannot be approximated in a ratio.Due to the hardness of the problems,we propose a greedy based algorithm.To further speed up the computation,we pro-pose some novel pruning rules.In the k-truss minimization problem,we propose an upper bound based strategy to further reduce the searching space.Finally,we do com-prehensive experiments on 8 real-world social networks and demonstrate the efficiency and effectiveness of proposed techiques.Moreover,we compare the two models and demonstrate the truss model is better than core model.