Granovetter’s argument

In 1973 the sociologist Mark Granovetter published “The Strength of Weak Ties”, one of the most cited papers in social network research. He defined the strength of a tie between two people as a combination of the amount of time they spend together, its emotional intensity, its intimacy (mutual confiding) and the reciprocal services it involves (M. S. Granovetter 1973).

The argument turns on an observation about triangles. If A has strong ties to both B and C, then B and C are likely to have at least a weak tie to each other: A spends a lot of time with both, so they have probably met, and since both resemble A they probably resemble each other. Granovetter called the configuration in which A is strongly tied to B and to C while B and C have no tie at all the “forbidden triad”: not impossible, but rare. A structural conclusion follows: strong ties are rarely bridges. A bridge (more precisely, a “local bridge”) is a tie connecting two people who would otherwise not be linked by any short path. If A–B is a strong tie, A’s other strong-tie friends will probably also know B, so there are other short paths from A to B and A–B is no longer the only channel. The ties that connect different circles tend to be weak ones.

These figures are often cited as evidence that “weak ties are more useful”, but by themselves they show only that weak ties make up the majority of the contacts who helped. There are two possible explanations: each weak tie really is more useful, or there are simply many more weak ties than strong ones. Telling the two apart needed the large-scale data that only appeared decades later (see the second half of this chapter).

Closed triangles and redundant information

Granovetter’s argument can be turned into a quantity that can be computed. For a tie $i$–$j$, the neighbourhood overlap is the number of contacts the two share divided by the total number of their other contacts:

$$O_{ij} = \frac{n_{ij}}{(k_i – 1) + (k_j – 1) – n_{ij}}$$

where $k_i$ and $k_j$ are the two people’s numbers of contacts and $n_{ij}$ the number of shared contacts. If $O_{ij}$ is close to 1, the tie sits inside closed triangles: you know most of the people the other person knows, and what he or she can tell you, you have probably heard already. If $O_{ij}$ is close to 0, the tie is a bridge.

# Bridges, closed triangles and redundant information (Granovetter 1973;
# Onnela et al. 2007). Synthetic network: 30 groups of 20 people, dense inside
# each group (tie probability 0.4) plus 150 random ties between groups.
# Neighbourhood overlap of tie i-j: shared contacts / (k_i - 1 + k_j - 1 - shared).
# "Novelty" of j for i: share of j's other contacts that i does not know.
# Then ties are removed in order of overlap (lowest first or highest first)
# and the largest connected component is tracked. Illustrative parameters.
import random
rng = random.Random(2)
G, S, P_IN, N_BETWEEN = 30, 20, 0.4, 150
N = G * S
nb = [set() for _ in range(N)]
for g in range(G):
    m = range(g * S, (g + 1) * S)
    for a in m:
        for b in m:
            if a < b and rng.random() < P_IN:
                nb[a].add(b); nb[b].add(a)
added = 0
while added < N_BETWEEN:
    a, b = rng.randrange(N), rng.randrange(N)
    if a // S != b // S and b not in nb[a]:
        nb[a].add(b); nb[b].add(a); added += 1
edges = [(a, b) for a in range(N) for b in nb[a] if a < b]

def overlap(a, b):
    sh = len(nb[a] & nb[b]); den = len(nb[a]) - 1 + len(nb[b]) - 1 - sh
    return sh / den if den > 0 else 0.0

def novelty(a, b):          # share of b's other contacts unknown to a
    others = nb[b] - {a}
    return len(others - nb[a]) / len(others) if others else 0.0

inside = [e for e in edges if e[0] // S == e[1] // S]
across = [e for e in edges if e[0] // S != e[1] // S]
mean = lambda xs: sum(xs) / len(xs)
print(f"{N} people, {len(edges)} ties: {len(inside)} inside groups,"
      f" {len(across)} between")
print("                     mean overlap   novelty of the contact's other contacts")
for name, es in (("inside-group ties", inside), ("between-group ties", across)):
    nov = mean([novelty(a, b) for a, b in es] + [novelty(b, a) for a, b in es])
    print(f"  {name:18s}  {mean([overlap(*e) for e in es]):10.3f}   {nov:8.3f}")

def giant(keep):
    par = list(range(N))
    def find(x):
        while par[x] != x:
            par[x] = par[par[x]]; x = par[x]
        return x
    for a, b in keep:
        ra, rb = find(a), find(b)
        if ra != rb: par[ra] = rb
    size = {}
    for x in range(N):
        r = find(x); size[r] = size.get(r, 0) + 1
    return max(size.values()) / N

order = sorted(edges, key=lambda e: (overlap(*e), rng.random()))
shuffled = edges[:]; rng.shuffle(shuffled)
print("largest component (share of people) after removing a share of ties:")
print("  removed   low overlap first    random    high overlap first")
for f in (0.0, 0.03, 0.06, 0.08, 0.1, 0.2, 0.4):
    k = int(f * len(edges))
    low, rnd = giant(order[k:]), giant(shuffled[k:])
    high = giant(order[:len(edges) - k])
    print(f"   {f:4.0%}        {low:6.2f}          {rnd:6.2f}        {high:6.2f}")
# 600 people, 2405 ties: 2255 inside groups, 150 between
#                      mean overlap   novelty of the contact's other contacts
#   inside-group ties        0.230      0.627
#   between-group ties       0.001      0.998
# largest component (share of people) after removing a share of ties:
#   removed   low overlap first    random    high overlap first
#      0%          1.00            1.00          1.00
#      3%          1.00            1.00          1.00
#      6%          0.99            1.00          1.00
#      8%          0.93            1.00          1.00
#     10%          0.26            1.00          1.00
#     20%          0.03            1.00          1.00
#     40%          0.03            1.00          0.99

Between-group ties are only about 6 % of all ties, but their mean overlap is almost zero (0.001), and 99.8 % of the contact’s other contacts are people you do not know; within-group ties have a mean overlap of 0.23, and only about 63 % of the contact’s contacts are new faces. The three removal orders give strikingly different results. Removing ties from the lowest overlap upwards, taking away only 10 % of the ties shrinks the largest component from everyone to about a quarter (0.26), and after 20 % it is no larger than a single group (3 %); removing ties at random, or from the highest overlap downwards, leaves the network almost intact even after 40 % of the ties are gone. In this synthetic network the between-group ties are exactly the low-overlap ties, so the result is cleaner than in real data, where overlap and strength are only correlated.

Small worlds

Another phenomenon connected with bridges is the small world: in a very large network, any two people are often only a few steps apart. In 1998 Watts and Strogatz used a simple model to explain how this can coexist with “my friends’ friends are my friends” (high clustering) (Watts and Strogatz 1998).

# Watts & Strogatz (1998) small-world model, standard library only.
# Ring of N nodes, each tied to its K nearest neighbours (K/2 on each side).
# Each lattice edge is rewired with probability p to a random new endpoint
# (no self-loops, no duplicate edges). L = mean shortest path (BFS from a
# random sample of sources), C = mean local clustering coefficient.
import math, random
from collections import deque

N, K = 1000, 10

def ws_graph(p, rng):
    nb = [set() for _ in range(N)]
    for i in range(N):
        for j in range(1, K // 2 + 1):
            a, b = i, (i + j) % N
            nb[a].add(b); nb[b].add(a)
    for j in range(1, K // 2 + 1):          # rewire lap by lap, as in the paper
        for i in range(N):
            b = (i + j) % N
            if b in nb[i] and rng.random() < p:
                new = rng.randrange(N)
                while new == i or new in nb[i]:
                    new = rng.randrange(N)
                nb[i].discard(b); nb[b].discard(i)
                nb[i].add(new); nb[new].add(i)
    return nb

def mean_path(nb, sources):
    tot = cnt = 0
    for s in sources:
        dist = {s: 0}; q = deque([s])
        while q:
            u = q.popleft()
            for v in nb[u]:
                if v not in dist:
                    dist[v] = dist[u] + 1; q.append(v)
        tot += sum(dist.values()); cnt += len(dist) - 1
    return tot / cnt

def clustering(nb):
    c = 0.0
    for i in range(N):
        ns = list(nb[i]); k = len(ns)
        if k < 2:
            continue
        links = sum(1 for a in range(k) for b in range(a + 1, k)
                    if ns[b] in nb[ns[a]])
        c += 2 * links / (k * (k - 1))
    return c / N

def curve(ps, reps=3, n_src=100, seed=1):
    rng = random.Random(seed)
    out = []
    for p in ps:
        L = C = 0.0
        for _ in range(reps):
            g = ws_graph(p, rng)
            L += mean_path(g, rng.sample(range(N), n_src)); C += clustering(g)
        out.append((p, L / reps, C / reps))
    return out

if __name__ == "__main__":
    ps = [0, 0.0003, 0.001, 0.003, 0.01, 0.02, 0.05, 0.1, 0.3, 1.0]
    res = curve(ps)
    L0, C0 = res[0][1], res[0][2]
    print(f"N = {N}, K = {K}: lattice L(0) = {L0:.1f}, C(0) = {C0:.3f}")
    print("    p      L(p)/L(0)   C(p)/C(0)")
    for p, L, C in res:
        print(f"  {p:<7}  {L / L0:8.3f}   {C / C0:9.3f}")
    lr = math.log(N) / math.log(K)
    print(f"random-graph benchmarks: L ~ ln N / ln K = {lr:.2f},"
          f" C ~ K / N = {K / N:.3f}")
# N = 1000, K = 10: lattice L(0) = 50.5, C(0) = 0.667
#     p      L(p)/L(0)   C(p)/C(0)
#   0           1.000       1.000
#   0.0003      0.734       0.999
#   0.001       0.492       0.997
#   0.003       0.326       0.990
#   0.01        0.183       0.972
#   0.02        0.136       0.942
#   0.05        0.106       0.872
#   0.1         0.089       0.747
#   0.3         0.071       0.352
#   1.0         0.065       0.012
# random-graph benchmarks: L ~ ln N / ln K = 3.00, C ~ K / N = 0.010

In the regular ring, two people are on average about 50 steps apart, and the clustering coefficient is 0.667. Rewiring just 1 % of the edges into random “shortcuts” ($p = 0.01$) brings the mean path length down to 18 % of its original value, while clustering keeps 97 % of its value; at $p = 0.05$ the path length is down to 11 % and clustering is still at 87 %. For clustering to fall noticeably as well, $p$ must exceed about 0.1; at $p = 1$ the network is close to fully random, the path length is about 6.5 % of the original (near the random-graph estimate $\ln N / \ln K = 3$ steps) and clustering is down to about 1 %. There is thus a wide range in which the network is both as tight as a small circle and as “small” as a random graph. The reason is that every shortcut shortens the distance between many pairs of people at once, but destroys only one local triangle.

In the original paper Watts and Strogatz showed that the collaboration network of Hollywood film actors, the power grid of the western United States and the neural network of the nematode worm all combine very short paths with clustering far higher than in a random graph (Watts and Strogatz 1998). The “shortcuts” of the model correspond, in social networks, to Granovetter’s bridges.

Later tests: which ties really help?

Granovetter’s data can only tell us that weak ties make up most of the contacts who helped. To answer whether a weak tie is more useful than a strong tie, one needs to know all of a person’s ties, and whether each of them brought a job.

These two studies are the strongest tests of Granovetter’s hypothesis so far, and their conclusion is more nuanced than “the weaker the better”: the value of a tie depends on how strength is measured, on whether one asks about the value of each tie or the total, and on the nature of the industry. The LinkedIn experiments changed whom users were shown without their knowledge, and after publication they prompted a debate about informed consent in platform experiments; the ethics section of Chapter 8 returns to this.

Taken together, the two studies show that “weak ties help”, “ties of moderate strength help most” and “a single strong tie is more useful” can all be true at once: strong ties are more willing to help, but what they know is mostly what you know already; weak ties bring fresher information, but each is less willing to help, and there are simply far more of them. Which statement holds depends on whether one asks about the value of each tie or the value of all of them together.

Chapter summary

From the “forbidden triad” Granovetter inferred that strong ties are rarely bridges and that bridges are mostly weak ties; his job-finding data come from a subsample of 54 people and show that most of the people who helped were acquaintances seen infrequently. Neighbourhood overlap makes the argument computable: low-overlap ties bring novel information and hold the whole network together. The Watts–Strogatz model shows that a few shortcuts make path lengths collapse while clustering barely changes. Large-scale studies with Facebook and LinkedIn data show that the overall contribution of weak ties comes largely from their number, and that, tie for tie, moderate strength is most useful. The next chapter moves from ties to positions: what it means to stand in the gap between circles.