Charakteristiky sítí mohou být lokální, týkající se jednotlivých vrcholů, např. stupeň vrcholu, clustering, anebo globální, týkající se celé sítě, např. průměrná vzdálenost, průměrný klusterovací koefficient.
Centrality jsou funkce ohodnocující důležitost jednotlivých vrcholů $v$:
$\sigma_{x,y}$ počet nejkratších cest mezi $x$ a $y$ a
$\sigma_{x,y}(v)$ počet nejkratších cest mezi $x$ a $y$ procházejících $v$ je
$$C_B(v) = \sum_{u,v \in {V(G) \setminus v \choose 2}} \frac{\sigma_{x,y}(v)}{\sigma_{x,y}}$$Globální betweenness centrality $$\bar{C}_B(G) = \frac{1}{n} \sum_{v \in V(G)} C_B(v)$$
Průměrná vzdálenost vrcholů $$L(G) = \frac{1}{n(n-1)} \sum_{\substack{u,v \in V(G)\\ u \neq v}} d(u,v)$$
Věta Buď $G$ neorientovaný graf velikosti $|V(G)| = n$, $L(G)$ jeho průměrná vzdálenost vrcholů a $\overline{C}_B(G)$ jeho globální betweeness centrality. Potom platí $\overline{C}_B(G) = (n - 1) (L(G) - 1)$.
Lemma Buď $G$ graf velikosti $n$ a buď $G'$ graf získaný z $G$ přidáním hrany mezi náhodnými vrcholy $u,v$ ve vzdálenosti $d = d(u,v) > 1$. Potom platí $$\overline{C}_B(G') \leq \overline{C}_B(G) - \frac{2(d - 1)}{n}.$$
Důsledek Buď $G=(V,E)$ graf, $G'=(V,E')$ jeho podgraf na všech vrcholech a $r = | E \setminus E'|$. Potom $$\overline{C}_B(G) \leq \overline{C}_B(G') - \frac{2r}{n}.$$
Důsledek Buď $G=(V,E)$ graf, kde $|V|=n$ a $|E|=m$, a buď $T$ jeho kostra. Potom $$\overline{C}_B(G) \leq \overline{C}_B(T) - \frac{2(m - n + 1)}{n}.$$
Vrchol je list pokud $\deg(v) = 1$ a k-okolí vrcholu definujeme jako $$\Gamma_k(v) = \{v\in V : d(u,v) = k\}.$$
Věta Buď $G$ graf velikosti $n$, $w \in V$ vrchol s výstředností $\epsilon(w)$ a buď $G'$ graf získaný z $G$ připojením vrcholu $u$ hranou $\{u,w\}$. Potom $$\overline{C}_B(G') = \frac{n}{n + 1}\overline{C}_B(G) + \frac{2}{n + 1}\sum_{k=1}^{\epsilon(w)} k|\Gamma_k(w)|.$$
Tvrzení Buď $G$ graf velikosti $n$ a buď $G'$ graf získaný z $G$ přidáním nového vrcholu $w$ a hran spojující jej s vrcholy $u$ a $v$ ve vzdálenosti $1 \leq d(u,v) \leq 2$ potom $$\frac{1}{n+1} \left[n\overline{C}_B(G) + n - 2\right] \leq \overline{C}_B(G').$$
Úloha 1: Pojďme vymyslet příklady různých druhů sítí a jejich parametrů.
Výsledky našich úvah si ověříme na některém z praktických cvičení.
Úloha 2: Vymysli vzorec pro betweenness centralitu vrcholů
Vzorec bude záviset na $n$ jakožto počtu vrcholů grafu a v některých případech i na nějakém dalším parametru. Pokud $n$ nebude stačit, zadefinuj a použij ve vzorci vlastní parametr.
Úloha 3: Odhadni, jak se změní betweenness centralita, jestliže