CommonFinder: A decentralized and privacy-preserving common-friend measurement method for the distributed online social networks

Distributed social networks have been proposed as alternatives for offering scalable and privacy-preserving online social communication. Recommending friends in the distributed social networks is an important topic. We propose CommonFinder, a distributed common-friend estimation scheme that estimates the numbers of common-friends between any pairs of users without disclosing the friends’ information. CommonFinder uses privacy-preserving Bloom filters to collect a small number of common-friend samples, and proposes low-dimensional coordinates to estimate the numbers of common friends from each user to any other users. Simulation results on real-world social networks confirm that CommonFinder scales well, converges quickly and is resilient to incomplete measurements and measurement noises.