I’m going to take a bit of a guess here that it is actually a pretty complicated implementation of a 6 degrees of separation thing, except a bit more complicated. In fact, networking, especially social networking, has been a very hot topic for research in algorithms in recent years. Considering that this is what Facebook is designed for, I wouldn’t see it as surprising that they might have some pretty complicated implementations.
For instance, you have the obvious example where two people share mutual friends, there’s a certain probability that they probably know eachother. However, the thing to keep in mind here is that having some number of friends in common isn’t going to translate linearly to a probability. Say, for instance, me and Aaron each know Beth, Chad, and David all of whom are fairly normal users, then it’s fairly likely that Aaron and I know eachother. Now consider a scenario where Aaron and I share three friends, but these friends are, say, Barrack Obama, Cameron Diaz, and David Beckham (sticking with my alphabetic naming convention); if they’re on Facebook (I have no idea), chances are they’d have plenty more connections than everyone else, so it’s much less likely that Aaron and I know eachother based on those connections.
Now extrapolate this out another level, where Aaron and I don’t have any friends in common, but many of our friends have some level of established connections, like say I know Beth, Chad, and David who are all mutually friends with Eric, Frank, and George who are friends with Aaron, then it’s not unlikely that Aaron and I know eachother.
They also have other information at their disposal, like what high school or college you went to, where you live, where you work, your age, etc. and all of that can be used in there as well. The quote upthread also says it make look at cookies, so it’s not unlikely that it could see that two people two people visit a site that tends to have a tighter connection (like the SDMB vs. ESPN.com), and it would also use that to weight common connections more.
To walrus and Philster, the reason that experiment didn’t work is probably because that’s not how people generally interact. I’d think that it really can’t work unless you actually made some connections and worked them. That is, I’d guess that not all friends are created equally. If I were on facebook and interacted heavily with some friends, but not with others, I’d think those links would be weighted more than the other ones, so even if I have fewer connections to someone through those links than with someone else that I don’t interact with much, it may guess that I’m more likely to know the former. If someone just creates a Facebook account, but never makes friends, or has very few friends, and never interacts with them, I’d suspect that it won’t do a very good job of connecting them to anyone.