13 Research methods, statistics, critical review and evidence-based practice13.13 Network analysis
13.13.4 Degree, centrality and network distances
3 min read1 figure
Written by Resident Doctor Committee · Published
New in the 2027 syllabus
The College added this topic for exams from January 2027.
Degree and strength
Degree is the number of edges (lines) attached to a node in a simple undirected graph. An isolated node, with no edges, has degree zero.
In-degree and out-degree apply to a directed graph, where each edge points one way. In-degree counts incoming edges. Out-degree counts outgoing edges.
Normalised degree centrality divides a node's degree by n - 1, where n is the number of nodes in a simple graph.
Strength is the version usually used in symptom networks. It adds up the absolute weights of a node's connections. This separates a node with several weak associations from one with several strong ones.
Centrality measures
Centrality measure | What gives a node a high value |
|---|---|
Degree | Many direct connections |
Strength | A large total of absolute connection weights |
Closeness | Short shortest-path distances to the other nodes |
Betweenness | Lying on a large share of the shortest paths between other pairs |
Eigenvector | Connections to nodes that themselves score highly |
Each measure answers a different question, so their rankings need not agree. For example, a node that bridges two groups can have high betweenness even when it has few direct connections.
Paths and diameter
A path is a route along edges that never visits the same node twice. In an unweighted graph, its length is the number of edges it crosses.
The shortest path between two nodes in an unweighted graph is the one that uses the fewest edges.
Closeness centrality, in a connected undirected graph, is the reciprocal (1 divided by the value) of the mean shortest-path distance from a node to all other nodes.
Network diameter is the longest of the shortest-path distances between pairs of nodes in a connected graph.
In a disconnected network some pairs of nodes cannot reach each other. To get a finite diameter you have to say which connected component you mean. Otherwise the diameter is undefined or treated as infinite.
Network density
Density is the proportion of possible edges that are actually present. It describes the whole network, not a single node.
A simple undirected graph with n nodes allows n x (n - 1) / 2 edges, so density = 2 x observed edges / [n x (n - 1)].
A simple directed graph allows n x (n - 1) edges, because an edge in each direction counts separately.
Worked example
A simple undirected graph has four nodes and the edges A-B, A-C, B-C and C-D.
Node | Direct neighbours | Degree |
|---|---|---|
A | B, C | 2 |
B | A, C | 2 |
C | A, B, D | 3 |
D | C | 1 |
There are four edges. The possible number is 4 x 3 / 2 = 6. So density = 4 / 6 = 0.67.
C has degree 3, so its normalised degree centrality = 3 / (4 - 1) = 1.
The shortest path from A to D is A-C-D, which has length 2. No pair is further apart, so the diameter is 2.
C is one edge from every other node. Its mean distance is 1, so its closeness centrality is 1 / 1 = 1.
Interpreting symptom networks
Sampling uncertainty can change estimated edge weights and centrality rankings. Check how stable they are before reading anything into small differences between nodes.
High centrality in an observational symptom network does not show that a symptom causes others, or that it is the best target for treatment.
Weighted shortest paths need a stated rule for turning association strength into distance. Do not automatically treat a strong association as a long distance.