Tvrzení Buď $G$ graf s $n$ vrcholy. Potom pro všechny $v\in V(G)$ platí $0\leq C_B(v) \leq (n-1)(n-2)$.
Množinu sousedů vrcholu $v$ budeme značit $\Gamma_G(v)$.
Tvrzení Buď $G$ a $v \in V(G)$. Potom $C_B(v) = 0$ právě tehdy, když $G[\Gamma_G(v)] \cong K_{\deg(v)}$.
Příklad Betweenness centralita v grafu $K_n - \{u,v\}$. $$C_B(w) = \begin{cases} \frac{1}{n-2} & w \neq v,u\\ 0 & \text{ jinak } \end{cases}$$
Tvrzení Pro každé racionální číslo $c = \frac{p}{q}$ dokážeme zkonstruovat graf $G_c$, který obsahuje vrchol $v$ takový, že $C_B(v) = c$.
Konstrukce grafu $G_c$ Mějme disjuktní sjednocení
- $K_p$, $K_{q-1}$ a hrany $\{u,v\}$
- $u$ propojíme s $K_p$ a $v$ s $K_{q-1}$
- $K_p$ a $K_{q-1}$ plně propojíme
Tvrzení Buď $G$ graf s maximálním stupněm $\Delta$. Potom $$C_{B\max}(G) = \max_{v\in V(G)} C_B(v) \leq \frac{\Delta - 1}{2\Delta}(n-1)^2$$
Maximální betweenness
Konkrétně maximální betweenness rodiny všech grafů $\mathcal{G}$ je $$C_{B\max}(\mathcal{G}) = \frac{(n-1)(n-2)}{2}.$$ Maximální betweenness rodiny grafů o maximálním stupni $\Delta$ je $$C_{B\max}(\mathcal{G}_{\Delta}) = \frac{\Delta - 1}{2\Delta}(n-1)^2.$$
$F_{r,s}$ je grafové spojení nezávislé množiny $I_r$ a cesty $P_s$.
Tvrzení Buď graf $G$ $2$-souvislý graf velikosti $n$. Potom $$C_{B\max}(G) \leq \frac{(n-3)^3}{2}.$$ Rovnost je dosažena u grafu $F_{1,n-1}$.
Grupa automorfismů grafu $\text{Aut}(G)$ je množina bijekcí $\sigma : V \rightarrow V$, které zachovávají hrany. Automorfismy zachovávají hodnoty centralit.
Graf $G$ je betweenness uniformní, pokud $C_B(v) = C_B(u)\ \forall\ u,v \in V(G)$.
Graf $G$ je vrcholově transitivní, pokud $\forall x,y\in V(G)$ existuje automorphismus $\sigma$ mapující $x \rightarrow y$. Z toho triviálně plyne i $C_B(x) = C_B(y)$, tedy
Pozorování Vrcholově transitivní grafy jsou betweenness uniformní.
Poznámka: Existují betweenness uniformní grafy, které nejsou vrcholově transitivní ani regulární.
Věta Každý betweenness uniformní graf je $2$-souvislý.
Lemma Buď $G=(V,E)$ graf s poloměrem $2$. Potom pro libovolné $x\in V$ platí $$C_B(x) = \sum_{\substack{(u,v)\in \Gamma^2(x) \\ uv\notin E(G)}} 1/\sigma_{u,v}.$$
Lemma Buď $G=(V,E)$ betweenness uniformní graf s poloměrem $2$, $|V|=n$ a $|E|=m$. Potom pro libovolné $x\in V$ platí $C_B(x) = n - 1 - 2m/n$.
Věta Buď $G=(V,E)$ betweenness uniformní graf s $\Delta(G) = n - 1$ a $|V|=n$. Potom $G \cong K_n$.
Věta Buď $G=(V,E)$ betweenness uniformní graf s $\Delta(G) = n - 2$ a $|V|=n$. Potom poloměr $G$ je roven $2$.
Věta Buď $G=(V,E)$ betweenness uniformní graf. Potom $C_B(v) = 0$ nebo $C_B(v) \geq 1$.
Tvrzení Nechť $G$ je betweenness uniformní graf a nechť $G'$ je graf, který vznikne
- nahrazením každého vrcholu $v$ úplným grafem $K_a$ pro nějaké přirozené $a$, jehož vrcholy označíme $v_1, \dots, v_a$, a
- přidáním hran $(v_i, u) \in E(G')$ pro všechna $i \in [a]$ kdykoli $(v, u) \in E(G)$. Potom $G'$ je také betweenness uniformní.
Betweenness centralitu můžeme spočítat pomocí balíku NetworkX následovně.
import networkx as nx
p8 = nx.path_graph(8)
cb_p8 = nx.betweenness_centrality(p8, normalized=False)
print(cb_p8)
for node in cb_p8:
print('vertex:{}, betweeness: {: 0.2f}'.format(node, cb_p8[node]))
{0: 0.0, 1: 6.0, 2: 10.0, 3: 12.0, 4: 12.0, 5: 10.0, 6: 6.0, 7: 0.0}
vertex:0, betweeness: 0.00
vertex:1, betweeness: 6.00
vertex:2, betweeness: 10.00
vertex:3, betweeness: 12.00
vertex:4, betweeness: 12.00
vertex:5, betweeness: 10.00
vertex:6, betweeness: 6.00
vertex:7, betweeness: 0.00
Parametr normalized=False říká, že chceme betweenness v reálných velikostech, nikoli vydělenou ${n-1 \choose 2}$.
Všimněte si, že tato funkce počítá betweenness pro neorientované cesty. Abychom získali hodnoty kompatibilní s hodnotami z přednášky a minulého cvičení, musíme tyto hodnoty násobit dvěma. (Anebo naopak vydělit dvěma vzorce z přednášky.)
Více informací k implementaci této funkce je v dokumentaci: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.betweenness_centrality.html#networkx.algorithms.centrality.betweenness_centrality
Úloha 1: Spočítej betweenness centralitu pro
Tyto třídy grafů jsou již naimplementované v NetworkX: https://networkx.org/documentation/stable/reference/generators.html#module-networkx.generators.classic Zkontroluj, zda výsledky odpovídají příkladům z přednášky a minulého cvičení.
Úloha 2: Napiš funkci is_betweenness_uniform(G), která pro zadaný graf ověří, zda je či není betweenness uniformní. Stáhněte si seznam betweenness uniformních grafů: https://iuuk.mff.cuni.cz/~anet/grafy-a-site/bugs.g6
Ověřte, zda jsou tyto grafy opravdu betweenness uniformní.
Z přednášky víme, že velkou skupinou betweenness uniformních grafů jsou vrcholově transitivní grafy. Testování této vlastnosti je trochu náročnější, a balík NetworkX ji přímo nepodporuje. Testování vrcholové transitivity a další algebraické operace nad grafy, jako například počítání automorfní grupy, jsou však implementované v SageMath(zkráceně Sage):https://doc.sagemath.org/html/en/index.html
Jedná se o poměrně rozsáhlý matematický software. Jednodušší než naimportovat Sage do Pythonu je spouštět Pythoní interpret uvnitř sage pomocí sage -python <skript>.py. Ve skriptu pak stačí zadat jednoduše from sage.all import * a používat veškeré funkce implementované v SageMath.
Návod k instalaci SageMath najdete zde: https://doc.sagemath.org/html/en/faq/faq-usage.html
Alernativou k instalaci Sage je jeho používání z některého online prostředí, například https://cocalc.com nebo https://sagecell.sagemath.org/.
Zpět k testování vrcholové transitivity. Sage obsahuje pro objekt Graph(ze Sage, nikoli NetworkX!) metodu is_vertex_transitive(). Konkrétní způsob volání a volitelné parametry viz dokumentace: https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.is_vertex_transitive
Úloha 3: Pomocí Sage zjistěte, které betweenness uniformní grafy z předchozí úlohy nejsou vrcholově transitivní.
Úloha 4: Naimplementujte funkci, která pro zadané číslo $c = \frac{p}{q}$ zkonstruuje graf obsahující vrchol $v$, pro který $C_B(v) = \frac{p}{q}$.