[Math] High betweenness but relatively low degree, and its opposite

graph theory

I'm a CS major working on social network analysis and its friends.

In page 15 of this lecture note, two very interesting questions have been asked. Given a social network graph, in which cases would we find nodes with high betweenness but relatively low degree? And, which cases would cause the opposite to happen, that is, high degree but relatively low betweenness? I'm trying to understand this from an intuitive point of view. I'd really appreciate it if someone can shed some light on this.

Added notes:
Betweenness: intuition: how many pairs of nodes would have to go through a particular node in order to reach one another in the minimum number of hops? Check Betweenness centrality in Wikipedia for formal definitions.

Best Answer

One way to have high degree but low betweenness is if almost all of your friends know each other. This is because whenever you are between two other nodes, the shortest path must use two of your friends who are not friends with each other.

One way to have low degree but high betweenness is if your friends each have high degree, and know different people to each other.

Related Question