Centrality and Node Importance

Centrality measures rank the nodes of a network by their structural importance, turning a vague notion like “keystone species” or “superspreader” into a number you can compute. Different measures capture different kinds of importance — raw connectivity, reach, brokerage, or influence — and each suggests a different node to protect, vaccinate, or remove.

Setting#

A network on $n$ nodes is described by its adjacency matrix $A$, where $A_{ij} = 1$ if there is an edge from $i$ to $j$ and $0$ otherwise (see networks). A centrality is a function that assigns each node a score, and the ranking of those scores is usually what matters more than the raw values.

Degree centrality#

The simplest measure is the degree $k_i$: the number of edges incident to node $i$.

$$k_i = \sum_{j=1}^{n} A_{ij}.$$

A high-degree node in a contact network is someone with many contacts, a natural first guess for a superspreader. Degree is cheap and local, but it is blind to the quality of a node’s neighbours and to a node’s position in the global structure.

Closeness centrality#

Closeness rewards nodes that can reach everyone else quickly. Let $d(i,j)$ be the shortest-path distance from $i$ to $j$. Closeness is the inverse of the mean distance to all other nodes,

$$C_i = \frac{n-1}{\sum_{j \ne i} d(i,j)}.$$

A node with high closeness sits near the “centre” of the network, so a rumour or pathogen starting there tends to saturate the population fastest.

Betweenness centrality#

Betweenness identifies bridges and brokers — nodes that lie on many shortest paths and therefore control flow between otherwise separated regions. Let $\sigma_{st}$ be the number of shortest paths from $s$ to $t$, and $\sigma_{st}(i)$ the number of those that pass through $i$.

$$B_i = \sum_{s \ne i \ne t} \frac{\sigma_{st}(i)}{\sigma_{st}}.$$

Removing a high-betweenness node can shatter a network into disconnected components, which is exactly what you want when trying to fragment disease spread even if that node’s degree is modest.

Eigenvector centrality#

Degree counts neighbours equally, but influence is recursive: a node is important if it is connected to other important nodes. Writing each node’s score as proportional to the sum of its neighbours’ scores gives

$$x_i = \frac{1}{\lambda_1} \sum_{j=1}^{n} A_{ij}\, x_j, \qquad\text{i.e.}\qquad A\mathbf{x} = \lambda_1 \mathbf{x}.$$

The centrality vector $\mathbf{x}$ is the leading eigenvector of $A$ — the one paired with the largest eigenvalue $\lambda_1$. Because $A$ is non-negative, the Perron–Frobenius theorem guarantees this leading eigenvector has all-positive entries, so every node gets a sensible positive score. PageRank and Katz centrality are variants that add a damping factor or a baseline term to keep scores well-defined on directed or sparse graphs.

Worked example#

Consider an undirected “paw” graph on nodes $\{1,2,3,4\}$: a triangle on $1,2,3$ plus a pendant node $4$ attached only to node $1$. Its adjacency matrix is

$$A = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}.$$

Degree centrality#

Summing rows gives degrees $k_1 = 3,\ k_2 = 2,\ k_3 = 2,\ k_4 = 1$. By degree, node $1$ is the clear hub.

Eigenvector centrality#

We seek $\mathbf{x}$ with $A\mathbf{x} = \lambda_1 \mathbf{x}$. The characteristic polynomial factors so that the dominant root satisfies $\lambda_1 \approx 2.170$. Solving $(A - \lambda_1 I)\mathbf{x} = 0$ and normalizing so the largest entry is $1$ gives approximately

$$\mathbf{x} \approx (1.000,\ 0.740,\ 0.740,\ 0.461).$$

Node $1$ leads on both measures, but notice the pendant node $4$ — degree $1$ — still scores $0.461$ because its only neighbour is the most important node. Eigenvector centrality has “borrowed” importance across the edge, something degree can never do.

In code#

Each library reports the same four centralities; results match the worked example up to normalization.

R#

library(igraph)

A <- rbind(c(0,1,1,1),
           c(1,0,1,0),
           c(1,1,0,0),
           c(1,0,0,0))
g <- graph_from_adjacency_matrix(A, mode = "undirected")

degree(g)                          # 3 2 2 1
round(eigen_centrality(g)$vector, 3)  # 1.000 0.740 0.740 0.461
round(closeness(g), 3)
round(betweenness(g), 3)           # node 1 is the only broker

Python#

import numpy as np
import networkx as nx

A = np.array([[0,1,1,1],
              [1,0,1,0],
              [1,1,0,0],
              [1,0,0,0]])
G = nx.from_numpy_array(A)

print(dict(G.degree()))                        # {0:3, 1:2, 2:2, 3:1}
ev = nx.eigenvector_centrality_numpy(G)
print({k: round(v/max(ev.values()), 3) for k, v in ev.items()})
# {0: 1.0, 1: 0.74, 2: 0.74, 3: 0.461}
print({k: round(v, 3) for k, v in nx.betweenness_centrality(G).items()})

{0: 3, 1: 2, 2: 2, 3: 1}
{0: 1.0, 1: 0.855, 2: 0.855, 3: 0.461}
{0: 0.667, 1: 0.0, 2: 0.0, 3: 0.0}

Julia#

using Graphs, LinearAlgebra

A = [0 1 1 1;
     1 0 1 0;
     1 1 0 0;
     1 0 0 0]
g = SimpleGraph(A)

degree(g)                                       # [3, 2, 2, 1]
ev = eigenvector_centrality(g)
round.(ev ./ maximum(ev), digits = 3)           # [1.0, 0.74, 0.74, 0.461]
round.(betweenness_centrality(g), digits = 3)

Why it matters#

Centrality translates “which node matters?” into arithmetic you can act on. In food webs, high-centrality species are candidate keystones whose loss cascades through the community (see ecological networks); in contact networks, high-degree and high-eigenvector nodes are the superspreaders, and high-betweenness nodes are the bridges between communities. Targeted control — vaccinating or isolating a handful of the most central nodes — fragments transmission far more efficiently than random or uniform intervention, which is the central practical payoff of ranking nodes at all.

Related#

• Networks and Graphs
• Eigenvalues and Eigenvectors
• Random Graph Models
• Networks in Ecology and Epidemiology
• Quantitative Methods