Study On The Method Of Social Network Dismantling

Social network dismantling is a hot topic in the field of social network,it is widely used in network security,information dissemination and protein analysis.Nodedeleting and edge-deleting are two important research directions.In the aspect of nodedeleting research,the existing methods based on node centrality index ignore the influence of the loop structure in the process of dismantling network.The methods based on node decycling will mistakenly delete a large number of non-critical nodes in the process of decycling,which leads to the need to put back too many nodes.In fact,the traditional network dismantling methods based on node-deleting ignore the cost.The deletion of nodes leads to the deletion of corresponding edges,and the cost of deleting each node is different.Although the traditional network dismantling methods based on edge-deleting consider the deletion cost,the existing methods based on edge centrality index iteratively calculate centrality value in the global network,which has high time complexity.The methods based on region division iteratively divides the giant connected components in the network,but the deletion of connected edges is lack of pertinence and ignores the community structure of the network,so the performance and efficiency need to be improved.Aiming at the shortcomings of node-deleting methods,this thesis proposes a nodedeleting social network dismantling method based on neighbor nodes fusion.This algorithm uses the fusion strategy of neighbor nodes to reduce the influence of loop structure on network dismantling,it reflects a more realistic value of node centrality and effectively reduces the removing of non-critical nodes.At the same time,a reasonable nodes put back mechanism is designed to further reduce the deletion of noncritical nodes.Experimental results on real-world and artificial networks show that,the proposed method can more accurately select the critical nodes of network dismantling,through deleting fewer critical nodes can fully dismantle the network,and it shows stable performance and strong adaptability in networks with different structures and characters.Aiming at the shortcomings of edge-deleting methods,this thesis proposes an edge-deleting social network dismantling method based on Community Detection and Inverse Reinsertion of Edges.In the first stage,the whole network is divided into different communities by using community detection algorithm and then edges between communities are removed to destroy the connectivity of communities.In the second stage,the strategy of inverse reinsertion of edges is used to destroy the connectivity within each community.Thus,we can dismantle the whole network into pieces.Experimental results on real-world and artificial networks show that,our proposed method can dismantle networks by removing a smaller set of edges than that of other state-of-the-art methods.In addition,our proposed method exhibits stable performance with the variation of network scale,network structure and the threshold of network dismantling.In this thesis,we propose two new solutions to solve the social network dismantling problem,which improve some problems of the existing methods.This thesis proposes a node-deleting social network dismantling method based on neighbor nodes fusion to solve the problems of ignoring circle structure and putting back too many non-critical nodes in node-deleting method.At the same time,this thesis proposes an edge-deleting social network dismantling method based on Community Detection and Inverse Reinsertion of Edges to solve the problems of high complexity,poor accuracy and ignoring community structure in the method of edge-deleting.Compared with the existing methods,the two methods have excellent performance and good stability.