how to calculate the similarity of two users in facebook? [closed]

Question

I am working on a project about data mining. My company has given me 6 million dummy customer info of Facebook. I was assigned to find out the similarity between any two users. Can anyone could give me some ideas how to deal with the large community data? Thanks in advance :)

Problem : I use the status info & hashtag info(hashtags are those words highlighted by user) as the two criteria to measure the similarity between two different users. Since the large number of users, and especially there may be millions of hashtags & statuses of each user. Can anyone tell me a good way to fast calculate the similarity between two users? I have tried to use TF-IDF to calculate the similarity between two different users, but it seems unfeasible. Can anyone have a very super algorithm or good ideas which could make me fast find all the similarities between users?

For example:

user A's hashtag = `{cat, bull, cow, chicken, duck}`
user B's hashtag =`{cat, chicken, cloth}` 
user C's hashtag = `{lenovo, Hp, Sony}`

clearly, C has no relation with A, so it is not necessary to calculate the similarity to waste time, we may filter out all those unrelated user first before calculate the similarity. In fact, more than 90% of the total users are unrelated with a particular user. How to use hashtag as criteria to fast find those potential similar user group of A? Is this a good idea? Or we just directly calculate the relative similarity between A and all other users? What algorithm would be the fastest and customized algorithm for the problem?

Answer 1

User vector representation

Using what you defined is ok. You can also include facebook likes, which is a good representation of user interest.

Similarity function

Either cosine distance or Jaccard similarity is appropriate for your case.

Finding similar users for a giving user

K-d Tree approach

You construct the k-d tree first, then for any given user, you can launch a query for that user, the kd-tree is able to return your the k-nearest-neighbor based on the similarity function. A good implementation in c++ is here.

locality-sensitive-hashing approach

You hash users to different buckets. Similar users have higher probability to be hashed together. So for similar user search, you only compare users in the same bucket. Check this for examples: How to understand Locality Sensitive Hashing?

clustering approach

Try those clustering algorithms like k-means. This could be your first step to group users in small number of clusters and then you can do your O(n^2) comparison among all pairs of users in the group.

collaborative-filtering approach.

Treat those likes or hashtags as items liked by users. You can try the collaborative-filtering approach then. For millions of users, you might want to use some map-reduce-based implementations, e.g., mahout.