Why Your Friends Have More Friends Than You Do

The big question of this module. Why do your friends have more friends than you do?

This module is built on one number — a node’s degree, the count of edges touching it. From that single count come two counting rules you will reuse for the rest of the course, a way of drawing degree distributions that does not mislead you, and one genuinely surprising result: in every network, the average friend is better connected than the average person. Along the way we meet degree bias, heavy tails, and what they mean for robustness, spreading, and targeted interventions.

Count the Lines That Touch You

A node’s degree is the number of edges touching it. Here we focus on why that simple count matters.

At the level of an individual node, degree measures visibility and influence: high-degree nodes see and can spread information (or infection) quickly; low-degree nodes have limited reach. At the level of a network, the collection of degrees reveals how centralized or evenly distributed connectivity is — and that shape drives many collective behaviors.

Figure 1: A small example graph — node degrees are shown as labels

The tiny graph above makes the point visually: node A has degree 3 (it connects to three nodes) while B, C, and D each have degree 1. That asymmetry — one hub (a node with far more edges than the average node) surrounded by three leaves (nodes with exactly one edge) — is common in real networks and underlies many of the phenomena we study.

Every Edge Has Two Ends — and Two Facts Follow

Before moving on, two counting facts fall straight out of the definition of degree. They look like trivia and are used constantly.

Count the degrees of every node and add them up. Each edge has two endpoints, so each edge gets counted exactly twice — once from each end. Therefore

\sum_{i=1}^N k_i = 2M

where N is the number of nodes and M is the number of edges. Equivalently, the average degree is \langle k \rangle = 2M/N. The angle brackets \langle \cdot \rangle are read “average over all nodes”, and we will use them for the rest of the course. In the four-node graph above, 3 + 1 + 1 + 1 = 6 = 2 \times 3, and \langle k \rangle = 6/4 = 1.5.

This is why 2M keeps appearing in formulas throughout the course (modularity in Module 5, the stationary distribution of a random walk in Module 7): it is just “the total number of edge endpoints.”

A second fact follows immediately. The left side, \sum_i k_i, equals 2M and is therefore even. Split the sum into even-degree nodes and odd-degree nodes. The even-degree part is even. So the odd-degree part must be even too — and a sum of odd numbers is even only when there is an even number of them. This is the handshaking lemma: in any network, the number of nodes with odd degree is even.

The name comes from the party version: if everyone reports how many hands they shook, the number of people reporting an odd count must be even. It is also the hidden reason Euler’s condition in Module 1 allows zero or two odd-degree nodes and never one — one is arithmetically impossible.

How Common Is Each Degree?

Shift your attention from single nodes to the whole network by asking: how common is each degree? The degree distribution answers that question. Write p(k) for the fraction of nodes whose degree is exactly k:

p(k) = \frac{\text{number of nodes with degree } k}{N}

In the four-node graph above, three of the four nodes have degree 1 and one has degree 3, so p(1) = 3/4, p(3) = 1/4, and p(k) = 0 for every other k. That whole list of fractions — one number per degree — is the degree distribution. Because degree is a whole number, p(k) is a probability mass function: a fraction of nodes sitting at each degree, not a curve you integrate.

Reading this distribution quickly tells you whether connectivity is evenly spread or concentrated in a few nodes. Why does that summary matter in practice? Because the distribution shapes how networks behave, as we have already seen in previous modules:

• Robustness vs. fragility — In many real networks a few nodes have enormously more edges than the rest, with a long thin stretch of intermediate degrees in between. Such a distribution is called heavy-tailed (you will also see fat-tailed and degree-heterogeneous; all three name the same picture). These networks tolerate random node loss, because a random removal almost always hits a low-degree node, but they are fragile to targeted hub removal, which can fragment them (Module 3).

• Small-world effects — If a few hubs dominate the degree distribution, they act as shortcuts that dramatically reduce distances between nodes (Module 2).

We will add an additional interesting example, called the Friendship Paradox, in the next section.

Why Your Friends Are More Popular Than You Are

