2 Replies - 1092 Views - Last Post: 03 December 2012 - 02:40 AM

#1 LDaneil  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 3
  • Joined: 25-June 09

how to calculate the similarity of two users in facebook?

Posted 02 December 2012 - 07:19 PM

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 hastags & statuses of each user. Can anyone tell me a good way to fast calculate the similarity between two users? I have tried to use FT-IDF to calculate the similarity between two different users, but it seems infeasible. 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?

Is This A Good Question/Topic? 1
  • +

Replies To: how to calculate the similarity of two users in facebook?

#2 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1148
  • View blog
  • Posts: 2,528
  • Joined: 05-May 05

Re: how to calculate the similarity of two users in facebook?

Posted 02 December 2012 - 08:25 PM

Locality-sensitive hashing is often used for similarity matching/nearest neighbor problems, comparing N objects in O(N) time. The idea is that if two pieces of data are similar, their hashes will be similar. Perhaps you could use the 100 or 1000 most-popular hash tags as your high-dimensional data, and then you can represent each person as a binary array, where a 1 at some index indicates they have listed whatever tag is associated with that index, and 0 otherwise. Unfortunately, LSH isn't a widely studied topic, so there's not a ton of easy-to-digest information on it. Here are a few sources that may help to get you started.

Reading:

Web Intelligence Lecture on LSH
Locality Sensitive Hashing and Large Scale Image Search
A theoretical treatment of Bayesian LSH and similarity search (direct link to PDF)

Implementations:

C#/C++ Libraries
Java Libraries

This post has been edited by blackcompe: 02 December 2012 - 08:28 PM

Was This Post Helpful? 2
  • +
  • -

#3 LDaneil  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 3
  • Joined: 25-June 09

Re: how to calculate the similarity of two users in facebook?

Posted 03 December 2012 - 02:40 AM

hi, blackcompe :smartass: Thank you very much for your good suggestions. :clap:

Locality-sensitive hashing is a very new concept for me, I will go to read it carefully. In fact, the idea is there, the only thing need to do is to modify the data structure to make it feasible to implement with this kind of huge, my main focus here is the time complexity and space complexity concern. The main purpose here is to find the related similarity between all the users, but in real facebook life, we may know only a very very small portion, it means there are actually a very very small group who have somewhat similarity with a particular person, if I directly calculate the similarity between each user, it will go through a lot of unnecessary similarity calculation, which waste a lot of time. So that I thought of filtering out all those unrelated users first, and find out that so-called related group first. The final step is to calculate the similarity between a particular person with his related group only, this way may be much faster than directly calculating the similarity. Use normal data structure:

Step 1: use an array to store the 6 million(6m)users
use link list to chain all the related users to a particular user

Problem: Search time complexity is huge. Time complexity = O(6m*6m*K)
K is the number of distinct hashtags a particular user has.

1. select a particular user, search all other users(6m)
2. there are 6 million users (6m)
3. each user may have a large amount of distinct hashtags (K)

From the analysis above, using normal data structure is infeasible. I will go to read
Locality-sensitive hashing mentioned by blackcompe, Thank you very much again, bro.



View Postblackcompe, on 02 December 2012 - 08:25 PM, said:

Locality-sensitive hashing is often used for similarity matching/nearest neighbor problems, comparing N objects in O(N) time. The idea is that if two pieces of data are similar, their hashes will be similar. Perhaps you could use the 100 or 1000 most-popular hash tags as your high-dimensional data, and then you can represent each person as a binary array, where a 1 at some index indicates they have listed whatever tag is associated with that index, and 0 otherwise. Unfortunately, LSH isn't a widely studied topic, so there's not a ton of easy-to-digest information on it. Here are a few sources that may help to get you started.

Reading:

Web Intelligence Lecture on LSH
Locality Sensitive Hashing and Large Scale Image Search
A theoretical treatment of Bayesian LSH and similarity search (direct link to PDF)

Implementations:

C#/C++ Libraries
Java Libraries

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1