Hacker News Reader

Comment by aidenn0 | Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com