Of Notes

Centrality

2 min read · revised 16 October 2026 · referred to by 2 notes · ·

We are gonna say there are four types of centrality:

  • Degree - how connected a node is
  • Closeness - How close to targets
  • Betweenness - Traffic based (flow of information)
  • Eigenvector - Connection to important nodes

We define some sort of average distance of a node by saying:

Closeness Centrality

This is the complement of the average distance:

Betweenness Centrality

This is some information about the importance of a node for moving around some graph.

We first define and which both measure the number of paths within a graph.

and

Two kinds of path count between \(j\) and \(l\): \(g(j,l;A)\) counts all shortest paths, here \(g = 2\) — the ones through \(i\) and through \(a\). Of those, \(n_i(j,l;A) = 1\) passes through \(i\) (accented), so this pair contributes \(n_i / g = 1/2\) to the betweenness of \(i\).
Fig. 1. Two kinds of path count between and : counts all shortest paths, here — the ones through and through . Of those, passes through (accented), so this pair contributes to the betweenness of .

Using these two we then define:

which can be simplified for a tree graph by removing the node and considering sub-graphs of which we count the nodes:

where represents the number of nodes inside the sub-graph.

Removing \(i\) (accented) from a tree falls the graph into \(k_i(A)\) disconnected sub-graphs, one per neighbour, with \(N_\alpha(i)\) nodes each. Pairs of nodes in different sub-graphs have no route left except through \(i\).
Fig. 2. Removing (accented) from a tree falls the graph into disconnected sub-graphs, one per neighbour, with nodes each. Pairs of nodes in different sub-graphs have no route left except through .

Identities

like when they are 1

Eigenvector Centrality

TODO study this in more depth and derive the concept

/ or Ctrl K
search; empty, it shows notes to revise and lately read
m
mark this note to revise, or unmark it
c
cover maths, proofs and solutions to test yourself
n
uncover the next covered item
y
copy this note’s org-roam link
e
copy this note as markdown, LaTeX kept as TeX
p
the next problem to work; there h hints, s shows the solution, x passes it for today
→ ← j k space
turn the page, when reading in pages
l
on the map, trace the greatest distance, then the longest path
double-click
a formula, to copy its TeX
rest on maths
bind a part of a formula and open the wheel of notes it comes from; scroll or ↑ ↓ widens it, 1–6 goes
?
this card