Skip to content
Sem 5 Prep
← Visual AnalyticsCentrality and prestige

Formulas for this chapter

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
Step 5 of 27
The real wordsPractical

The geodesic distance matrix

Geodesic distanceThe length of the shortest path between two nodes, counted in edges. d(i,j).
Geodesic distance matrixThe square table of every d(i,j), with zeros down the diagonal.

Build it in waves from each node: the neighbours are at distance 1, their unvisited neighbours at 2, and so on. For an undirected network the matrix is symmetric, so you only have to fill half of it.

Every closeness and betweenness number comes out of this table, so build it first and check it before going on.

← BackContinue →