An idea

#1

Post by cellis » Thu, Aug 16, 2007, 3:06 AM UTC

ok, so yeah I have this idea. And I don't mind telling people about it. If you want to do it, go ahead, but first let me know what you think.

I'm sure everyone has heard of this, and I'm pretty sure this has already been thought of (what hasn't, right?) but I haven't seen it in my feed pop up in the myriad facebook apps my friends have added. The pitch: facebook app/six degrees of separation game (find out how many steps to a random person (if possible)). Just had this idea like two minutes ago. Any thoughts??

Re: An idea

#2

Post by bmaier » Thu, Aug 16, 2007, 3:42 AM UTC

It seems like an interesting idea but what does it do other than add one more app to facebook. It seems like work that might not add much value. jmho but if you're going to put out the effort put it into something more beneficial.

Re: An idea

#3

Post by rms » Thu, Aug 16, 2007, 4:05 AM UTC

bmaier wrote: post #2

It seems like an interesting idea but what does it do other than add one more app to facebook. It seems like work that might not add much value. jmho but if you're going to put out the effort put it into something more beneficial.

if you can get an app with a million users you can make money because facebook app advertisers are overpaying for now. i've heard $10 cpm which is almost as high as during the bubble.

Re: An idea

#4

Post by ph0rque » Thu, Aug 16, 2007, 4:19 AM UTC

I was just thinking about the same thing a few hours ago. I think this would be useful because if I wanted e.g. someone to introduce me to a potential investor, I could look the investor up on FB and see if I am connected to that person, and ask the "connectors" to introduce me.

Re: An idea

#5

Post by blackdog » Thu, Aug 16, 2007, 5:09 AM UTC

With the current primitives, it'd be pretty hard to do. You can get a list of your friends, but you can't do get a list of their friends - the best you can do is ask if two people are connected. you'd basically have to keep an offline list of the facebook web of connections.

Re: An idea

#6

Post by ed » Thu, Aug 16, 2007, 5:13 AM UTC

Wonder if you'd have enough user data exposed through the API to actually map out the relevant network... computationally it'd be fairly trivial to verify the user's guess, but you'd have a hell of a time actually calculating minimum distance with a dataset as large as Facebook's. That's why for the most part you won't see a social network telling you how two users are connected beyond a distance of two hops.

Re: An idea

#7

Post by ed » Thu, Aug 16, 2007, 5:18 AM UTC

ed wrote: post #6

Wonder if you'd have enough user data exposed through the API to actually map out the relevant network... computationally it'd be fairly trivial to verify the user's guess, but you'd have a hell of a time actually calculating minimum distance with a dataset as large as Facebook's. That's why for the most part you won't see a social network telling you how two users are connected beyond a distance of two hops.

Just for fun i calculated the worst-case state space for a network assuming that the average node has 150 peers -- out to 6 hops you have roughly 10^13 unique paths. Not impossible to work with, but you'd have to get pretty clever to reduce the computing time to something practical.

Re: An idea

#8

Post by danteembermage » Thu, Aug 16, 2007, 5:32 AM UTC

ed wrote: post #7

ed wrote: post #6

Wonder if you'd have enough user data exposed through the API to actually map out the relevant network... computationally it'd be fairly trivial to verify the user's guess, but you'd have a hell of a time actually calculating minimum distance with a dataset as large as Facebook's. That's why for the most part you won't see a social network telling you how two users are connected beyond a distance of two hops.

Just for fun i calculated the worst-case state space for a network assuming that the average node has 150 peers -- out to 6 hops you have roughly 10^13 unique paths. Not impossible to work with, but you'd have to get pretty clever to reduce the computing time to something practical.

Didn't we just see a post about a quantum computer designed to address the traveling salesman problem? Maybe that was reddit...

Re: An idea

#9

Post by brett » Thu, Aug 16, 2007, 7:07 AM UTC

ed wrote: post #6

Wonder if you'd have enough user data exposed through the API to actually map out the relevant network... computationally it'd be fairly trivial to verify the user's guess, but you'd have a hell of a time actually calculating minimum distance with a dataset as large as Facebook's. That's why for the most part you won't see a social network telling you how two users are connected beyond a distance of two hops.

I seem to remember Max Levchin talking about this exact problem at Startup School. He was talking about how Friendster shot themselves in the foot by calculating all the hops between you and whomever's profile you were viewing, slowing page load significantly. He pointed out that Myspace provided similar user experience by simply slapping "Is in your extended network" on all pages.

Re: An idea

#10

Post by ratsbane » Thu, Aug 16, 2007, 2:21 PM UTC

It would be quite neat to be able to do that. Ancestry.com is another site that should offer something like that... enter your family tree and then pick some random person who also has a family tree on file and show how you're related. They can't even do that within your own family tree (e.g. pick a person in your family tree and tell you "Augustus is your fourth cousin three times removed" or "Myrtle is your great-grandmother."

It is an example of the traveling salesman problem but there are ways of optimizing that... think about chess, or how google maps and the other map programs give you a route to a destination. If they had to check every single intersection it would be NP-complete. Instead they use the distance between two points as a weighting factor and try to find major arteries near both points.

I think you could do the same thing with Facebook et al - first look for common groups between people and then look for people who have pairs of common groups which would help to connect the people.

But you would have to have a reasonably complete set of Facebook data to work on. I wonder if they'd mind if you crawled their entire network and then did it again every few days, just to keep things current?