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 3 of 27
The real wordsTheory

Degree centrality

Undirected: C_D(i) = d(i) / (n - 1) Directed: C'_D(i) = d_out(i) / (n - 1)

d(i) is the node's degree, the number of edges at it; n is the number of nodes, so n - 1 is the most neighbours anyone could have. The result is therefore a fraction between 0 and 1.

What it finds: very connected, popular individuals; people likely to hold most information; people who can quickly connect with the wider network. In and out degree are worth reporting separately for transactional data.

← BackContinue →