Network Centrality

Ranking nodes by structural importance: who connects most, who bridges groups, and who the important nodes themselves point to.

$A four-node star shows the center dominating degree, betweenness, and PageRank while leaves score only a fraction$

A four-node star shows the center dominating degree, betweenness, and PageRank while leaves score only a fraction

Why Does This Exist?

"Important" is not one thing. A hub with a hundred ties, a broker joining two departments, and a newcomer cited by three Nobelists are each central in a different sense, and each sense predicts something different: hubs spread behaviour, brokers control flow, the endorsed inherit status. Picking the wrong measure answers the wrong question, expensively: vaccinating hubs versus bridges, or ranking pages by raw in-degree versus endorsement quality, gives different top lists and different outcomes. The graph encoding is in graph fundamentals; the walk machinery behind the last measure is a random walk settling to its stationary split.

The one idea you need first

All centralities score nodes from structure alone. Degree counts neighbours (local). Closeness averages distances to all others (reach). Betweenness counts shortest paths passing through (brokerage). Eigenvector and PageRank count endorsements weighted by the endorser's own score (recursive status).

Think of It Like This

An airport network, three crowns

Busiest airport crowns the hub: most direct flights. Best-connected crowns the broker: sits on the most itineraries between other cities, even with few runways of its own (think a small Gulf hub joining continents). Most prestigious crowns the airport that important airports fly to: a handful of flagship routes outweighs dozens of regional hops.

One airport can hold all three crowns (a star's center), or they can split: a regional hub has degree without brokerage, a bridge town has brokerage without degree, a boutique destination has prestige without either. The measure you publish decides which town gets the new runway.

Where the analogy stops: real centralities normalize by network size, weight by traffic, and (for PageRank) add teleportation so the ranking exists on messy graphs.

How It Actually Works

On $n$ nodes, with distances $d(i,j)$ and $\sigma_{st}$ shortest paths between $s$ and $t$ :

Degree. $C_D(i) = d_i/(n-1)$ : share of possible ties held. Cheap, local, blind to position.

Closeness. $C_C(i) = (n-1)/\sum_j d(i,j)$ : inverse of average distance. High means short trips everywhere. Needs a connected graph (or harmonic variants).

Betweenness. $C_B(i) = \sum_{s \ne i \ne t} \sigma_{st}(i)/\sigma_{st}$ : share of shortest paths brokered. High means bridge. Costly: all-pairs paths in principle.

Eigenvector. $Ax = \lambda x$ : score proportional to neighbours' scores. Prestige flows along edges. Needs a connected (or strongly connected) graph to be unique.

PageRank. Stationary of $dP + (1-d)\mathbf{1}v^\top$ with damping $d \approx 0.85$ : recursive endorsement plus teleportation that guarantees existence on any graph.

Worked example

Star: center 1 tied to leaves 2, 3, 4. $n = 4$ .

Degree: center $3/3 = 1.0$ , each leaf $1/3 \approx 0.333$ .

Betweenness (unnormalized): leaf pairs $(2,3)$ , $(2,4)$ , $(3,4)$ all route through 1, so center $3$ , leaves $0$ . The center brokers everything despite the leaves outnumbering it.

PageRank with $d = 0.85$ : let center be $c$ , each leaf $l$ . Then $c = 0.0375 + 0.85(3l)$ and $l = 0.0375 + 0.85(c/3)$ . Solving: $c \approx 0.4796$ , $l \approx 0.1734$ , summing to $0.4796 + 3(0.1734) \approx 1.0$ . The center takes nearly half the rank while each leaf holds 17 percent: endorsement concentrates harder than raw degree (75 vs 8 percent of degree share would suggest 3:1, PageRank gives about 2.8:1 here after teleportation flattens).

Watch Out For

Reading centrality as causality or quality

High centrality predicts exposure and control, not merit or influence over outcomes. The most-cited paper may be a wrong result everyone refutes; the most-between person may be a bottleneck everyone resents; the highest-degree account may be a bot.

Symptom: interventions on top-ranked nodes (seed, vaccinate, promote) underperform because rank measured traffic, not persuasion. Fix: pair structure with behaviour (actual forwarding, conversion, transmission rates) and test the intervention, since centrality is a hypothesis about importance, not a measurement of it.

Running prestige scores on graphs with sinks and spikes

Dangling nodes leak PageRank out of the system, disconnected pieces trap it, and a spam farm of interlinked pages manufactures eigenvector score from nothing. Raw eigenvector centrality on a directed mess may not even be unique.

Symptom: ranks shift with initialization, sinks accumulate mass, or obvious spam outranks authorities. Fix: always teleport (PageRank, not raw eigenvector) on directed graphs, remove or repair sinks first, and distrust prestige scores on graphs you have not cleaned.

The Quick Version

Degree counts ties, closeness counts reach, betweenness counts brokerage, eigenvector and PageRank count weighted endorsements.
On the 4-star, the center scores degree 1.0, betweenness 3, PageRank 0.48; leaves score 0.33, 0, 0.17.
Hubs spread, bridges control, the endorsed inherit: match the measure to the question.
Centrality is structural exposure, not proven influence: validate with behaviour.
Teleport and clean before trusting prestige scores on directed or messy graphs.