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 1 of 27
The ideaTheory

Who is the most important person here

Three people in an office. Asha knows everyone. Bala knows only two people, but he is the only link between the sales floor and the factory. Chandra knows four people, and every one of them knows everyone else.

Who is most important? All three, and for different reasons. Asha is popular, Bala is a bottleneck, Chandra is well placed.

Each measure in this chapter picks one of those meanings and turns it into a number.

← BackContinue →