Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An idea

news.ycombinator.com

Post reply on HN
Print view View original

11–18 of 18 posts

Re: An idea

#11

Post by eru »

ratsbane wrote: post #10

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-g…

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.

Re: An idea

#12

Post by eru »

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.

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

Re: An idea

#13

Post by cellis »

blackdog wrote: post #5

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.

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

Re: An idea

#14

Post by ratsbane »

eru wrote: post #11
ratsbane wrote: post #10

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-g…

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.

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.

Re: An idea

#15

Post by ratsbane »

blackdog wrote: post #5

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.

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.

Re: An idea

#16

Post by cellis »

ratsbane wrote: post #15
blackdog wrote: post #5

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.

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 Pr…

I'm going to the whiteboard!

Re: An idea

#17

Post by bmaier »

rms wrote: post #3
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.

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?

Re: An idea

#18

Post by eru »

ratsbane wrote: post #14
eru wrote: post #11

Earlier quoted context omitted.

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.

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 w…

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