The Friendship Paradox (Feld 1991) states that your friends have more friends than you do on average. This is not an insult — it is a statistical consequence of how connections are counted in most social networks. This counterintuitive phenomenon emerges from the mathematical properties of networks and has profound implications for how we understand social structures, information flow, and even public health interventions.

At its core, the Friendship Paradox reveals a fundamental asymmetry in social networks: high-degree nodes (popular individuals) get counted as somebody’s friend many times over, while low-degree nodes are counted rarely. This creates a sampling bias: the average degree of a randomly chosen friend comes out higher than the average degree of a randomly chosen person.

Figure 2: Friendship paradox example — node labels show degrees

The network diagram above illustrates the Friendship Paradox with a simple four-node network. The average degree in this network is (1+3+1+1)/4 = 1.5, but when we look at the average degree of each person’s friends, we get a different story.

Let us list all the friendship ties in adjacency list format, along with the degree of each node in parentheses:

• Bob: Alex (1), Carol (1), David (1)
• Alex: Bob (3)
• Carol: Bob (3)
• David: Bob (3)

Now, let’s compute the average degree of a friend. There are six entries in that list — one per (person, friend) pair, which is also the number of edge endpoints, 2M = 6:

\frac{\overbrace{1 + 1 + 1}^{\text{Bob's friends}} + \overbrace{3 + 3 + 3}^{\text{The friends of Alex, Carol, and David}}}{\underbrace{6}_{\text{\# of (person, friend) pairs}}} = 2

So the average person in this network has 1.5 friends, while the average friend has 2. That is the friendship paradox.

Read that claim carefully: it compares two averages, not two people. Bob himself does better than his friends — he has 3, each of them has 1. What holds for the network as a whole need not hold for any particular person in it.

Why does the average tilt upward? Because the list above counts Bob three times: Alex, Carol, and David each name him. Alex appears only once, since only Bob names Alex. Every person shows up once per friendship they have, so the well-connected are counted over and over and the poorly-connected barely at all. That systematic over-counting of high-degree nodes is called degree bias.

Counting it is one thing; watching it happen is another. Below, Bob has moved into a slightly bigger village — nine people, eight friendships — and there are two ways to reach into it. Pick a person and all nine are equally likely. Pick a friend and you are not picking a person at all: you are picking one end of one edge, and Bob owns five of the sixteen ends. Step through it, and then turn the dial at the end and try to make the gap go away.

It Is Always True, and the Gap Is Var(k)/⟨k⟩

Two hand-counted examples are suggestive, but is the paradox always true? It is, and the reason is exactly the counting we just did.

Picking a random friend means picking a random edge endpoint, not a random node. A node with degree k owns k of the 2M endpoints, so a person with 10 friends is 10 times as likely to be drawn as a person with 1. Averaging degree over endpoints instead of over nodes therefore over-weights precisely the high-degree nodes — and the average can only move up.

Pushing that counting through gives an exact answer. The algebra is short and lives in the appendix; the result is what you need here.

ImportantThe friendship paradox, exactly

Averaged over the whole network, friends have

\frac{\text{Var}(k)}{\langle k \rangle}

more friends than people do.

Here \text{Var}(k) is the variance of the degrees — the standard measure of how spread out a list of numbers is. It is the average squared distance from the mean: for the degrees 3, 1, 1, 1 with mean 1.5, that is (1.5^2 + 0.5^2 + 0.5^2 + 0.5^2)/4 = 0.75. It equals zero when every node has the same degree, and grows as the degrees become more unequal.

Check the formula against the network above: \text{Var}(k)/\langle k \rangle = 0.75/1.5 = 0.5, and the gap we counted by hand was 2 - 1.5 = 0.5. Exactly.

A variance is never negative, so the gap is never negative: in every network, the average friend is at least as connected as the average person. It vanishes only when \text{Var}(k) = 0 — when everyone has identical degree, which is the ring you were left with at the far-left end of the dial above. And the more unequal the degrees, the wider the gap, which is why it is dramatic in social networks and invisible in a lattice.

The average friend’s degree, \langle k \rangle + \text{Var}(k)/\langle k \rangle, even has a name you have already met: it is the degree heterogeneity \kappa that decides whether a network survives random failure in Module 3. The friendship paradox and network robustness are the same piece of mathematics wearing different clothes.

Try it. Can you build a network in which the paradox is absent — where your friends have exactly as many friends as you? And one where the gap is as large as you can make it? Test your ideas in The friendship paradox, built by hand: ten people, and you click pairs to make and break friendships. It keeps the two averages side by side on one ruler and prints \text{Var}(k)/\langle k \rangle underneath, so you can watch the identity above hold on every network you build.

Beyond fun trivia, the friendship paradox has practical consequences. Most people find that their friends have more friends than they do, not because they are unpopular, but because of this counting bias. The same principle applies elsewhere: in scientific collaboration networks, the average coauthor has more collaborators than the average researcher; on the Web, a page you arrive at by following a random link has more incoming links than a page picked at random.

Vaccinate the Friend, Not the Person

This observation has profound practical consequences, especially in public health and epidemiology. To slow an epidemic you can use the friendship paradox to find better targets, called acquaintance immunization (Cohen et al. 2003), which goes as follows:

1. Pick a random sample of individuals.
2. Ask each to nominate one friend.
3. Vaccinate the nominated friends (who tend to be better connected).

This works because when people nominate a friend, they’re more likely to name someone with many social connections. By targeting these nominated friends, public health officials can reach the most connected individuals in a network without needing to map the entire social structure — which matters, because in exactly the settings where an epidemic must be slowed, nobody has that map.

Can you beat random vaccination by choosing targets this way? Who do you vaccinate? runs the three strategies against each other on the same population of a hundred and twenty: names picked at random, friends nominated by people picked at random, and — as the unreachable best case — the most connected people, which nobody in a real outbreak knows how to find. Slide the number of doses and read the average degree each strategy reaches. Random lands on \langle k \rangle. Nominating a friend lands on \langle k^2 \rangle / \langle k \rangle, the number from the previous section, without anyone ever seeing the network.

Why the Obvious Histogram Lies

The first thing anyone does with a degree distribution is plot it, and the obvious plot is a histogram: degree along the bottom, fraction of nodes up the side. On a heavy-tailed network that plot comes out very nearly blank.

Below is one network’s worth of degrees: N = 5{,}000 nodes and M = 10{,}890 edges, so \langle k \rangle = 2M/N = 4.36. Sixty-two different degrees occur in it, from 2 up to a single node with 227 neighbors. Step through the figure, then drag the dial and watch those sixty-two bars unfold.

Nothing in that figure changed the data. Every bar you saw at the end was already on the page at the start, drawn a fraction of a pixel tall. What changed was the ruler.

NoteWhat a logarithmic axis does

On an ordinary axis, equal widths mean equal additions: 0 to 50 takes the same room as 200 to 250.

On a logarithmic axis, equal widths mean equal multiplications: 1, 10, 100 and 1000 come out equally spaced, because each is ten times the one before.

So a tick labelled 10^{-3} is not “a little below” 10^{-2} — it is one tenth of it, and on a four-decade axis it gets a full quarter of the height to itself. Put both axes on logarithmic rulers and you have a log–log plot.

A log–log plot earns its keep because a power law becomes a straight line on one. If p(k) \propto k^{-\gamma}, then multiplying k by 100 always divides p(k) by 100^{\gamma}, wherever you start from — a fixed multiplication along the bottom always buys the same fixed multiplication up the side, and that is exactly what a straight line on log rulers means.

The slope of that line is -\gamma, and you can read it off the figure with two fingers. The dashed line is p(k) = 2.93\,k^{-2.5}, the law these 5,000 degrees were drawn from. Walk from k = 2 to k = 200 — a factor of 100 to the right — and it falls from 0.52 to 0.0000052, a factor of 100{,}000. And 100^{2.5} = 10^5. A steeper slope (larger \gamma) means hubs are rarer; a shallower one means more of them.

Many real networks — biological, technical, social — have degree distributions that look like this, and that recurrence is one of the foundational observations of network science.

A straight line on a log-log plot is not, by itself, proof of a power law. A mixture of Poisson distributions, or a lognormal, can look just as straight over the range of degrees you actually observe. Whether the power law is a good model for real-world networks is actively contested (Artico et al. 2020; Holme 2019; Voitalov et al. 2019; Broido and Clauset 2019), and settling it for a given network requires a statistical test, not a visual inspection.

There is also one thing the log rulers cannot fix, and the last step of the figure names it. A histogram of N nodes cannot draw a fraction smaller than 1/N: a bin holding a single person reads 1/5000 = 0.0002 whether that person has 41 friends or 227. So the whole right-hand side collapses onto one horizontal shelf, broken by gaps where a degree happened to draw nobody at all. That shelf is not a property of the network — it is the resolution limit of the instrument, which is why the tail of a p(k) plot should never be fitted by eye. The usual repair is to stop asking “how many nodes have degree exactly k?” and ask instead “how many have degree more than k?” That is the complementary cumulative distribution function (CCDF):

\text{CCDF}(k) = P(k' > k) = \sum_{k'=k+1}^\infty p(k')

CCDF represents the fraction of nodes with degree greater than k, or equivalently, the fraction of nodes that survive the degree cutoff k. It is also known as the survival function of the degree distribution. For a side-by-side comparison of the CCDF and the plain histogram, see Figure 3 of Newman (2005).

The CCDF of the same 5,000 degrees, on the same log rulers. Every node is counted at every k below its own degree, so the curve only ever goes down — and the picket fence is gone. There are no bins here to fall empty, and nothing lands on the 1/5000 floor until the single largest node. Read the slope off the dashed law with two fingers: from k = 10 to k = 100 it falls from 0.057 to 0.0019, a factor of about 30, and log₁₀30 = 1.47 — a slope of about −1.5, which is the next section's point.

A nice feature of the CCDF compared to a histogram of p(k) is that it does not require any binning of the data. To draw the histogram of a heavy tail you must group degrees into bins, and the shape you see depends on the bin width you chose. The CCDF has no bins to choose.

There is a related function, the cumulative distribution function (CDF): the fraction of nodes with degree less than or equal to k, i.e. 1 - \text{CCDF}(k). For heavy-tailed networks the CCDF is the one to plot, because the CDF squeezes the whole interesting tail into a flat line just below 1.

The CCDF Slope Is 1 − γ, Not −γ

For networks whose degree distribution follows a power law, p(k) \propto k^{-\gamma}, the CCDF offers a direct path to estimating the exponent \gamma — provided you do not misread the slope.

Adding up a power-law tail leaves a power law behind, but with the exponent reduced by one:

P(k' > k) \propto k^{-(\gamma - 1)}

Take logarithms of both sides and you get a straight line whose slope is -(\gamma - 1) = 1 - \gamma. The one-paragraph calculation behind this is in the appendix.

You can see the shift happen in the two figures above. Read both slopes off the dashed line, which is the law itself and not a sample of it. In the histogram it falls a factor of 10^5 across a factor of 100 in k: slope -2.5, which is -\gamma. In the CCDF of the very same degrees it falls a factor of 30 across a factor of 10 in k: since \log_{10} 30 \approx 1.47, that is a slope of about -1.5, which is 1 - \gamma. The two slopes differ by exactly one, and the CCDF is the shallower of the two. (Measure the purple staircase over that same stretch instead — 279 nodes have more than 10 friends, 6 have more than 100 — and you get a factor of about 46, not 30. That is not an error in the figure: 5,000 draws are a sample of the law, not the law, and reading a slope off one short window of one sample is a poor way to estimate an exponent. It is good enough to tell -1.5 from -2.5, which is all this section is asking you to do.)

ImportantDo not lose the −1

On a log-log plot, the slope of the CCDF is 1 - \gamma, not -\gamma.

If you measure a CCDF slope of -1.3, the degree exponent is \gamma = 2.3, not 1.3 (since -1.3 = 1 - 2.3). Forgetting the shift is the most common way to report a wrong exponent.

Hubs Come from Growth Plus “the Rich Get Richer”

We have described heavy-tailed degree distributions but not explained them. Why should any network develop hubs at all? A random network does not: wire N nodes at random and you get a Poisson degree distribution, in which almost every node sits within a few edges of the average and the chance of anyone having ten times the average degree is essentially nil — no hubs worth the name.

The classic answer is the Barabási-Albert model (Barabási and Albert 1999), which needs only two ingredients.

1. Growth. The network is not fixed. Nodes arrive one at a time, each bringing m edges.
2. Preferential attachment. A new node does not choose its neighbors uniformly. It attaches to an existing node i with probability proportional to that node’s current degree:

\Pi(k_i) = \frac{k_i}{\sum_j k_j}.

That is the whole model: the rich get richer. A node that is already well connected is more likely to gain the next edge, which makes it still more attractive, and so on. Nodes that arrive early have more time to accumulate edges, so age and degree end up correlated.

The consequence — which you can verify by simulation before believing any derivation — is a power-law degree distribution with \gamma = 3.

Neither ingredient suffices alone. Growth with uniform attachment gives an exponential degree distribution, not a power law. Preferential attachment on a fixed set of nodes eventually connects everything to everything. It is the combination that produces hubs.

Preferential attachment is the most famous explanation, not the only one, and probably not the right one everywhere. Copying models (a new paper cites the references of a paper it read), fitness models (some nodes are intrinsically more attractive regardless of degree), and optimization models all produce heavy tails too. In Module 8 we will meet another: nodes trading off popularity against similarity in an underlying hyperbolic geometry, where preferential attachment turns out to be an emergent consequence rather than a primitive rule.

Two Networks with the Same Degrees Can Behave Nothing Alike

The degree distribution says how many hubs there are. It says nothing about where they sit relative to each other — and two networks with identical degree distributions can behave completely differently depending on the answer.

Ask: when you follow an edge, does a high-degree node tend to find another high-degree node on the other end, or a low-degree one?

Below are three networks that are identical in every way this module has measured so far. Each has twelve nodes and sixteen edges; each has exactly four nodes of degree 4 and eight of degree 2; so all three have the same \langle k \rangle = 32/12 = 2.67, the same p(k), the same \text{Var}(k), the same friendship-paradox gap. The only difference is who is wired to whom.

assortative
r = +0.5

6×(4,4)  4×(4,2)  6×(2,2)

The four 4s are wired to each other; the 2s are strung together in two chains.

neutral
r = 0

4×(4,4)  8×(4,2)  4×(2,2)

Half of each 4's edges go to other 4s, half to 2s — no preference either way.

disassortative
r = −1

0×(4,4)  16×(4,2)  0×(2,2)

No 4 touches another 4. Every single edge joins a 4 to a 2.

The same twelve nodes and the same twelve degrees, wired three ways. Under each drawing is its list of sixteen edges written as pairs of degrees — that list is the whole of what r measures.

The number under each drawing is the degree assortativity coefficient r. To see where it comes from, do what the tallies do: walk over every edge and write down the pair (degree at this end, degree at that end). That gives a list of sixteen pairs. Then ask the question a correlation coefficient always asks — when the first number of a pair is above average, is the second one too? The answer is squeezed into a single number between -1 and +1: +1 means always, -1 means never, and 0 means knowing one end tells you nothing about the other.

The right-hand picture makes -1 concrete. Every one of its sixteen edges is a 4 paired with a 2; big never goes with big, so the correlation is as negative as a correlation can be. The left-hand picture has six 4–4 edges and six 2–2 edges against only four mixed ones, so big usually does go with big, and r comes out positive. The middle one splits the difference exactly.

Because all three share a degree sequence, the arithmetic collapses to something you can do in your head. With these degrees,

r = \frac{1}{16}\sum_{\text{edges}} j\,k \; - \; 9,

where j and k are the degrees at the two ends of an edge. Read the products straight off the tallies: 6(16) + 4(8) + 6(4) = 152, and 152/16 - 9 = 0.5. The middle wiring gives 4(16) + 8(8) + 4(4) = 144 and 144/16 - 9 = 0; the right-hand one gives 16(8) = 128 and 128/16 - 9 = -1. Where the 16 and the 9 come from — and why they depend on the degree sequence alone, so that only \sum j\,k can move — is worked out in the appendix.

So the vocabulary:

• Assortative (r > 0): hubs connect to hubs, and a densely connected core forms. Social networks are typically assortative — popular people know popular people.
• Disassortative (r < 0): hubs connect to peripheral nodes. Technological and biological networks are typically disassortative — a big router serves many small ones, a hub protein binds many specific partners.
• Neutral (r \approx 0): no preference either way. The configuration model, which rewires edges at random while preserving degrees, is neutral by construction.

Why care? Because degree correlations change everything downstream:

• Robustness. An assortative network has a hub core that holds together under attack; a disassortative one fragments faster once its hubs go, since the periphery hangs off them and nothing else.
• Spreading. Assortativity concentrates an epidemic in the hub core, giving a lower epidemic threshold but slower escape to the periphery.
• Our theory’s assumptions. The Molloy-Reed derivation in Module 3’s appendix assumes a node reached by an edge has \kappa - 1 onward edges on average. That is a neutral-network statement. When degrees are correlated, the branching factor changes and the predicted threshold shifts.

What You Can Now Do

• Compute a node’s degree, the degree sum 2M, and the degree distribution p(k) of a small network by hand.
• Say why the average friend is better connected than the average person in every network — and predict the size of the gap from \text{Var}(k)/\langle k \rangle.
• Choose between a linear histogram, a log-log histogram, and a CCDF, and read a power-law exponent off a CCDF slope without losing the -1.
• Say what a logarithmic axis does to a plot, and why the flat shelf at the right of a p(k) log-log plot is the histogram’s resolution limit rather than the network’s shape.
• Explain acquaintance immunization to someone who has never heard of a network.
• Wire one degree sequence assortatively and disassortatively, and compute the resulting r from the list of (degree, degree) pairs along the edges.

Next: put it into code in the hands-on notebook, practice in the exercises, or read the two derivations in the appendix.

References

Artico, Igor, I Smolyarenko, Veronica Vinciotti, and Ernst C Wit. 2020. “How Rare Are Power-Law Networks Really?” Proceedings of the Royal Society A 476 (2241): 20190742.

Barabási, Albert-László, and Réka Albert. 1999. “Emergence of Scaling in Random Networks.” Science 286 (5439): 509–12. https://doi.org/10.1126/science.286.5439.509.

Broido, Anna D., and Aaron Clauset. 2019. “Scale-free networks are rare.” Nature Communications 10 (1). https://doi.org/10.1038/s41467-019-08746-5.

Cohen, Reuven, Shlomo Havlin, and Daniel ben-Avraham. 2003. “Efficient Immunization Strategies for Computer Networks and Populations.” Physical Review Letters 91 (24). https://doi.org/10.1103/physrevlett.91.247901.

Feld, Scott L. 1991. “Why your friends have more friends than you do.” American Journal of Sociology 96 (6): 1464–77.

Holme, Petter. 2019. “Rare and Everywhere: Perspectives on Scale-Free Networks.” Nature Communications 10 (1): 1016.

Newman, Mark EJ. 2005. “Power Laws, Pareto Distributions and Zipf’s Law.” Contemporary Physics 46 (5): 323–51.

Voitalov, Ivan, Pim Van Der Hoorn, Remco Van Der Hofstad, and Dmitri Krioukov. 2019. “Scale-Free Networks Well Done.” Physical Review Research 1 (3): 033034.