Link Privacy Protection Based On Random Walk

With the rise of social media,more and more users choose to share personalized information to social network services,and more and more information is exposed to social networks.The openness of information has caused people to pay attention to privacy protection.Therefore,privacy protection is required before data is published.Many of the relationships in social networks are sensitive information,and the relationship between users should be protected when publishing social networks.How to effectively protect the privacy of links between users in social networks has attracted more and more attention.This thesis is based on random walks to protect the connection privacy of social networks,the main research work is as follows:1)This thesis studies the privacy protection of links between users and users in social networks.This thesis applies the random walk algorithm to weighted social networks,and proposed a link privacy protection scheme on weighted graphs(WRW).Random walk is used to randomly select the destination nodes of fake links,and fake links are used instead of real links.It also provides a false weight for the false link.While protecting the relationship between users,the distribution of the weights can be kept small.Finally,through simulation experiments,the link prediction attack is simulated,and the disturbed social network is reconstructed.The result proves that the scheme can protect the link privacy of the social network.The structure of the social network graph after disturbance is analyzed from the average shortest path length,degree distribution,weight distribution,edge change rate and other indicators.It proves that the scheme preserves the structural characteristics of the network while maintaining the connection availability,and maintains the network availability.2)Based on the WRW algorithm,this paper considers the similarity between nodes and proposes the improved WRW algorithm.The idea of the scheme is to sort the similarities between the nodes in the original graph,and disturb the link with high similarity.Due to the focus on disrupting links with similarities,our solution is better able to withstand link-predicted attacks.At the same time,the solution does not disturb all links,so it can better maintain the utility of social networks,such as the shortest path of social networks,weight distribution,degree distribution and so on.3)Due to the possible directionality of the relationship in social networks,this thesis proposes a link privacy protection scheme for directed networks based on random walk for directed social network.When disturbing the link,the direction of the link and the degree of the node are considered.When traversing a node in a social network,it only disturbs the edge of the node and adds a false edge.On the one hand,it can disrupt the link of the social network,on the other hand,it can keep the node's output degree unchanged.Finally,in the experimental demonstration,our solution can protect the privacy of the directed social network,while retaining the average shortest path,the distribution of the social network,etc.,can basically keep the graph more usable.