3
$\begingroup$

Let Alice and Bob be two users chosen uniformly at random from a social network (e.g. Facebook). What is the probability that they are friends assuming that they share $k$ mutual friends?

I am interested both in the experimental values (or estimates) from currently existing social networks (e.g. Facebook) and values predicted by random graph models for these social networks.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ You should be more precise about the model of the social network you use. You probably know that the Erdös Rényi produces graphs that have not the properties of SN-friendships graphs (such as small diameter and power law distributed degrees). An alternative would be the Watts-Strogatz model. But you have to specify which parameters you use for this model, also there are several variants, such as the modification of Jon Kleinberg that allows decentralized search. $\endgroup$
    – A.Schulz
    Sep 16, 2012 at 8:21
  • $\begingroup$ @A.Schulz, I don't have any particular model in mind, as long as the model is deemed to model the friendship graph over a social network like Facebook it is interesting for me. $\endgroup$
    – Kaveh
    Sep 17, 2012 at 0:56

1 Answer 1

Reset to default
3
$\begingroup$

Okay, this is my approach to this problem. I think the key concept here is the clustering coefficient $c$. The value of $c$ is denotes how likely it is that two nodes are connected by an edge, if the have a common neighbor. In SN-friendship graphs the clustering coefficient is usually high compared to classical random graph models, such as Erdös-Rényi.

What is known about the clustering coefficient of the facebook-graph? If you follow the presentation of this paper, for a node of degree 100, we have $c=0.14$. Assuming that you have 100 friends is a reasonable assumption than it is close to the median degree (about 99, see here) and the average degree (might be around 95, see here).

Lets make the bold assumption, that the events that a tie between two nodes $A$ and $B$ is present if they have friend $X$ in common, are independent. Then we get

$$\begin{align} P[\text{$A$ and $B$ are friends}] & = 1 - P[\text{$A$ and $B$ are not friends}] \\ &=1-(1-c)^k. \end{align}$$

A plot of this function looks like this:

enter image description here

So if $A$ and $B$ have 5 friends in common it is slightly more likely they are friends, than they are not.

This is just a rough calculations that ignores several effects.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.