What is the chance to have a mutual friend with a random person ?

#1
We have a social network say facebook.
We know that it is composed by 500 milion of users.
We know that each user have an average of 135 friend.

Taking a random person, what is the chance that he has a mutual friend with me ?
And how the chance increase if we are not looking for mutual friends with me, but we want to know what is the chance that this random guy have a mutual friend with a set of people composed by N users (so not just me).

Any suggestion ?

Thanks
 

Link

Ninja say what!?!
#2
your question is not as straight forward as you would expect. There's a high amount of correlation seen when dealing with stuff like this. For example, if I were to go to one of your friend's pages and pick a person at random, the probability that the person has a mutual friend with you would be 100% (since I'm picking it off your friend's page, and that friend would be the mutual friend).

Let's say that I don't do that though and that instead, I pick someone from your same school. The chances again of having a mutual friend would be very high because you guys go to the same school.

Now lets say that I pick someone from a rural town in India. The probability of having a mutual friend would be almost 0.

There are techniques to deal with this type of correlation, with some built in assumptions. I doubt you'll want to nor be ready to learn about them though without at least a solid understanding of introductory probability and statistics.

Addressing the problem in its simplest form though, lets say that there is independence among the draws...that you don't have to worry about the correlation. Then this becomes the "same birthday" problem (look it up if you're interested). The probability that a randomly chosen person will have the same friend you do is just 1 minus the probability that the both of you share no friends.
 
#5
Addressing the problem in its simplest form though, lets say that there is independence among the draws...that you don't have to worry about the correlation. Then this becomes the "same birthday" problem (look it up if you're interested). The probability that a randomly chosen person will have the same friend you do is just 1 minus the probability that the both of you share no friends.
This is very interesting, I didn't thought about it before: As the number of set of user increase the chance to find a mutual friend increase as well according to the birthday problem.

mmm how can I use the birthday paradox in my context ?
I want to formulate problem in another way to let you understand better:

I have a little network (say MyNet that is wrapped in Facebook) and I have an huge network ( Facebook), if there are only 2 user in MyNet (apparently with not relationship), what is the chance that exists a mutual friend in Facebook ?
When MyNet grows up say 1000 users, what is the chance that exist a mutual friend of any of 2 in facebook ?
How the chance increase according to the increasing of the MyNet's users ?
The birthday paradox seems to be a good point in this problem
 
#7
I'd hope some of it would be of at least tangential relevance. How 'bout the 'small world' references at the bottom of the link?
It is more relevant to my problem, but it concentrates more to the 6 degree separation rather than give me a solution to my problem
 
#8
I found interesting academic article that are giving me a lot of answers:

https://wiki.vbi.vt.edu/download/at....the-structure-of-growing-social-networks.pdf

I would like to know what do you think about the formula number 1 on page 3. Is the final formula that answer to the question: "What is the chance that two user are friends ? " If yes how can I change the formula to know "what is the chance that two user have a mutual friend ?"

P.S If you follow the link you will see that the site is insecure because it says that it is https instead it's not https ... of course it doesn't matter because you just have to read the pdf file without giving any sensitive information.

What do you think ? Is it the solution to all my problems ?
 
#9
I like to use the 6 degrees of separation in my calculations regarding human networks. Recently at my boarding school we did a mathematical experiment regarding the whole six degrees rule and I was quite amazed. I didn't realize such complex issues can be explained in such a simple manner. Do you guys know about Chrysalis School Montana, it's a boarding school that teaches such things.
 
Last edited: