Friendship paradox disappears under degree biased network sampling

This paper demonstrates that degree-biased sampling in undirected graphs eliminates the friendship paradox by ensuring the expected degree of sampled vertices equals the expected degree of their neighbors, a condition equivalent to the stationary state of a random walk or the conservation of total flow.

The Gist

The Big Idea: Why Your Friends Usually Have More Friends Than You (But Not Always)

You've probably heard of the Friendship Paradox. It's that funny feeling you get when you look at your friends' social media and think, "Wow, everyone I know seems more popular, happier, or more successful than I am."

Mathematically, this is true for most people in a standard social network. If you pick a random person, their friends will, on average, have more friends than they do. This happens because popular people (with many friends) show up in many people's friend lists, while unpopular people (with few friends) show up in very few. So, when you look at your friends, you are statistically more likely to be looking at the "popular" ones.

This paper asks a simple question: What if we change the way we look at the network? What if we stop picking people at random and instead pick them based on how popular they are?

The author, Wojciech Roga, discovered a surprising twist: If you sample people based on their popularity (degree), the paradox disappears. In this specific scenario, your friends have the exact same number of friends as you do, on average.

---

The Analogy: The "Influencer" vs. The "Random Tourist"

To understand this, let's imagine a giant party (the network) where people are shaking hands (edges).

1. The Standard View (The Random Tourist)

Imagine you are a tourist walking into this party. You close your eyes and point to a random person. Let's call them Bob.

• Bob has 3 friends at the party.
• You ask Bob, "Who are your friends?"
• Because Bob is connected to 3 people, he introduces you to them.
• The Paradox: It turns out that the people Bob introduced you to are likely to be the "super-connectors" of the party (people with 50 or 100 friends). Why? Because those super-connectors are friends with everyone, including Bob.
• Result: You feel like Bob's friends are way more popular than Bob. The "average friend" is more popular than the "average person."

2. The New View (The Degree-Biased Sampler)

Now, imagine a different way to pick someone. Instead of picking a random person, imagine a robot that picks people proportional to how many hands they are shaking.

• If Bob is shaking 3 hands, he has a 3% chance of being picked.
• If Sarah is shaking 100 hands, she has a much more chance of being picked (relative to Bob).
• The robot picks Sarah.
• Sarah is a super-connector. She has 100 friends.
• You ask Sarah, "Who are your friends?"
• She introduces you to her 100 friends.
• The Twist: Because Sarah was picked because she is so popular, her friends are less popular. But the number of less popular people is large, so picking randomly one of them is also probable, then their friends are likely more popular. And here is the magic: The math balances out perfectly.

In this specific "degree-biased" world, the average popularity of the person you picked (Sarah or others) is exactly equal to the average popularity of the people she introduced you to. The "paradox" vanishes. The "friends of friends" are no more popular than the "friends" themselves.

---

The Three Ways to See the Same Thing

The paper proves this using three different "lenses" or metaphors. They all lead to the same conclusion:

1. The "Flow" Analogy (Water in Pipes)

Imagine the network is a system of pipes. The "flow" is the difference between how many friends you have and how many your friends have.

• If you have fewer friends than your friends, water flows out of you.
• If you have more, water flows in.
• The paper shows that if you look at the whole network, the total water flowing in equals the total water flowing out. The system is perfectly balanced. There is no net "imbalance" or bias.

2. The "Random Walker" (The Drunkard's Walk)

Imagine a person wandering through the party, moving from one person to a random friend, over and over again.

• If they wander long enough, they will spend more time hanging out with the popular people (because there are more paths leading to them).
• The paper uses the argument that in this "steady state" of wandering, the average number of friends the walker has right now is exactly the same as the average number of friends they will have in the next step.
• The "now" and the "next" are perfectly matched. The paradox doesn't exist here.

3. The "Crawling Robot"

Imagine a robot crawling the internet (or the party).

• If the robot picks pages/people completely at random, it sees the paradox (it thinks everyone else is more popular).
• But if the robot is programmed to visit pages/people in proportion to how many links they have, it sees a balanced world. It realizes, "Hey, the people I'm visiting are just as connected as the people they link to."

---

Why Does This Matter?

You might ask, "Why should I care if the math balances out in a weird sampling method?"

The paper argues that how we measure things changes what we see.

• The Bias: The Friendship Paradox isn't a "law of nature" that says you are uncool. It's a statistical artifact caused by how we usually look at data (picking random people).
• The Warning: If researchers, doctors, or financial analysts use the wrong sampling method, they might get "Majority Illusions." They might think a behavior is common or a risk is high just because they are looking at the "popular" nodes too much.
• The Solution: By understanding that the paradox disappears under degree-biased sampling, we realize that the "paradox" is actually a sign of systematic error in our measurement. It tells us that if we want to see the "true" average, we need to be careful about how we pick our sample.

The Takeaway

The Friendship Paradox is real, but it's a trick of the light caused by how we count. If you change the rules of the game to count people based on their popularity, the trick disappears, and the numbers balance out perfectly.

In short: The reason your friends seem more popular than you is that you are looking at the network through a lens that magnifies the popular people. If you adjust the lens, the distortion goes away.

Technical Summary

1. Problem Statement

The Friendship Paradox is a well-established phenomenon in social network theory stating that, on average, individuals have fewer friends than their friends do. Mathematically, the expected degree of a uniformly sampled vertex is strictly less than the average degree of its neighbors.

• The Issue: This paradox arises from a statistical bias inherent in uniform sampling. When individuals are sampled uniformly, those with high degrees (popular nodes) are underrepresented in the sample of "individuals" but overrepresented in the sample of "neighbors" (since high-degree nodes appear as neighbors to many people).
• Consequences: This bias leads to "majority illusions," systematic errors in medical surveys, distorted perceptions in finance, and skewed opinions on social norms.
• The Gap: While the paradox is well-documented under uniform sampling, the paper investigates whether this phenomenon persists under degree-biased sampling (where the probability of selecting a node is proportional to its degree). The author posits that under this specific sampling method, the paradox should vanish.

2. Methodology

The paper employs a combination of rigorous mathematical proofs, theoretical equivalence mapping, and numerical simulations.

A. Mathematical Formulation

The author defines the local imbalance for a vertex $i$ as the difference between the average degree of its neighbors and its own degree:
$$\text{Imbalance}_i = \left( \frac{\sum_{j \in S_i} k_j}{k_i} \right) - k_i$$
where $k_i$ is the degree of vertex $i$, and $S_i$ is the set of its neighbors.

The core analysis calculates the expected value of this imbalance under degree-biased sampling. In this sampling scheme, the probability $p_i$ of selecting vertex $i$ is proportional to its degree:
$$p_i = \frac{k_i}{2|E|}$$
where $|E|$ is the total number of edges.

B. Theoretical Equivalence

The paper establishes that the disappearance of the paradox under degree-biased sampling is mathematically equivalent to two fundamental concepts in graph theory:

1. Stationary State of Random Walks: The probability distribution of a random walker on an undirected graph converges to a stationary state where $p_i \propto k_i$.
2. Conservation of Flow: The net flow (divergence) defined by degree differences across the network sums to zero.

C. Simulations

To validate the theoretical findings, the author simulated random walks on three distinct graph structures:

1. Erdős–Rényi Graph: A random graph with $n=1000$ nodes and connection probability $p=0.05$.
2. Zachary's Karate Club: A small-world social network with 34 nodes and 78 edges.
3. SNAP Facebook Dataset: A large-scale real-world network with 4,039 nodes and 88,234 edges.

In these simulations, the "local imbalance" was calculated at each step of the random walk, and the running average was tracked to observe convergence.

3. Key Contributions

A. Proof of the Identity

The central contribution is the proof that under degree-biased sampling, the expected imbalance is exactly zero.

• Derivation: The expected value is calculated as $\sum_i p_i (\text{Imbalance}_i)$.
• Key Identity: The proof relies on the identity $\sum_i \sum_{j \in S_i} k_j = \sum_i k_i^2$. This identity holds because in a double summation over neighbors, a vertex with degree $k_i$ appears as a neighbor exactly $k_i$ times.
• Result:
  $$E[\text{Imbalance}] = \sum_i \frac{k_i}{2|E|} \left( \frac{\sum_{j \in S_i} k_j}{k_i} - k_i \right) = \frac{1}{2|E|} \left( \sum_i \sum_{j \in S_i} k_j - \sum_i k_i^2 \right) = 0$$
  Consequently, the expected degree of a sampled vertex equals the expected degree of its neighbors.

B. Equivalence to Random Walk Stationarity

The paper clarifies that the "Friendship Paradox" is essentially a result of comparing a uniform distribution (random node selection) against the stationary distribution of a random walk (degree-biased selection).

• In a random walk, the walker is more likely to be at a high-degree node.
• The expected degree of the current node ($d_{now}$) and the next node ($d_{next}$) are identical in the stationary state.
• Therefore, $d_{next} - d_{now} = 0$, meaning the "friends have more friends" effect disappears when viewed through the lens of a random walker.

C. Flow Conservation Interpretation

The author introduces a novel perspective viewing the paradox through flow conservation. By defining flow between nodes $i$ and $j$ as $\phi(i \to j) = k_i - k_j$, the total divergence in the network sums to zero. This frames the paradox not just as a statistical anomaly, but as a violation of flow conservation under uniform sampling, which is restored under degree-biased sampling.

4. Results

• Theoretical: The paper rigorously proves that the friendship paradox is an artifact of uniform sampling. Under degree-biased sampling, the inequality $E[k_{neighbor}] > E[k_{node}]$ becomes an equality.
• Simulation: The numerical experiments confirmed the theoretical prediction.
  • In all three graph types (Random, Karate Club, Facebook), the running average of the local imbalance converged to zero.
  • The Standard Error of the Mean (SEM) converged to a constant value dependent on the network structure, but the mean itself remained at zero.
  • Convergence to zero occurred relatively quickly, often before the random walker had explored the entire graph.

5. Significance and Implications

• Clarification of Sampling Bias: The paper explicitly defines the conditions under which the friendship paradox exists (uniform sampling) and where it vanishes (degree-biased sampling). This is crucial for researchers designing network surveys or algorithms.
• Correction of Systematic Errors: It highlights that many "paradoxical" observations in social networks (e.g., happiness, citation counts) are artifacts of the sampling method. If data is collected via methods that inadvertently mimic degree-biased sampling (like following links), the paradox may not appear, leading to different interpretations of network dynamics.
• Network Crawling and Algorithms: The findings are relevant for "internet crawling robots" or network crawlers. A crawler that follows links (random walk) naturally samples nodes with probability proportional to their degree. Such a crawler will not observe the friendship paradox; it will see a balance between a node's degree and its neighbors' degrees.
• Theoretical Unification: By linking the paradox to the stationary state of random walks and flow conservation, the paper unifies social network statistics with fundamental principles of statistical mechanics and graph theory.

In conclusion, Roga demonstrates that the friendship paradox is not an intrinsic property of the network topology itself, but rather a consequence of the sampling distribution. When the sampling distribution matches the natural stationary distribution of a random walk (degree-biased), the paradox disappears, revealing a fundamental symmetry in the network's structure.