Not only how many connections, but to whom

Degree centrality simply counts a person’s contacts. But knowing ten people who know only you is plainly a different position from knowing ten people who each know hundreds. In 1972 Bonacich proposed a self-consistent definition: a person’s status is proportional to the sum of the statuses of his or her contacts (Bonacich 1972).

Bonacich’s beta-centrality: the power of being depended upon

In 1987 Bonacich generalised the idea into a family of measures:

$$c(\beta) = \alpha \sum_{k=0}^{\infty} \beta^k A^{k+1} \mathbf{1}$$

$A^{k+1}\mathbf{1}$ counts the walks of length $k+1$ starting from each person, $\beta$ sets how much weight distant walks receive, and the series converges for $|\beta| < 1/\lambda_{\max}$; at $\beta = 0$, $c$ is just degree, and as $\beta$ approaches $1/\lambda_{\max}$, $c$ approaches eigenvector centrality. He pointed out that when $\beta$ is negative the measure captures something else: in exchange and bargaining networks, power comes from being tied to people who have no other options, because they can only depend on you, whereas being tied to people with many options of their own weakens your bargaining position (Bonacich 1987).

# Eigenvector centrality (Bonacich 1972) and Bonacich's (1987) beta-centrality
#   c(beta) = alpha * sum_{k>=0} beta^k R^(k+1) 1,  scaled so that sum c^2 = n,
# computed as a series (valid for |beta| < 1/lambda_max). beta > 0: being tied
# to well-connected people counts; beta < 0: being tied to people who have
# FEW other options counts (bargaining power in exchange networks).
# Invented network: X has four contacts x1-x4 with no other ties; Y has four
# contacts y1-y4 who are all tied to each other; X and Y are tied.
# All columns are scaled the same way (beta = 0 gives degree).
import math
from itertools import combinations
ties = [("X", f"x{i}") for i in range(1, 5)] + [("Y", f"y{i}") for i in range(1, 5)]
ties += list(combinations([f"y{i}" for i in range(1, 5)], 2)) + [("X", "Y")]
nodes = sorted({v for e in ties for v in e})
nb = {v: set() for v in nodes}
for a, b in ties:
    nb[a].add(b); nb[b].add(a)

def mult(x):                       # R x
    return {v: sum(x[w] for w in nb[v]) for v in nodes}

def scale(x):
    s = math.sqrt(sum(val * val for val in x.values()) / len(x))
    return {v: x[v] / s for v in nodes}

x = {v: 1.0 for v in nodes}        # power iteration for the leading eigenvector
for _ in range(500):
    y = mult(x)
    lam = math.sqrt(sum(v * v for v in y.values()) / sum(v * v for v in x.values()))
    x = scale(y)
print(f"lambda_max = {lam:.3f}, so |beta| must stay below {1 / lam:.3f}")

def beta_centrality(beta, terms=400):
    total, walk = {v: 0.0 for v in nodes}, mult({v: 1.0 for v in nodes})
    for k in range(terms):
        for v in nodes:
            total[v] += beta ** k * walk[v]
        walk = mult(walk)
    return scale(total)

deg = scale({v: float(len(nb[v])) for v in nodes})
cols = [("degree", deg), ("eigenvector", x)]
cols += [(f"beta {b:+.2f}", beta_centrality(b)) for b in (0.2, -0.2)]
print("node  " + "".join(f"{name:>13s}" for name, _ in cols))
for v in ("X", "Y", "x1", "y1"):
    print(f" {v:4s}" + "".join(f"{c[v]:13.2f}" for _, c in cols))
# lambda_max = 4.068, so |beta| must stay below 0.246
# node         degree  eigenvector   beta +0.20   beta -0.20
#  X            1.46         0.48         0.75         2.10
#  Y            1.46         1.47         1.50         1.11
#  x1           0.29         0.12         0.21         0.05
#  y1           1.16         1.37         1.32         1.04

X and Y have exactly the same degree, but their eigenvector centralities differ by a factor of three (0.48 against 1.47): Y’s contacts are connected to one another and each has many connections, while X’s contacts know only X. With $\beta = +0.2$ the order is the same (0.75 against 1.50). But with $\beta = -0.2$ the order reverses: X scores 2.10 and Y 1.11. In Bonacich’s sense, X’s contacts can deal with the outside world only through X, so X is in a position of being depended upon. This connects with Chapter 2: all of X’s four contacts are separated by structural holes, and X’s network constraint is low.

Which centrality is “right” depends on the question. If what matters is how fast information can spread from a person through the network, being connected to well-connected people (positive $\beta$, eigenvector centrality) counts for more; if what matters is bargaining power in negotiation and exchange, being depended upon (negative $\beta$) may count for more. Ranking everyone by a single measure without saying what the question is is often meaningless.

PageRank

