Degree centrality
C_D(i) = d(i) / (n - 1) C'_D(i) = d_out(i) / (n - 1)
To find popular, highly connected nodes. Report in-degree and out-degree separately for transactional data. Both Centrality Question papers use total degree for the directed case; say which you use.
- d(i)
- Degree of node i: the number of edges at it
- d_out(i)
- Out-degree: arrows leaving node i
- n - 1
- The largest degree any node could have
Closeness centrality
C_C(i) = (n - 1) / SUM over j of d(i,j)
To find the best broadcasters, the nodes that can reach the whole network fastest. Weak discriminator in a dense network, so use it within one cluster. Unreachable distances are entered as 100.
- d(i,j)
- Geodesic distance from i to j, in edges; 100 if j is unreachable
- n - 1
- Numerator, so a node one step from everyone scores 1
Betweenness centrality
C_B(i) = SUM over j < k of p_jk(i) / p_jk
To find bridges and gatekeepers who control flow between clusters. Neither j nor k may be i. Normalise by the number of pairs and state which pair set you used.
- p_jk
- Number of shortest paths between j and k
- p_jk(i)
- How many of those pass through i
- pairs
- C(n,2) = n(n-1)/2 pairs in total; the deck instead uses the pairs excluding i
Degree prestige
P_D(i) = d_in(i) / (n - 1)
Directed networks only. Raw popularity: how many nodes point at you. The number of followers, not the number you follow.
- d_in(i)
- In-degree: arrowheads pointing at node i
- n - 1
- The most in-links any node could have
Proximity prestige
P_p(i) = SUM over j in I_i of d(j,i) / |I_i|
Directed networks. Accessibility: how close the nodes that can reach you are. A mean distance, so LOWER is better, and it must be quoted alongside |I_i|.
- I_i
- The set of nodes that can reach i by a path of any length
- |I_i|
- How many nodes are in that reaching set
- d(j,i)
- Shortest distance from j to i, following the arrows
Unreachable-node convention
d(i,j) = 100 when j cannot be reached from i
In any closeness or distance-matrix calculation on a directed network. The worked solution writes "Use – as 100". Some texts use n instead; state your choice, and expect the score to collapse towards zero.
- 100
- The stand-in for an infinite distance used by this class
- d(i,j)
- Geodesic distance from i to j