An idea

[cellis]

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??

[ed]

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.

[brett → ed]

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.

[ed → ed]

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.

[danteembermage → ed]

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

[eru → ed]

Pretty clever? Findind the shortest path between two nodes in a graph is more or less a solved problem..

[ph0rque]

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.

[ratsbane]

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?

[eru → ratsbane]

Findind the shortest path between two nodes in a graph has nothing to do with the Traveling Salesman problem. You could use e.g. linear optimization to solve it. The Problem here lies in P.

[ratsbane → eru]

You're exactly right - [argh] it's not at all the traveling salesman problem. Thanks for the correction.

In any case, the thesis of my post was that it's a totally solvable problem and that you could use other factors to reduce the number of nodes - like looking for shared group or network memberships.

I think this is the relavant bit? http://en.wikipedia.org/wiki/Dijkstra's_algorithm Except that the Facebook thing wouldn't be a weighted graph - unless you wanted to consider length of time people have been marked as friends, or count "worked together" more or less than some other form of association.

[eru → ratsbane]

Or you just set the weights to one. You could even use an A*-Algorithm that uses geography as a hint.

[blackdog]

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.

[ratsbane → blackdog]

I think that would violate the TOS ( http://www.facebook.com/terms.php ) "In addition, you agree not to use the Service or the Site to: ...use automated scripts to collect information from or otherwise interact with the Service or the Site;"

The developer TOS don't, as far as I can tell, provide exceptions to this. In fact, the following seems to quash the whole idea of crawling:

"4) You may not store any Facebook Properties in any Data Repository which enables any third party (other than the Applicable Facebook User for such Facebook Properties) to access or share the Facebook Properties without our prior written consent."

But perhaps they would be willing to consent if you asked?

I think it's a good idea.

[cellis → ratsbane]

I'm going to the whiteboard!

[cellis → blackdog]

wow, very interesting. I guess I'll have to read up on NP-hard problems then, no?

[bmaier]

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.

[kf → bmaier]

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.

[bmaier → kf]

Might be a bit late on the reply but the $10 cpm seems to be an inflated statistic. The ones that are quoting that are getting rates of 10 per cpm on the canvas page while in reality that page is only a small fraction of the total page views. If the canvas page accounts for 1/3 of total page views then that statistic gets brought down to a lower number cpm for total pageviews. Is this consistent with what others are seeing?