Note that yahoo does not seem to rely on graph algorithms to do that. To reach from X to Y, where X is not directly connected to Y, they ask X which of their friends might connect them to Y.
Have there been any other prominent attempts (besides the famous friendster feature) to validate this hypothesis?