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.
Task 2: Decide if the following graphs are betweenness-uniform or not.
1)
2)
3)
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.