Directed networks raise two problems that do not exist in undirected ones. The first is dangling nodes: pages with no outgoing links, where the random surfer has nowhere to go. The usual remedy is to let such a page jump to any page with equal probability. The second is traps: a set of pages that link only to one another and never out, so that a random surfer who enters cannot leave and the score accumulates there. The random jumps of the damping factor solve both problems at once and also guarantee that power iteration converges: the error shrinks by a factor of roughly $d$ at each step. Langville and Meyer give a systematic review of these remedies and of the convergence properties (Langville and Meyer 2004).

# PageRank by power iteration, standard library only (Brin & Page 1998;
# Page et al. 1999). An invented web of 8 pages. F has no out-links (a
# dangling page): its rank is spread evenly over all pages. G and H link only
# to each other (a "rank sink" that B feeds). With damping d, the surfer
# follows a link with probability d and jumps to a random page otherwise:
#   PR = (1 - d)/n + d * (sum over in-links PR(j)/out(j) + dangling mass/n)
links = {"A": "BC", "B": "CG", "C": "A", "D": "CE", "E": "CF", "F": "",
         "G": "H", "H": "G"}
pages = sorted(links)
n = len(pages)

def pagerank(d, tol=1e-12, max_it=20000):
    pr = {p: 1 / n for p in pages}
    errs = []
    for it in range(1, max_it + 1):
        dangling = sum(pr[p] for p in pages if not links[p])
        new = {p: (1 - d) / n + d * dangling / n for p in pages}
        for p in pages:
            for q in links[p]:
                new[q] += d * pr[p] / len(links[p])
        err = sum(abs(new[p] - pr[p]) for p in pages)
        errs.append(err); pr = new
        if err < tol:
            return pr, it, errs
    return pr, max_it, errs

pr, it, errs = pagerank(0.85)
order = sorted(pages, key=lambda p: -pr[p])
print("d = 0.85: " + "  ".join(f"{p} {pr[p]:.3f}" for p in order))
print(f"  converged in {it} iterations; error ratio per step about"
      f" {errs[30] / errs[29]:.3f} (close to d)")
print("damping   iterations   G + H share   top page")
for d in (0.5, 0.85, 0.95, 0.99, 1.0):
    pr_d, it_d, _ = pagerank(d)
    top = max(pages, key=lambda p: pr_d[p])
    its = f"{it_d:9d}" if it_d < 20000 else "    never"
    print(f"  {d:4.2f}   {its}     {pr_d['G'] + pr_d['H']:8.3f}       {top}")
# d = 0.85: G 0.279  H 0.260  A 0.144  C 0.143  B 0.084  F 0.036  E 0.032  D 0.023
#   converged in 146 iterations; error ratio per step about 0.827 (close to d)
# damping   iterations   G + H share   top page
#   0.50          35        0.326       G
#   0.85         146        0.539       G
#   0.95         462        0.759       G
#   0.99        2356        0.938       G
#   1.00       never        1.000       H

At $d = 0.85$ the highest-ranked pages are G (0.279) and H (0.260), because half of B’s score flows into the trap and can then only circulate between the two, with only the random jumps carrying it out again. C has four incoming links (from A, B, D and E), more than any other page, yet its score (0.143) is slightly lower than that of A (0.144), which has only one incoming link: C gives all of its score to A. PageRank measures not the number of incoming links but their sources. The error shrinks by a factor of about 0.827 per step, close to $d$.

The larger the damping factor, the closer the ranking comes to the “pure” link structure, but at two costs: convergence slows (35 iterations at $d = 0.5$, 146 at $d = 0.85$, 2,356 at $d = 0.99$), and the trap absorbs more of the score (G and H together rise from 0.33 to 0.94); at $d = 1$ the iteration oscillates between G and H for ever and never converges, with the whole score trapped. $d = 0.85$ is a compromise between “respecting the link structure” and “being stable, fast and not hijacked by traps”; it has no theoretical claim to optimality.

Centrality applied to people

In social networks, centralities of various kinds are often treated as measures of “influence” and used to choose starting points for spreading. Chapter 3 showed that for complex contagions, centralities based on shortest paths can pick the wrong people; this chapter’s examples show that different centralities answer different questions. There is a further limitation: centrality describes only a structural position, and says nothing about whether a person is willing to pass something on or whether his or her word is trusted.

Chapter summary

Eigenvector centrality brings “whom one is connected to” into the calculation of status and can be found by power iteration. Bonacich’s beta-centrality joins degree and eigenvector centrality into one family of measures; negative beta captures the bargaining power of being depended upon, which connects with structural holes. PageRank is a random walk with random jumps on a directed network: the damping factor deals with dangling nodes and traps and guarantees convergence, and $d = 0.85$ is a compromise rather than an optimum. The next chapter discusses how, when everyone watches what the people before them do, a group can converge on the same direction, and why that direction may be wrong.