Hacker News Reader

Comment by notenoughbeans | Hacker News Reader

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?

View on HN

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.

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.

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.

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

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.

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.

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!"

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.

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.

Reply on news.ycombinator.com