Privacy-preserving and efficient friend recommendation in online social networks

Bharath K. Samanthula, Lei Cen, Wei Jiang, Luo Si

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


The popularity of online social networks (OSNs) is on constant rise due to various advantages, including online communication and sharing information of interest among friends. It is often that users want to make new friends to expand their social connections as well as to obtain information from a broad range of people. Friend recommendation is a very important application in many OSNs and has been studied extensively in the recent past. However, with the growing concerns about user privacy, there is a strong need to develop privacy-preserving friend recommendation methods for social networks. In this paper, we propose two novel methods to recommend friends for a given user by using the common neighbors proximity measure in a privacy-preserving manner. The first method is based on the properties of an additive homomorphic encryption scheme and also utilizes a universal hash function for efficiency purpose. The second method utilizes the concept of protecting the source privacy through anonymous message routing and recommends friends accurately and efficiently. In addition, we empirically compare the efficiency and accuracy of the proposed protocols, and address the implementation details of the two methods in practice. The proposed protocols provide a trade-off among security, accuracy, and efficiency; thus, users or the network provider can choose between these two protocols depending on the underlying requirements.

Original languageEnglish
Pages (from-to)141-171
Number of pages31
JournalTransactions on Data Privacy
Issue number2
StatePublished - Jun 29 2015

ASJC Scopus subject areas

  • Software
  • Statistics and Probability


  • Encryption
  • Friend recommendation
  • Online social network
  • Privacy

Cite this