Finding Similar Users in Social Networks

Authors: Aviv Nisgav Boaz PattShamir

Publish Date: 2010/12/22

Volume: 49, Issue: 4, Pages: 720-737

PDF Link

Abstract

We consider a system where users wish to find similar users To model similarity we assume the existence of a set of queries and two users are deemed similar if their answers to these queries are mostly identical Technically each user has a vector of preferences answers to queries and two users are similar if their preference vectors differ in only a few coordinates The preferences are unknown to the system initially and the goal of the algorithm is to classify the users into classes of roughly the same preferences by asking each user to answer the least possible number of queries We prove nearly matching lower and upper bounds on the maximal number of queries required to solve the problem Specifically we present an “anytime” algorithm that asks each user at most one query in each round while maintaining a partition of the users The quality of the partition improves over time for n users and time T groups of tildeOn/T users with the same preferences will be separated with high probability if they differ in sufficiently many queries We present a lower bound that matches the upper bound up to a constant factor for nearly all possible distances between user groups

Keywords: