Two kinds of social capital

The previous chapter was about ties: which relationships bring new information. This chapter is about positions: how a person’s contacts are connected to one another. Sociology offers two views that seem to point in opposite directions.

The first emphasises closure. Coleman argued that when a person’s contacts know one another and are connected among themselves, the network can generate trust, norms and sanctions: if someone breaks a promise, everyone will hear of it, so everyone keeps their word; in schools where the parents know one another, children find it harder to escape discipline. He called the benefits that come from such closed networks social capital (Coleman 1988).

The second emphasises brokerage. In his 1992 book Structural Holes, Burt argued that what is most valuable in a network is often not density but gaps: if two of your contacts do not know each other, there is a “structural hole” between them, and you are the only one who can connect the information, resources and opportunities on the two sides. Opinion and practice converge inside circles; people who stand between circles see different ideas earlier and can decide what to carry from one side to the other (Burt 1992).

Network constraint and effective size

Burt measured the extent to which a person’s network is “trapped” among mutually connected contacts. Let $p_{ij}$ be the share of $i$’s time and energy invested in contact $j$ (for an unweighted undirected network, $p_{ij} = 1/k_i$). The dyadic constraint between $i$ and $j$ is

$$c_{ij} = \Big(p_{ij} + \sum_{q \neq i, j} p_{iq}\, p_{qj}\Big)^2$$

The first term in the brackets is $i$’s direct investment in $j$; the second is the indirect investment through shared contacts $q$: if $i$’s other contacts also deal a great deal with $j$, $i$ can hardly get around $j$. The network constraint of $i$ is $C_i = \sum_j c_{ij}$. The higher the constraint, the fewer the structural holes (Burt 1992).

Another measure is effective size: the number of contacts minus their redundancy. For unweighted undirected networks, Borgatti showed that Burt’s definition simplifies to $n – 2t/n$, where $n$ is the number of contacts and $t$ the number of ties among them (Borgatti 1997). Effective size divided by $n$ is called efficiency.

# Burt's network constraint and effective size on a small invented network.
# Three groups of four (a, b, c) are cliques. Ana is a fifth member of group a
# (tied to all of a1-a4). Bo is tied to one person in each group (a1, b1, c1).
# Cy is tied to two people in group b and two in group c (b2, b3, c2, c3).
# For binary undirected ties p_ij = 1/k_i (Burt 1992). Dyadic constraint
#   c_ij = (p_ij + sum over q != i, j of p_iq * p_qj) ** 2,  C_i = sum_j c_ij.
# Effective size = n - 2t/n (t = ties among the n contacts; Borgatti 1997).
from itertools import combinations
groups = {g: [f"{g}{i}" for i in range(1, 5)] for g in "abc"}
ties = set()
for members in groups.values():
    ties |= {tuple(sorted(e)) for e in combinations(members, 2)}
ties |= {("Ana", x) for x in groups["a"]}
ties |= {("Bo", x) for x in ("a1", "b1", "c1")}
ties |= {("Cy", x) for x in ("b2", "b3", "c2", "c3")}
nb = {}
for u, v in ties:
    nb.setdefault(u, set()).add(v); nb.setdefault(v, set()).add(u)

def p(i, j):
    return 1 / len(nb[i]) if j in nb[i] else 0.0

def dyadic(i, j):
    return (p(i, j) + sum(p(i, q) * p(q, j) for q in sorted(nb[i]) if q != j)) ** 2

def constraint(i):
    return sum(dyadic(i, j) for j in sorted(nb[i]))

def effective_size(i):
    n = len(nb[i])
    t = sum(1 for u, v in combinations(nb[i], 2) if v in nb[u])
    return n - 2 * t / n

print("node  contacts  effective size  efficiency  constraint  largest c_ij")
for i in ("Ana", "a2", "a1", "Cy", "Bo"):
    n, es = len(nb[i]), effective_size(i)
    j = max(sorted(nb[i]), key=lambda x: dyadic(i, x))
    print(f" {i:4s} {n:6d} {es:13.2f} {es / n:12.2f} {constraint(i):11.3f}"
          f"     {j} {dyadic(i, j):.3f}")
print("benchmarks: n unconnected contacts give C = 1/n;"
      f" a clique of 5 gives C = {4 * (0.25 + 3 / 16) ** 2:.3f}")
# node  contacts  effective size  efficiency  constraint  largest c_ij
#  Ana       4          1.00         0.25       0.733     a1 0.191
#  a2        4          1.00         0.25       0.733     a1 0.191
#  a1        5          2.60         0.52       0.530     Ana 0.123
#  Cy        4          3.00         0.75       0.391     b2 0.098
#  Bo        3          3.00         1.00       0.333     a1 0.111
# benchmarks: n unconnected contacts give C = 1/n; a clique of 5 gives C = 0.766

All four of Ana’s contacts, like those of a2, know one another: the effective size is just 1 and the constraint 0.733 (had a1 not been tied to Bo, everyone in this five-person clique would have a constraint of 0.766). Bo has only three contacts, but they belong to three groups that do not know one another: effective size 3, efficiency 1 and constraint 1/3, the lowest in the network. Cy’s four contacts form two pairs, so the effective size is 3 and the constraint 0.391. Because a1 belongs to group a and is also tied to Bo, a1’s constraint falls to 0.530. These numbers show that constraint has little to do with how many contacts one has and a great deal to do with whether those contacts are connected: Ana, with more contacts, is far more constrained than Bo, with fewer.

Betweenness centrality and Brandes’s algorithm

Another common measure of “standing in the middle” is Freeman’s betweenness centrality: the share of all shortest paths between pairs of people that pass through a given person (Freeman 1977). Computing it directly means enumerating all paths. In 2001 Brandes gave a much faster algorithm: run one breadth-first search from each starting point, recording the number of shortest paths to each person, then work back from the farthest people accumulating the share of paths each person “carries”; for unweighted networks the total work is proportional to the number of people times the number of ties (Brandes 2001).

# Betweenness centrality with Brandes' (2001) algorithm, standard library only:
# one breadth-first search per source, then dependencies accumulated backwards,
# O(n m) for unweighted graphs instead of O(n^3).
# Part 1: the invented network of the constraint program (p03).
# Part 2: a synthetic network of 12 groups of 15 (tie probability 0.35 inside,
# 40 random ties between groups): do betweenness and low constraint agree?
import random
from collections import deque
from itertools import combinations

def brandes(nb):
    bc = {v: 0.0 for v in nb}
    for s in nb:
        stack, pred = [], {v: [] for v in nb}
        sigma = dict.fromkeys(nb, 0); sigma[s] = 1
        dist = dict.fromkeys(nb, -1); dist[s] = 0
        q = deque([s])
        while q:
            v = q.popleft(); stack.append(v)
            for w in sorted(nb[v]):
                if dist[w] < 0:
                    dist[w] = dist[v] + 1; q.append(w)
                if dist[w] == dist[v] + 1:
                    sigma[w] += sigma[v]; pred[w].append(v)
        delta = dict.fromkeys(nb, 0.0)
        while stack:
            w = stack.pop()
            for v in pred[w]:
                delta[v] += sigma[v] / sigma[w] * (1 + delta[w])
            if w != s:
                bc[w] += delta[w]
    n = len(nb)
    return {v: bc[v] / 2 / ((n - 1) * (n - 2) / 2) for v in nb}   # undirected, 0..1

def constraint(nb, i):
    p = lambda a, b: 1 / len(nb[a]) if b in nb[a] else 0.0
    return sum((p(i, j) + sum(p(i, q) * p(q, j) for q in sorted(nb[i])
                              if q != j)) ** 2 for j in sorted(nb[i]))

def add(nb, u, v):
    nb.setdefault(u, set()).add(v); nb.setdefault(v, set()).add(u)

nb = {}
for g in "abc":
    for u, v in combinations([f"{g}{i}" for i in range(1, 5)], 2):
        add(nb, u, v)
for x in ("a1", "a2", "a3", "a4"): add(nb, "Ana", x)
for x in ("a1", "b1", "c1"): add(nb, "Bo", x)
for x in ("b2", "b3", "c2", "c3"): add(nb, "Cy", x)
bc = brandes(nb)
print("part 1 (normalised betweenness, 0-1):")
top6 = sorted(nb, key=lambda v: -bc[v])[:6]
print("  " + ", ".join(f"{v} {bc[v]:.3f}" for v in top6))
print(f"  Ana {bc['Ana']:.3f}, a2 {bc['a2']:.3f}")

rng = random.Random(4)
G, S = 12, 15
big = {i: set() for i in range(G * S)}
for g in range(G):
    for a, b in combinations(range(g * S, (g + 1) * S), 2):
        if rng.random() < 0.35: add(big, a, b)
k = 0
while k < 40:
    a, b = rng.randrange(G * S), rng.randrange(G * S)
    if a // S != b // S and b not in big[a]:
        add(big, a, b); k += 1
bc = brandes(big)
con = {v: constraint(big, v) for v in big}

def ranks(d):                     # average ranks, so tied values share a rank
    order = sorted(d, key=lambda v: d[v]); r = {}; i = 0
    while i < len(order):
        j = i
        while j + 1 < len(order) and abs(d[order[j + 1]] - d[order[i]]) < 1e-12:
            j += 1
        for v in order[i:j + 1]: r[v] = (i + j) / 2
        i = j + 1
    return r

def pearson(x, y):
    mx, my = sum(x) / len(x), sum(y) / len(y)
    sxy = sum((a - mx) * (b - my) for a, b in zip(x, y))
    sxx = sum((a - mx) ** 2 for a in x); syy = sum((b - my) ** 2 for b in y)
    return sxy / (sxx * syy) ** 0.5

rb, rc = ranks(bc), ranks(con)
n = len(big)
rho = pearson([rb[v] for v in big], [rc[v] for v in big])   # Spearman
print(f"part 2: {n} people; Spearman correlation of betweenness with constraint"
      f" = {rho:+.2f}")
top = sorted(big, key=lambda v: -bc[v])[:5]
print("  top 5 by betweenness  (bc, constraint C, ties outside own group):")
for v in top:
    out = sum(1 for w in big[v] if w // S != v // S)
    print(f"    person {v:3d}: bc {bc[v]:.3f}, C {con[v]:.2f}, {out} outside")
print(f"  median person: bc {sorted(bc.values())[n // 2]:.3f},"
      f" C {sorted(con.values())[n // 2]:.2f}")
# part 1 (normalised betweenness, 0-1):
#   Bo 0.544, a1 0.440, b1 0.251, c1 0.251, Cy 0.126, b2 0.050
#   Ana 0.000, a2 0.000
# part 2: 180 people; Spearman correlation of betweenness with constraint = -0.78
#   top 5 by betweenness  (bc, constraint C, ties outside own group):
#     person 133: bc 0.129, C 0.19, 2 outside
#     person  32: bc 0.127, C 0.19, 2 outside
#     person 100: bc 0.114, C 0.19, 2 outside
#     person   6: bc 0.111, C 0.18, 2 outside
#     person 116: bc 0.102, C 0.31, 2 outside
#   median person: bc 0.009, C 0.28

In the invented network Bo has the highest betweenness (0.544), because the shortest paths between the three groups all run through him; a1 comes next (0.440), since group a’s connections to the outside all run through a1; Ana and a2 have betweenness 0, because every pair has equally short paths that avoid them. In the synthetic network of 180 people the rank correlation between betweenness and constraint is −0.78: people who stand in the middle usually have low constraint. The five people with the highest betweenness each have two ties to other groups and constraints between 0.18 and 0.31, while the median person has a betweenness of only 0.009 and a constraint of 0.28. The two measures are not identical: betweenness looks at paths across the whole network, constraint only at the local structure around a person, and someone can have low constraint and still sit in a remote corner.

Evidence on brokerage

This study is the most frequently cited evidence for structural-hole theory, but some points need noting. First, it is a cross-sectional correlational study in a single company, and it cannot rule out reverse causation: more able managers may find it easier to build ties across departments, rather than cross-departmental ties making people more able. Second, the “good ideas” were judged by two senior managers whose own positions and preferences may have shaped their ratings. Third, the sample consists of managers in one American company; whether the returns to brokerage exist elsewhere has to be tested separately.

This study suggests that “structural holes pay” is not a universal law but depends on how an organisation regards the person in the middle: as a bridge who brings in new information, or as someone who may exploit gaps in information for private gain. In an environment that relies heavily on trust and long-term commitment, the second view may prevail. Coleman’s closure and Burt’s brokerage therefore look more like a pair of options to be weighed according to the setting than a question of who is right.

Chapter summary

Coleman’s closure stresses that dense networks bring trust and sanctions; Burt’s structural holes stress that standing between circles brings information and opportunity. Network constraint measures how far a person is trapped among mutually connected contacts; it depends on whether the contacts are connected, not on how many there are. Network constraint and betweenness centrality measure the same kind of “position” from different angles; in a synthetic network they are strongly (negatively) correlated but not identical. Burt’s study of 673 managers shows that those who span structural holes are more likely to put forward ideas judged valuable and to enjoy better pay and promotion; but in Chinese high-tech firms structural holes were harmful where the organisational culture emphasised high commitment. The next chapter asks whether bridges are enough when what spreads is not a piece of news but a behaviour that needs reinforcement from several people.