A Negative Survey based Method for Preserving Topology Privacy in Social Networks

Currently, the rapid popularity of social network platforms makes the real social relations in social networks face the potential risk of disclosure. Therefore, most users may refuse to provide their social relations for the purpose of privacy preservation, which is not conducive to the development of social networks. The negative survey is an emerging sensitive information collection method, which can collect sensitive information while preserving personal privacy. In this paper, based on negative survey, we propose an algorithm called NetNS to preserve the privacy of social relations, namely the topology privacy of social networks. The proposed NetNS is simple and efficient, which only randomly divides the nodes in social networks into different groups, and disturbs the topology of each group by a dedicated negative survey model. Experiments are carried out on three real networks of different sizes. The experimental results show that compared to three algorithms tailored for topology privacy of social networks, the proposed NetNS can against graph structure attack while realizing better utility of social networks.