A friendly introduction to the Friendship Paradox (2021) | Hacker News Reader

A friendly introduction to the Friendship Paradox (2021)

scribe.citizen4.eu

101 pointstriyambakam59 comments

On the bright side, the people you are not friends with have fewer friends than you do.

This answer made me laugh so much harder than it should have.

I'm thanking the art of selective statistics for this little highlight in my day!

How to Lie with Statistics by Darrel Huff is really good satire https://archive.org/details/HowToLieWithStatistics_201608

From page 32 in the chapter on how to "choose the right average"

> You and your partners have paid yourselves $11,000 each in salaries. You find there are profits for the year of $45,000 to be divided equally among you. How are you going to describe this? To make it easy to understand, you put it in the form of averages. Since all the employees are doing about the same kind of work for similar pay, it won’t make much difference whether you use a mean or a median.

> This is what you come out with:

> Average wage of employees $ 2,200

> Average salary and profit of owners .... 26,000

> That looks terrible, doesn’t it? Let’s try it another way

> Take $30,000 of the profits and distribute it among the three partners as bonuses. And this time when you aver- age up the wages, include yourself and your partners. And be sure to use a mean.

This is the Friendship Paradox of graph theory:

https://en.wikipedia.org/wiki/Friendship_paradox

Oh—I think this is just another Pareto distribution: a small minority of people have the majority of friends (probably something like the top 20% of people have 80% of the friends).

You're probably friends with several people in that top 20% because they know a lot of people. The average number of friends your friends have including the outliers is going to be higher than the number of friends you have.

I don't think that's a good representation of what they're saying. They showed that the average number of friends that your friends will have is mu+std/mu, so if the distribution is anything but perfectly homogeneous then you can expect that your friends will have more friends than you. It doesn't need to be super skewed with some people knowing everybody, any variation _at all_ leads to this, no need for outliers.

> any variation _at all_ leads to this, no need for outliers.

A lot of dismissals miss this in talk about super popular celebrities. It just requires that some people have more friends than other people. The people who have more friends are more likely to be friends with you than the people who have fewer friends [edit: even if "more friends" means five friends and "fewer friends" means four friends.] That's it. It isn't about outliers pulling up means.

Their description seems like a fairly good take. The main idea is that in graph you are more likely to be connected to an outlier when it comes to connexions by virtue of them being more connected and these outliers skew the average. Of course you might yourself be the outlier.

If you think about it, this is not far from saying that: if you know a distribution is non homogenous with a limited number of elements skewed - like say a normal distribution - and pick an element at random, it is more likely to be average than exceptional which is pretty trivial when you think about it.

How would the results differ if you looked at median instead of average? It seems like median would probably be about the same in many cases, when talking about # of friends.

If my friends have more friends than me, do their friends have more friends than them? And if I'm my friend's friend, am I not included in their friends that have more friends?

No, because the statement is about averages (normal people), not the outliers (celebrities) that average people are friends with.

Celebrities are a much less counterintuitive example. The effect is quite obvious if you look at asymmetric relations like being aware of a famous person (or, say, Twitter follows). It's pretty obvious that a lot more people know Justin Bieber or Barack Obama by name than the pop star or U.S. President know by name.

What's slightly less intuitive about the friendship paradox is that this also tends to be true with symmetric relations.

The real title and the principle are "your friends more likely have more friends than you". It's not true in every case, and obviously not on both sides of a reciprocal pair.

Exactly. The heavy lifting in this case is being done by the phrase “on average.” They could have just said “a small number of people have WAY more friends than usual.”

> They could have just said “a small number of people have WAY more friends than usual.”

They do say that, but that's a way to explain why the friendship paradox is true. It's not some trivially equivalent statement. If the statements were trivially equivalent, then people wouldn't be complaining that one is counterintuitive while the other is obvious. The whole point is that one fact is a counterintuitive result of another more intuitive fact.

Whenever you start talking about averages, you have to be careful. The average nuclear family having 2.5 kids, for example.

More like 2.499 once you consider the mass defect when you fission the third child.

If you select a random person, and then select a random friend of that person, most of the time, the latter has more friends.

This is because friendship graphs tend to have a small number of highly-connected nodes and a large number of less-connected nodes. Therefore most of the connections are between a less-connected node and a more connected node. So, if you just select a random node, you are highly likely to select a less-connected node, which also means that if you follow a random connection from that node, you are likely to reach a highly connected node.

So to answer your original question: No.

Thanks for the succinct summary, I understand it better than the featured article.

That summary is still confusing to me. Rather, "If you select a random person, and then average how many friends all of their friends have, most of the time the latter will be higher." I don't think it holds nearly as strongly in the case of selecting a single neighbor. (I can't say it doesn't hold.)

Let's simplify this a bit. Divide people into "lots of friends" (L) and "few friends" (F). Most nodes are F, most edges are F<->L.

Therefore if you randomly select a person, you probably end up with an F. Since most edges are F<->L, following an edge from an F is likely to get you to an L.

I could see a plurality of edges are actually F<->F, though? Such that most people you connect with are connected with everyone else you also connect with. You will just have a few people in any large group that are hyper connected outside of that group. Such that, as likely, you have the same number of friends as any given friend. Similarly, though, most likely you will have fewer friends than the average of all of your friends.

Even in that case you increase your chances of selecting an L by using this algorithm as long as (number of F nodes) >> (number of L nodes).

Do you, though? I think I can agree that you are most likely to select an F with your random initial choice. And since the degree of your average L is >> the degree of your average F, it just takes a single L in a highly connected group of Fs to make the general statement true. As such, if you pick an F in a connected group and make a single jump, you are probably not on an L, but another connected F.

