<p>I'm thinking of an application that would try to prove the "<a href="http://en.wikipedia.org/wiki/Six_degrees_of_separation" rel="nofollow noreferrer">Six degrees of separation</a>" theory with a set of users that are part of a social network.</p>

<p>I would have those elements:</p>

<ol>
<li>A couple of users for which I'd like to prove the six degrees theory</li>
<li>For each user, I know the list of friends in the social network</li>
</ol>

<p>Which is the best algorithm to see if the two users are connected, with which degree and show the eventual steps in the connection?</p>

Some additional background material:
To solve this problem generally, you'd want to avoid web scraping and other ad-hoc techniques that are specific to one social network.  Instead, you will probably want to look into
XHTML Friends Network (XFN)
which is a way to use the rel="" attribute of a hyperlink to indicate the relationship between the target of that hyperlink and you. There is also a competing standard called
FOAF
which uses
RDF
.
These
microformats
have been around for a while, but support for them has grown a great deal just recently.  StackOverflow uses "me" in the link on your profile page.  WordPress blogs provide an easy way in the editing interface for the blogroll to add these tags.  Many social sites use these in links between friends to indicate relationships.
Because of this, Google has gotten interested in this, and is starting to mine this data.  They have a
Social Graph API
that can mine both XFN and FOAF data to do exactly some of the things you want to do. I suggest you start there.  The nice thing about Google's API is since they are mining this all over the web, you can widen out your search beyond the specific social network you had in mind.