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 scoring degree 1.0, betweenness 3, and PageRank 0.48 while each leaf scores 0.33, 0, and 0.17$

A four node star shows the center scoring degree 1.0, betweenness 3, and PageRank 0.48 while each leaf scores 0.33, 0, and 0.17

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 prize winners are each central in a different sense. Each sense predicts something different: hubs spread behavior, brokers control flow, the endorsed inherit status. Picking the wrong measure answers the wrong question, and the cost is concrete: vaccinating hubs versus bridges, or ranking pages by raw in-degree versus endorsement quality, gives different top lists and different outcomes. The graph encoding sits in graph fundamentals, and 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 neighbors. Closeness averages distances to all others. Betweenness counts shortest paths passing through. Eigenvector and PageRank count endorsements weighted by the endorser's own score.

Think of It Like This

An airport network, three crowns

Busiest airport crowns the hub: most direct flights. Best-connected crowns the broker: it sits on the most itineraries between other cities, even with few runways of its own, like 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, as a star center does, 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$ , where $d(i, j)$ names the hop distance and $\sigma_{st}$ counts the tied-shortest routes:

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, where $\sigma_{st}(i)$ counts those passing through $i$ . High means bridge. Costly in principle, since it reasons over all pairs.

Eigenvector. $A x = \lambda x$ : score proportional to neighbors' scores, where $A$ is the adjacency matrix, $x$ the score vector, and $\lambda$ its scale. Prestige flows along edges. Needs a connected graph to be unique.

PageRank. Stationary point of $d P + (1 - d) \mathbf{1} v^{T}$ with damping $d \approx 0.85$ , where $P$ holds walk transitions, $\mathbf{1}$ is ones, and $v$ is the teleport vector. Recursive endorsement plus teleportation guarantees an answer on any graph. Its walk foundation is Markov chains, and shortest-route counting leans on shortest paths.

Worked example

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

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

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

PageRank with $d = 0.85$ : write center $c$ and each leaf $l$ . Teleport per node is $0.15 / 4 = 0.0375$ . Then $c = 0.0375 + 0.85 \cdot 3l$ and $l = 0.0375 + 0.85 \cdot (c / 3)$ . Substituting gives $c = 0.133125 + 0.7225c$ , so $0.2775c = 0.133125$ and $c \approx 0.4796$ . Then $l \approx 0.0375 + 0.2833 \cdot 0.4796 \approx 0.1734$ . Check: $0.4796 + 3 \cdot 0.1734 \approx 1.0$ . The center takes nearly half the rank while each leaf holds 17 percent.

Watch Out For

Reading centrality as causality or quality

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

Symptom: treating top-ranked nodes with seeding, vaccination, or promotion underperforms because rank measured traffic, not persuasion. Fix: pair structure with behavior such as forwarding, conversion, or transmission rates, and test the intervention, since centrality is a hypothesis about importance rather than 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 scores on a directed mess may not even be unique.

Symptom: ranks shift with initialization, sinks collect mass, or obvious spam outranks authorities. Fix: always teleport through PageRank rather than raw eigenvector on directed graphs, 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, and eigenvector with PageRank count weighted endorsements.
On the 4-star, the center scores degree 1.0, betweenness 3, and PageRank 0.48, while leaves score 0.33, 0, and 0.17.
Hubs spread, bridges control, and the endorsed inherit, so match the measure to the question.
Centrality is structural exposure rather than proven influence, so validate with behavior.
Teleport and clean before trusting prestige scores on directed or messy graphs.