How to determine likely connections in a social network?

Problem Detail: 

I am curious in determining an approach to tackling a "suggested friends" algorithm.

Facebook has a feature in which it will recommended individuals to you which it thinks you may be acquainted with. These users normally (excluding the edge cases in which a user specifically recommends a friend) have a highly similar network to oneself. That is, the number of friends in common are high. I assume Twitter follows a similar path for their "Who To Follow" mechanism.

Stephen Doyle (Igy), a Facebook employee suggested that the related newsfeed that uses EdgeRank formula which seems to indicate that more is to valued than friends such as appearance is similar posts. Another user suggested the Google Rank system.

Facebook states their News Feed Optimization as $\sum u_{e}w_{e}d_{e}$ where

$u_{e}$ = affinity score between viewing user and edge creator
$w_{e}$ = weight for this edge (create, comment, like, tag, etc)
$d_{e}$ = time decay factor based on how long ago the edge was created

Summing these items is supposed to give an object's rank which I assume as Igy hinted, means something in a similar format is used for suggested friends.

So I'm guessing that this is the way in which connections for all types are done in general via a rank system?

Asked By : phwd

Answered By : Dave Clarke

You can think of the social graph as a matrix $\mathbf{M}$. One approach to the problem is to first calculate $\mathbf{M}^2$, which will give all of the paths of length two between two actors in the social network. This can be seen as the weight of the connection between these friends of friends. The next step is to select the columns from the row of $\mathbf{M}^2$ corresponding to the person of interest to get the best candidates for new friends.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/261