Grafy a sítě

Zde jsou mé poznámky z přednášky, kterou vede docent David Hartman (kompletní výčet všech jeho titulů najdete na jeho stránkách). Během semestru je budu postupně aktualizovat.

View source

Motivace a příklady

Chceme reálný svět/systém modelovat grafem/sítí, se kterou se pracuje lépe. Z této sítě pak spočítáme nějaký reálný vektor (např. pravděpodobnostní distribuce), který nám říká něco o reálném světě.

Příklad: (Twitter) Reprezentujeme sítí $G = (V,E)$ : Vrcholy $V$ reprezentují uživatele/profily/stránky a orientovaná hrana $uv \in E$ představuje vztah, že uživatel $u$ sleduje $v$ .

po síti se nám rozšířily dezinformace a my bychom chtěli vědět, kde vznikla (root finding problem)
sociální sítě umí být dobrý prediktor vývoje akciového trhu
recommender systems – cílená reklama

Small-world

Problém: modely reálných systémů mohou být obrovské

nebudeme tak modelovat celý systém, ale jen některý jeho sample, to může mít ale svá úskalí

Příklad: (Milgram experiment) Vzdálenost mezi dvěma lidmi skrze hrany reprezentující přátelství je malá.

ve státě Omaha jeden člověk poslal svému okolí dopis, který měli přeposlat cílovému recipientovi, nebo někomu o kom si myslí, že by jej mohl znát (aby nebyly cykly, v dopise byl seznam lidí, přes které již dopis přešel)
průměrná vzdálenost od počátku k cílovému recipientovi byla 6
později označeno pouze za small-world fenomén

Vague Definice: (small-world) Síť je označovaná za small-world (SW), pokud má tendence tvořit clustery vrcholů (husté podgrafy) a zároveň vzdálenost každých dvou vrcholů je malá.

síť koautorství článků – scientometrie
- vrcholy: autoři, hrany: relace „pracovali na stejné publikaci”
- Erdősovo číslo – vzdálenost od Paula Erdőse
  - Nešetřil má Erdősovo číslo 2 (I think)
síť citací
- vrcholy: papery, hrany: jeden paper se odkazuje na jiný
- může nám pomoct odhalit fake news nebo diskreditovat články založené na neplatných datech

Metody modelování

Příklad: (autoregresivní systémy) Máme velmi složitý systém a my se jej pokusíme modelovat lineárním modelem

$y_t = c + \bold{A y_{t-1}} + e_t$ $y_{t} = c + A y_{t - 1} + e_{t}$
- $c$ : konstantní bias
- $e_t$ : náhodná veličina
- $\bold{y_{t-1}}$ : vektor předchozího „stavu”
- $\bold A$ : matice modelující lineární závislost
typicky funguje dobře v krátkém časovém horizontu, na zkoumání delšího časového úseku už budeme potřebovat nejspíš přesnější model

Příklad: (klinické studie) Pacientovi uděláme MRI (nebo EEG) a z dat sestrojíme graf představující jak dobře jsou propojené jednotlivé komponenty mozku – tzv. temporální síť

např. pacienti s Alzheimerem měli temporální síť s daleko hustšími clustery a většími vzdálenostmi mezi vrcholy
typicky také vykazují small-world efekt

Příklad: (interakce proteinů) Máme graf protein-protein interakcí (PPIN) a pro každý protein známe jeho funkci. Chceme najít chování dvou proteinů v jejich společné interakci.

Neighborhood metody:
- pro každý vrchol $v$ je funkce daná nejčastější funkcí proteinu v jeho okolí
Community metody:
- pro každý vrchol $v$ je funkce daná nejčastější funkcí proteinu v jeho komunitě
- problém: hledání komunit je NP-těžký problém (dá se ale docela dobře aproximovat)

Příklad: (Internet) Vrcholy jsou IP adresy, hrany jsou jejich „spojení po internetu”

