Finding similar users in social networks
Aviv Nisgav, Boaz Patt-Shamir · 2009
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: each user has a vector of preferences, 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 with the least possible number of queries presented to any user. We prove nearly matching lower and upper bounds on that problem. ecifically, we present an "anytime" algorithm that maintains a partition of the users, and the quality of the partition improves over time: let n be the number of users. At time T, groups of Õ(n/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.