Link perturbation in social network analysis through neighborhood randomization

Social network, as a new phenomenon, has opened new venues of research area in many sciences. Most studies on social networks require access to the data, which often contains sensitive information that needs to be anonymized before publication. One of such anonymized approaches is link privacy. A standard technique of link privacy is to probabilistically randomize the destination of a link in the local neighborhood of the source node of link, known as neighborhood randomization technique. In this paper, we propose an algorithm based on neighborhood randomization. Unlike previous studies, the proposed algorithm pays more attention to popular nodes in the social network structure. Given the low number of these nodes and the fact that the links of these nodes are more often threatened, they have been perturbed more than other nodes to preserve the privacy of popular nodes. The algorithm has been evaluated using real life social network data.