Facebook provides you the user's list of friends, and each friend's list of mutual friends with the user. From there, we construct the friend graph, and then run our clustering algorithm on it.
You're right about Facebook not providing friends of friends. Supposedly they used to back in the day, but not anymore.
Great service, did a great job on my list of friends. I would love to use this, but having to send over user access tokens is a little scary, even over HTTPS. Have you guys considered licensing this? Would be cool as a heroku plugin...
We thought about licensing it, and we'd probably feel comfortable doing so. However, the infrastructure required to run this is pretty intense and customized. We're actually pushing a patent for the infrastructure/technology behind it.