Betweenness centrality $$C_B(v) \leftarrow \sum_{s\neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}},$$ where $\sigma_{st}(v)$ is the number of shortest path from $s$ to $t$ through $v$ and $\sigma_{st}$ is the same but without condition about $v$.
Notation:
Main ideas:
Lemma (Bellman criterion) A vertex $v \in V$ lies on a shortest path between vertices $s, t \in V$, if and only if $d(s, t) = d(s,v) + d(v,t)$.
Observation Betweenness centrality is a sum of pair dependencies: $$C_B(v) = \sum_{s\neq v \neq t} \delta_{st}(v)$$
Lemma For $s \neq v$ we have $$\sigma_{sv} = \sum_{u\in P_s(v)} \sigma_{su}$$
Lemma If there is exactly one shortest path from $s\in V$ to each $t\in V$, the dependency of $s$ on any $v\in V$ obeys $$\delta_{s\bullet}(v) = \sum_{w: v\in P_s(w)} \left(1 + \delta_{s\bullet}(w)\right)$$
Theorem The dependency of $s \in V$ on any $v \in V$ obeys $$\delta_{s\bullet}(v) = \sum_{w: v\in P_s(w)} \frac{\sigma_{sv}}{\sigma_{sw}}\left(1 + \delta_{s\bullet}(w)\right).$$
for counting betweenness centrality.
Proposition Let $G$ be a graph with $n$ vertices. Then for all $v\in V(G)$ holds $0\leq C_B(v) \leq (n-1)(n-2)$.
Let the set of neighbours of a vertex $v$ be $\Gamma_G(v)$.
Proposition Let $G$ and $v \in V(G)$. Then $C_B(v) = 0$ if and only if $G[\Gamma_G(v)] \cong K_{\deg(v)}$.
Example Betweenness centrality in graph $K_n - \{u,v\}$. $$C_B(w) = \begin{cases} \frac{1}{n-2} & w \neq v,u\\ 0 & \text{ otherwise } \end{cases}$$
Proposition For each rational number $c = \frac{p}{q}$ we can construct a graph $G_c$, which contains vertex $v$ such that $C_B(v) = c$.
Construction of a graph $G_c$ Let us have disjoint union of
- $K_p$, $K_{q-1}$ and edge $\{u,v\}$
- $u$ connect to $K_p$ and $v$ with $K_{q-1}$
- make a full join of $K_p$ and $K_{q-1}$
Proposition Let $G$ be a graph with maximál degree $\Delta$. Then $$C_{B\max}(G) = \max_{v\in V(G)} C_B(v) \leq \frac{\Delta - 1}{2\Delta}(n-1)^2$$
Maximal betweenness
Specifically, the maximal betweenness of the class of all graphs $\mathcal{G}$ is $$C_{B\max}(\mathcal{G}) = \frac{(n-1)(n-2)}{2}.$$ Maximal betweenness of a family of graphs with maximal degree $\Delta$ is $$C_{B\max}(\mathcal{G}_{\Delta}) = \frac{\Delta - 1}{2\Delta}(n-1)^2.$$
$F_{r,s}$ is a complete bipartite connection of an independent set $I_r$ and a path $P_s$.
Proposition Let $G$ be a $2$-connected graph of size $n$. Then $$C_{B\max}(G) \leq \frac{(n-3)^3}{2}.$$ Equality is is obtained for graph $F_{1,n-1}$.
Automorphism group $\text{Aut}(G)$ is a set of bijections $\sigma : V \rightarrow V$, which preserve edges. Centrality values are preserved by automorphism group.
Graph $G$ is betweenness uniform, if $C_B(v) = C_B(u)\ \forall\ u,v \in V(G)$.
Graph $G$ is vertex transitive, if $\forall x,y\in V(G)$ exists automorphism $\sigma$ mapping $x \rightarrow y$. From this trivially follows $C_B(x) = C_B(y)$, so
Observation Vertex transitive graphs are betweenness uniform.
Remark: There are betweenness uniform graphs, which are neither vertex transitive nor regular.
Theorem Every betweenness uniform graph is $2$-connected.
Lemma Let $G=(V,E)$ be a graph with diameter $2$. Then for any $x\in V$ it holds $$C_B(x) = \sum_{\substack{(u,v)\in \Gamma^2(x) \\ uv\notin E(G)}} 1/\sigma_{u,v}.$$
Lemma Let $G=(V,E)$ be betweenness uniform graph with diameter $2$, $|V|=n$ and $|E|=m$. Then for any $x\in V$ it holds $C_B(x) = n - 1 - 2m/n$.
Theorem Let $G=(V,E)$ be betweenness uniform graph with $\Delta(G) = n - 1$ and $|V|=n$. Then $G \cong K_n$.
Theorem Let $G=(V,E)$ be betweenness uniform graph with $\Delta(G) = n - 2$ and $|V|=n$. Then diameter of $G$ is equal to $2$.
Theorem Let $G=(V,E)$ be betweenness uniform graph. Then $C_B(v) = 0$ or $C_B(v) \geq 1$.
Proposition Assume $G$ is betweenness uniform graph and let $G'$ be a graph, which is created by
- substituing each vertex $v$ with a complete graph $K_a$ for some natural $a$, whose vertices we denote by $v_1, \dots, v_a$, and
- adding $(v_i, u_j) \in E(G')$ for all $i,j \in [a]$ whenever $(v, u) \in E(G)$. Then $G'$ is also betweenness uniform.
Task 1: Express the number of shortest paths between vertices $x$ and $y$, i.e. $\sigma_{xy}$ in the network created from two full binary trees of height $L$ as in picture below, using their levels. What is the number of such paths passing through vertex $z$, i.e. $\sigma_{xy}(z)$, again depending on its level.
Solution: We call vertical layers "levels" and horizontal layers as "lines". We want to express $\sigma_{xy}$ based on the level $i$ of $x$ and level $j$ of $y$.
Observation If $i,j \leq L$ or $i,j \geq L$, there is only one shortest path between them which is using the respective tree, so $\sigma_{xy} = 1.$
For $i,j$ such that $i \leq L$ and $j \geq L$ we first observe how $\sigma_{xy}$ behaves if their lines are as close as possible.
The easiest case is when $i = j$. We can iteratively use the lemma claiming that $$\sigma_{sv} = \sum_{u\in P_s(v)} \sigma_{su}.$$ In each step from $y$ towards $x$ there are always two predecessors until we reach layer $L$. After then there is always only one predecessor. By summing the respective shortest paths we obtain that $$\sigma_{xy} = 2^{k}$$ for $k = |L - i| = |L-j|$. Furthermore, by making $x$ or $y$ further from layer $L$, number of shortest paths does not change, as by doing this there is always only one predecessor on the shortest path when backtracking. This gives that for $i \neq j$ on as close lines as possible there are $$\sigma_{xy} = 2^{k}$$ for $k = \min\{|L - i|, |L - j|\}$.
As last step, we realize that when having $x$ and $y$ on lines further from each other, we can go from e.g. $x'$ with the closest line and then uniquely traverse the tree to $x$. There is also possibility to go to $y'$ on closest line and then traverse to $y$, so for $x$ and $y$ on lines further from each other we just multiply the result by two.
At last, for the vertex $z$ which lies between the vertices $x$ and $y$ we can compute $\sigma_{xy}(z)$ by using a lemma from the lecture which claims $\sigma_{xy}(z) = \sigma_{xz} \cdot \sigma_{zy}$. Note that one of these values is always one because of our initial observation.
Task 2: Decide if the following graphs are betweenness-uniform or not.
1)
Solution: This graph can be also drawn as a "diamond" with a square in the middle and two vertices fully connected to the middle square. There is automorphism between any two vertices of the middle square (rotation) and also between the upper/lower vertex and any vertex of the square. This means that the graph is vertex transitive and thus betweenness uniform.
2)
Solution: This graph is a result of "blowing-up" $K_3$ by $K_2$'s as in the proposition, so this graph is betweenness uniform.
3)
Solution: This graph has two equivalent (in terms of automorphisms) groups of vertices, the two vertices of the "roof" and four vertices of the base. For both groups it can be shown by manual computation that their betweenness if $\frac{2}{3}$. This graph is the smallest betweenness uniform graph, which is not regular.
4)
Task 3: Let $G$ be a betweenness-uniform graph on $n$ vertices and $H_1, H_2, \dots, H_n$ be betweenness-uniform graphs. Let $G'$ be a graph obtained by replacing each vertex $i$ by $H_i$ and doing full join between $H_i$ and $H_j$ whenever $i$ is adjacent to $j$. Prove or disprove the claim that $G'$ is betweenness-uniform.
Solution: This can be disproved by e.g. taking even cycle and blowing up every second vertex by $K_2$ and every other by $K_1$. The result is clearly not betweenness uniform.