FA+
Shop
Suggestion algorithm (super-nerdery inside)
14 years ago
(Crossposted from LJ)
While killing time in a boring meeting yesterday, I was wrestling with the problem of a suggestion algorithm for discrete sets- specifically, friend lists. It's either that or zone out and stare at the ceiling. Would anyone who reads this (as I know a lot of nerds will see this) happen to know if an algorithm like this exists already?
Assume there's a network of users (U) that can befriend each other. Each user can follow or not follow any other user, i.e. Twitter style, not Facebook style. Basically a directed graph. The problem is to calculate "suggested" friends based on a user's friend list versus the rest of the network.
Sure, it's probably been done to death, but here's what I came up with:
Let A be the list of friends of a given user in the network
Let B[i] represent another user's friend list (that is not A).
For each B[i], calculate the size of A (intersect) B[i], and call this C. This is the number of friends the two users share.
For each user NOT in A (intersect) B[i], assign them C "points". This is a weighting factor so that users with extremely similar friend groups (but may not know each other) will have a greater influence on the outcome.
Calculate the total "points" for each user and sort in descending order.
The obvious problem with this is that it has a complexity of something ridiculous like O(n^2) speed and O(n) memory. Oh well.
Here's an example:
A friends: B, C, E, F
B friends: A, C, F
C friends: A, D
D friends: B, C
Say you want to suggest a friend for D. (the x means intersection):
D x A: 2, so E and F get 2 points
D x B: 1, so A and F get 1 point
D x C: 0, so nobody gets any points.
Your result is F=3, E=2, A=1, so you recommend that D check out E. Obviously a terrible example, but that's basically how it works.
Has this been done before? I'm beginning to doubt it, due to the inefficiency and the fact that you have to know the entire network beforehand. You could potentially speed it up by restricting computations to only users with N friends in common, or only compare against friends' friend-lists. It would be interesting to attempt at least, just to see if it spits out anything useful.
And that's what I really do at work... hmm...
---
In other news... I can't believe May's almost over. I remember when it was "oh shit Cinco de Mayo is right around the corner" and now I can't even remember what day it is.
Up, work, home, TV^H^H computer, bed.
While killing time in a boring meeting yesterday, I was wrestling with the problem of a suggestion algorithm for discrete sets- specifically, friend lists. It's either that or zone out and stare at the ceiling. Would anyone who reads this (as I know a lot of nerds will see this) happen to know if an algorithm like this exists already?
Assume there's a network of users (U) that can befriend each other. Each user can follow or not follow any other user, i.e. Twitter style, not Facebook style. Basically a directed graph. The problem is to calculate "suggested" friends based on a user's friend list versus the rest of the network.
Sure, it's probably been done to death, but here's what I came up with:
Let A be the list of friends of a given user in the network
Let B[i] represent another user's friend list (that is not A).
For each B[i], calculate the size of A (intersect) B[i], and call this C. This is the number of friends the two users share.
For each user NOT in A (intersect) B[i], assign them C "points". This is a weighting factor so that users with extremely similar friend groups (but may not know each other) will have a greater influence on the outcome.
Calculate the total "points" for each user and sort in descending order.
The obvious problem with this is that it has a complexity of something ridiculous like O(n^2) speed and O(n) memory. Oh well.
Here's an example:
A friends: B, C, E, F
B friends: A, C, F
C friends: A, D
D friends: B, C
Say you want to suggest a friend for D. (the x means intersection):
D x A: 2, so E and F get 2 points
D x B: 1, so A and F get 1 point
D x C: 0, so nobody gets any points.
Your result is F=3, E=2, A=1, so you recommend that D check out E. Obviously a terrible example, but that's basically how it works.
Has this been done before? I'm beginning to doubt it, due to the inefficiency and the fact that you have to know the entire network beforehand. You could potentially speed it up by restricting computations to only users with N friends in common, or only compare against friends' friend-lists. It would be interesting to attempt at least, just to see if it spits out anything useful.
And that's what I really do at work... hmm...
---
In other news... I can't believe May's almost over. I remember when it was "oh shit Cinco de Mayo is right around the corner" and now I can't even remember what day it is.
Up, work, home, TV^H^H computer, bed.
But to answer your question; I dunno if there is a specific name for that way, but I think there is something like that.