zajímá nás jak odolné jsou části sítě vůči defektům v infrastruktuře
WWW je obrovská síť u které nemáme šanci ji efektivně analyzovat najednou nebo dokonce i po menších částech, místo toho tak síť nějak aproximujeme
- graphon – převedeme graf do takové „spojité matice sousednosti” na intervalu $[0,1]^2$ $[0, 1]^{2}$
  - nyní už nemůžeme mluvit o hranách, ale máme spíš něco jako pravděpodobnostní rozdělení
- Erdős-Rényi graf – mezi každými dvěma vrcholy je pravděpodobnost $p$ $p$ , že tam existuje hrana
  - zajímá nás pak třeba očekávaná délka cesty mezi dvěma vrcholy
  - můžeme mít více různých navzájem nezávislých parametrů $p,q,r$ $p, q, r$ pravděpodobností existencí hran
    - krásně se s tím pracuje, ale bohužel je to docela trash model, protože moc dobře nereflektuje realitu
    - typicky v reálných sítích jsou tyto parametry závislé :(

Small-world

Clustering

Definice: (clustrovací koeficient) Pro graf $G$ a vrchol $v \in V(G)$ definujeme jeho (lokální) clustrovací koeficient jako

C_v(G) = \frac{|E(G[N_G(v)])|}{{\deg_G(v)}\choose2}

a pokud je stupeň $v$ roven 0 nebo 1, pak definujeme $C_v(G) = 0$ .

👁️ : $0 \le C_v(G) \le 1$ $0 \leq C_{v} (G) \leq 1$
- $C_v(G)$ můžeme interpretovat jako pravděpodobnost, že nějací dva sousedé $v$ jsou spojeni hranou
grafy s $\forall v \in V(G) : C_v(G) = 0$ – grafy bez trojúhelníků
grafy s $\forall v \in V(G) : C_v(G) = 1$ – disjunktní sjednocení úplných grafů
$C_v(G)$ není monotónní – přidání hrany může snížit hodnotu

Definice: (průměrný clustrovací koeficient) Pro graf $G$ , kde $n = |V(G)|$ , definujeme průměrný clustrovací koeficient jako

C(v) = \frac 1 n \sum_{v \in V(G)} C_v(G)

kolik maximálně můžeme mít hran v grafu tak, aby $C(G) = 0$ ?

Definice: (Turánův graf) graf $T_r(n)$ je úplný $r$ -partitní graf na $n$ vrcholech, kde $n = q \cdot r + s$ pro $0 \le s < r$ . V grafu má $s$ partit velikost $\lceil \frac n r \rceil = q + 1$ a zbytek (tedy $r-s$ partit) má velikost $\lfloor \frac n r \rfloor = q$ .

👁️: graf $T_r(n)$ neobsahuje cyklus délky $r+1$ , tedy pro $r \ge 2$ platí $C(T_r(n)) = 0$

Definice: (počet hran $T_r(n)$ ) definujme $t_r(n) := |E(T_r(n))|$

v $T_r(n)$ je každý vrchol spojen s každým dalším vrcholem, který není ve stejné partitě

úplný graf má $n \choose 2$ hran
máme $s$ partit velikosti $q + 1$ , v každé chybí $q+1\choose2$ hran
máme $r-s$ partit velikosti $q$ , v každé chybí $q\choose2$ hran

Dohromady tak máme $t_r(n) = {n\choose2} - s{q+1\choose2} - (r-s){q\choose2}$ . Tento výraz je maximalizován pro $n$ takové, že $r | n$ , tedy když $s = 0$ . To nám dává horní odhad na $t_r(n) \le \frac{r-1}r \cdot \frac{n^2}2$

Věta: (Turán 1940) Každý graf $G$ na $n$ vrcholech s více než $t_r(n)$ hranami obsahuje $K_{r+1}$ jako podgraf

Důkaz: Idea – ukážeme, že graf bez podgrafu $K_{r+1}$ s maximálním počtem hran je přesně $T_r(n)$ .

Mějme graf $G$ bez podgrafu $K_{r+1}$ a vezměme $v$ s maximálním $\deg(v)$ . Označme $A = N(v)$ , $B = V \setminus (A \cup \{v\})$ . Nyní sestrojme nový graf $G'$ z grafu $G$ odstraněním všech hran v $B$ a přidáme všechny hrany mezi $A$ a $B$ . To nám dává $e(G') - e(G) = |A|\cdot|B| - e(A,B) - e(B)$ . Nyní si všimněme:

