Privacy-preserving user clustering in a social network

In a ubiquitously connected world, social networks are playing an important role on the Internet by allowing users to find groups of people with similar interests. The data needed to construct such networks may be considered sensitive personal information by the users, which raises privacy concerns. The problem of building social networks while user privacy is protected is hence crucial for further development of such networks. K-means clustering is widely used for clustering users in a social network. In this paper, we provide an efficient privacy-preserving variant of K-means clustering. The scenario we consider involves a server and multiple users where users need to be grouped into K clusters. In our protocol the server is not allowed to learn the individual user data and users are not allowed to learn the cluster centers. The experiments on the MovieLens dataset show that deployment of the system for real use is reasonable as its efficiency even on conventional hardware is promising.