Scale-free networks and the friendship paradox

Scale-free networks

  • What do degree distributions look like?
    • In many cases, they are really skewed!
    • A few people have many edges, while many have few
  • Why?
    • Rich-get-richer processes (preferential attachment)

Why are they called scale-free?

  • No matter where you zoom in on the distribution, it has the same shape


  • Robust to random failures
  • Outcomes are “unfair”

Friendship paradox

  • Scott Feld (Purdue Sociologist!)
  • On average, your friends have more friends than you do


  • The key idea is that people who are connected to lots of people are more likely to show up in your friend network.
  • You are likely to be friends with people who have lots of friends, because they have lots of friends!
  • This is much more pronounced as the skew of a network changes
  • E.g., the people you follow on Twitter/Instagram are likely much more popular than you



  • In many cases, we can’t see who is most popular
  • Simply choosing a node at random, and then choosing one of their friends will identify a group that is more popular and closer to center
  • Detect outbreaks
  • Focus interventions