$\deg(x) \le \deg(v), \forall x \in B$
$\deg(x) = \deg_A(x) + \deg_B(x) \le |A|$ jelikož máme prázdné $B$ a $x \not\sim v$

Součtem těchto dvou přes všechna $x$ dostaneme $\sum_{x\in B} \deg(x) = \sum_{x \in B} \deg_A(x) + \sum_{x\in B}\deg_B(x) \le |A|\cdot|B|$ . Jelikož $e(A,B) + e(B) \le e(A,B) + 2e(B) = \sum_{x \in B} \deg(x)$ , pak dosazením výsledku výše dostáváme

e(G') - e(G) = |A|\cdot|B| - (e(A,B) + e(B)) \ge |A|\cdot|B| - |A|\cdot|B| = 0

To znamená, že touto operací jsme jenom zvýšili počet hran. Konstrukce $G'$ navíc zaručuje, že pokud $G$ neobsahoval $K_{r+1}$ , pak jej neobsahuje ani $G'$ .

Tento proces můžeme opakovat a nakonec dostaneme $T_r(n)$ .

Průměrná délka cesty

Definice: (průměrná délka cesty) pro metriku $d(u,v)$ na grafu $G$ definujeme průměrnou délku cesty v $G$

L(G) = \frac 2 {n(n-1)} \sum_{\{u,v\} \subseteq V, u\ne v} d(u,v) = \frac 1 {n(n-1)} \sum_{u,v \in V, u \ne v} d(u,v)

úplné grafy — $L(K_n) = 1$
hvězdičky — $L(S_n) = \frac{2(n+1)}n$ , což jde ke 2 s $n\to\infty$
cykly (předpokládáme $n=2k+1$ pro lepší počítání) $L(C_n) = \frac{n+1}4$

Definice: (hustota grafu) pro graf $G$ s $n = |V(G)|$ a $m = |E(G)|$ definujeme jeho hustotu jako

\rho(G) = \frac m {n \choose 2}

počet hran ku maximálnímu počtu hran
úplný graf má $\rho(G) = 1$ , graf bez hran má $\rho(G) = 0$

Určování small-world grafů

Definice: (ring-lattice) TODO

Definice: (Erdős-Renyi graf) Erdős-Renyi graf $G_{n,p}$ je náhodný graf konstruovaný následovně:

Mějme vrcholy $V = \{1,2,\dots,n\}$
Pro každou dvojici různých vrcholů ${i,j} \in V$ přidáme hranu $ij$ do $E$ s pravděpodobností $p$

👁️ nechť $k$ $k$ je cca průměrný stupeň, pak
- $L(G_{n,p}) \sim \frac {\log n} k$
- $C(G_{n,p}) \sim \frac k n$

Místo toho abychom přímo požadovali po grafech specifické vlastnosti, použijeme Erdős-Renyi graf jako „referenční model:”

Definice: (small-world) graf $G$ je small-world, pokud $L(G) \gtrsim L(R_G)$ a $C(G) \gg C(R_G)$ pro referenční náhodný graf $R_G$ .

$R_G$ může být Erdős-Renyi graf, nebo nějaký jiný
při tvorbě $R_G$ chceme alespoň přibližně zachovat hustotu $\rho(G) = \rho(R_G)$