This would be similar to how famous you are compared to your friends. On average, your friends are more famous than you. But only because you likely have a few much more famous friends. Such that, a random choice of your friends is not likely to be one of these few. (Agreed that it is higher than that initial selection. But would still be low.)

Edit: Reading your post, I think I can easily agree that you /increase/ your chances of selecting an L by taking a single hop from a random node. I'm more asking if it is better than 50% at that point. Seems like it shouldn't be.

Yes, if the plurality of nodes are F<->F and F >> L then the odds are less than 50%.

In a simple case, consider a subgraph with one L connected to all F, and every F is connected to 2 Fs (in addition to their connection to L). You have a 1/3 chance of selecting the L in this case (but since there must be at least 3 Fs to draw this graph, you have no better than a 1/4 chance of selecting an L at random and thus you still find more connected nodes on average by using this algorithm).

[edit]

The above example was too simple as the majority of edges do not contain an L, and in fact you don't improve your odds in the 4-node case (they are the same in that case, but at 5 and more nodes you do). It still shows how a small number of highly connected nodes can dominate rather quickly though.

Cool, that matches my current intuition for this. I'm curious on what the numbers say in realistic social networks. My gut call was that the distinction between "most of your friends have more friends than you do" and "your friends have more friends, on average," is one that is confusing to most people. Myself included.

The result actually doesn't depend on any special properties of social graphs. It works for any graph that has a component with non-constant number of edges per node.

IIRC it has to be high variance, not just non constant.

Indeed. Say you have a graph where nodes have different amounts of connections. You pick a random node, and from there, go on a random walk, always picking a random edge to another random "friend" node. After some amount of jumps, it's more likely that you've ended up on a node which has a higher than average amount of connections.

Well, no, it doesn't work like that. There's already not some guarantee that your friends will have more friends than you do. Obviously some of the people have to be the ones that have lots of friends, and you could very well be one of those people. The point is just that most people aren't those people, so most people who read these articles and check their friend graphs will go "whoa, it's true!"

No their friend's friends do not have more friends than them. Some people have an unusually large amount of friends, what this means practically is that they are more likely to be one of your very few friends, because they touch so many smaller groups, yours included. When they say most people's friends have more friends than them, it's the same very popular people being counted again and again by each unpopular person.

On a sort of related note, men and women have the same average number of sexual partners. Assuming equal numbers of each in the population and only considering heterosexual sex.

Edit: if we consider TFA do our partners have more partners than us on average?

Mean and median are two different things. By definition, mean heterosexual partners are exactly identical but median can vary between men and women.

The average human has 1 testicle and 1 ovary.

On a sort of related note.

The average human also has less than two legs.

Erasure of the third leg community.

Third leg - every photographer's dream.

Yes, but according to the Friendship Paradox _your_ sexual partners are likely to have had more sexual partners than you.

As a mathematician, my immediate reaction was: duh! Of course! Why is this interesting?

The go-to example would be a person having 10 friends, being the only friend for each of them. It's not too hard to generalize from there, or at least to have an intuition.

The interesting part for me was this:

> If there are only enough vaccines for a small fraction of the population, an effective strategy is to vaccinate a random friend of each randomly chosen person.

Oh. Makes sense!

Somehow, something like that didn't occur to me even when the math felt intuitive.

Well, the interesting thing isn't that such graphs exist, so finding an arbitrary graph with this property isn't really relevant.

It's that certain distributions of random graphs, when sampled tend to produce graphs with this property and human social networks are one of them.

True. My comment was to highlight how wrong my initial intuition was.

Looking around, this article[1] by Arun Maiya and Tanya Berger-Wolf explores this in the context of social networks. Fascinating stuff!

[1] https://arxiv.org/pdf/1109.3911.pdf

No, this statement is true for every graph that doesn't have constant degree. It's not really to do with random graphs. Rather it's the fact that a random neighbor of a random node draws from a different distribution than a random node, and the former distribution puts more mass on nodes of higher degree.

Ah, oops, you are correct.

Does this logic extend? What if i reached out to a random friend of a random friend of a random node - basically to degree 3 of the network. Is that better than degree 2 ? If so, then is there a degree where the spreading is optimal ?

This is why I intentionally make close friends.

What if the two people don’t agree they are friends? For some reason I know a lot of people who think they are my friend and claim as such but in my mind they aren’t and I know they tend to talk to me in their self interest.

Just as counter intuitive as that all file compression methods make most of all possible files larger.

Neither of the epidemiology examples makes any sense to me. There seems to be some kind of implicit assumption that people with more friends are more likely to be infected, but that really isn't how friendship works.

This is a good example of why the mean is often unhelpful.

Cousins also have cousins that aren't related to you.

But that one is kind of trivial. Your cousins have parents who aren't related to you.

Colloquially speaking, people have 'uncles' and 'aunts' that they share no blood with.

Indeed. An interesting exercise might be to ask yourself if the friendship paradox applies to cousin relationships (let's limit it to first cousins with zero removal).

The one that throws me is:

If you are a parent (say a father), and DO NOT have a child of the same sex as you (a son in this case), you have broken an unbroken line of parents before you who had a child of the same sex.

Every father that came before you had at least one son that lived to have their own children, and had a son...

It's simple but blows my tiny mind. My mother was quite shocked when she learnt the female line broke with her. :P

Median is sometimes more relevant than mean.

That is why I choose to have zero friends.

404?

Same.

Try reloading a few times. Guessing one of their backends doesn't have the files yet.

'tis the Slashdot hug effect. Pardon, HN DDOS.

Mirrors:

[1] https://archive.ph/nzKWP

[2] https://web.archive.org/web/20221128230655/https://scribe.ci...

Reply on news.ycombinator.com