A privacy-preserving friend recommendation scheme in online social networks

Recently, online social networks (OSNs), which can offer many innovative services, are on the rise. As making friends is a basic way to create user's social relationship, friend recommendation is proposed to help users expand their social circles in OSNs. However, traditional friend recommendation process poses several crucial privacy breaches in OSNs, such as identity theft and relationship privacy leakage. Aimed to solve this problem, different from traditional friend recommendation schemes, based on the common interests by characterizing user's social behaviors/activities, we identify the threat model, and then propose a k-degree anonymous friend recommendation (KFR) scheme. Firstly, we abstract OSN as a hypergraph and then propose an edge segmentation algorithm to hide user's identity privacy and social relationship privacy. Subsequently, based on users' common interests, we design a similarity calculation algorithm. Finally, combined the similarity calculation algorithm with the segmentation tree (ST) technique, a novel k-degree anonymous friend recommendation scheme is proposed. The experiments carried out on real datasets show that the proposed scheme is scalable and effective.